NOI2014 Day2 废话题解

program bzoj3670;
 
type tnode=record
        n,next:longint;
     end;
     snode=record
        n,t1:longint;
     end;
  
const maxn=1000017;
      maxm=3000017;
      mo=1000000007;
 
var str:array[0..maxn] of char; 
    pre,g:array[0..maxn] of longint;
    mem:array[0..maxm] of tnode;
    s:array[0..maxn] of snode;
    n,m,top,memsize,caseno:longint;
 
procedure insnbs(u,v:longint); inline;                                          begin
inc(memsize); with mem[memsize] do begin n:=v; next:=g[u]; end; g[u]:=memsize;  end;
 
procedure init;
var i,j:longint;
begin
n:=0; while not seekeoln do begin inc(n); read(str[n]); end; readln; 
fillchar(pre,sizeof(pre),0); j:=0; pre[1]:=0; for i:=2 to n do begin
        while (j>0)and(str[j+1]<>str[i]) do j:=pre[j]; 
        inc(j,byte(str[j+1]=str[i])); pre[i]:=j;
end; fillchar(g,sizeof(g),0); memsize:=0; for i:=1 to n do insnbs(pre[i],i); 
end;
 
function dfs(u:longint):int64;
var i,j:longint;
begin
dfs:=1; top:=1; s[top].n:=u; s[top].t1:=g[u]; i:=1;
while top>0 do begin
        if s[top].t1=0 then begin
                dec(top); j:=s[top].n>>1; while s[i].n>j do dec(i);  
        end else begin
                inc(top);                       s[top].n:=mem[s[top-1].t1].n;
                s[top].t1:=g[s[top].n];         s[top-1].t1:=mem[s[top-1].t1].next;
                j:=s[top].n>>1; while s[i+1].n<=j do inc(i); dfs:=dfs*i mod mo;
        end;
end;
end;
 
begin
readln(caseno); while caseno>0 do begin dec(caseno);
        init; writeln(dfs(0));
end;
end.

program bzoj3671;
 
const maxn=25000017;
      maxr=5017;
      mask=1<<16-1;
 
var a,p:array[0..maxn] of longint;
    tr1,tc1,tr2,tc2:array[0..maxr*5] of longint;
    n,row,col,zkwr,zkwc:longint;
 
procedure init;
var i,j,k,t,pa,pb,pc,pd:longint;
begin
readln(a[0],pa,pb,pc,pd); readln(row,col,k); n:=row*col;
for i:=1 to n do a[i]:=(int64(pa)*a[i-1]*a[i-1]+int64(pb)*a[i-1]+pc)mod pd;
for i:=1 to n do begin j:=a[i]mod i+1; a[i]:=a[j]; a[j]:=i; end;
while k>0 do begin dec(k); readln(i,j); t:=a[i]; a[i]:=a[j]; a[j]:=t; end;
k:=0; for i:=1 to row do for j:=1 to col do begin inc(k); p[a[k]]:=(i<<16)or j; end;
end;
 
function flag(x,y:longint):boolean;
var i,j:longint;
begin
i:=x+zkwr; j:=col-y; while i>0 do begin if (tr1[i]>=y)or(tr2[i]>j) then exit(false); i:=i>>1; end;
i:=y+zkwc; j:=row-x; while i>0 do begin if (tc1[i]>=x)or(tc2[i]>j) then exit(false); i:=i>>1; end;
exit(true);
end;
 
procedure mark(x,y:longint);
var l,r,k:longint;
begin
l:=x+zkwr; r:=row+zkwr+1; k:=y-1; while l xor r<>1 do begin
        if (l and 1=0)and(tr1[l xor 1]<k) then tr1[l xor 1]:=k;
        if (r and 1=1)and(tr1[r xor 1]<k) then tr1[r xor 1]:=k;
        l:=l>>1; r:=r>>1;
end;
l:=y+zkwc; r:=col+zkwc+1; k:=x-1; while l xor r<>1 do begin
        if (l and 1=0)and(tc1[l xor 1]<k) then tc1[l xor 1]:=k;
        if (r and 1=1)and(tc1[r xor 1]<k) then tc1[r xor 1]:=k;
        l:=l>>1; r:=r>>1;
end;
l:=zkwr; r:=x+zkwr; k:=col-y; while l xor r<>1 do begin
        if (l and 1=0)and(tr2[l xor 1]<k) then tr2[l xor 1]:=k;
        if (r and 1=1)and(tr2[r xor 1]<k) then tr2[r xor 1]:=k;
        l:=l>>1; r:=r>>1;
end;
l:=zkwc; r:=y+zkwc; k:=row-x; while l xor r<>1 do begin
        if (l and 1=0)and(tc2[l xor 1]<k) then tc2[l xor 1]:=k;
        if (r and 1=1)and(tc2[r xor 1]<k) then tc2[r xor 1]:=k;
        l:=l>>1; r:=r>>1;
end;
end;
 
procedure work;
var i,j,k,x,y:longint;
begin fillchar(a,sizeof(a),0);
zkwr:=1; while zkwr<row+2 do zkwr:=zkwr<<1; fillchar(tr1,sizeof(tr1),0); fillchar(tr2,sizeof(tr2),0);
zkwc:=1; while zkwc<col+2 do zkwc:=zkwc<<1; fillchar(tc1,sizeof(tc1),0); fillchar(tc2,sizeof(tc2),0);
for i:=1 to n do begin x:=(p[i]>>16)and mask; y:=p[i]and mask;
        if flag(x,y) then begin inc(a[0]); a[a[0]]:=i; mark(x,y); end;
end; write(a[1]); for i:=2 to a[0] do write(' ',a[i]); writeln;
end;
 
begin
init;
work;
end.

{$INLINE ON}
program bzoj3672;

type point=record x,y:int64; end;
     tedge=record n,next:longint; end;
     pnode=^tnode;
     tnode=record
        v,e:point;
        p:longint;
        l,r:pnode;
     end;

const maxn=200017;
      maxm=200017;
      maxint=longint($3f3f3f3f);
      eps=1e-9;
      nuv:point=(x:-1;y:-1);
      nev:point=(x:0;y:0);

var g,fa,anc,q,size,sons:array[0..maxn] of longint;
    a,b,f,dr,lim:array[0..maxn] of int64;
    mem:array[0..maxm] of tedge;
    flag:array[0..maxn] of boolean;
    n,memsize,casetype,frt,rer:longint;
    treap,null:pnode;

operator <(a,b:point) c:boolean; inline; begin exit((a.x<b.x)or((a.x=b.x)and(a.y<b.y))); end;
operator -(a,b:point) c:point; inline; begin c.x:=a.x-b.x; c.y:=a.y-b.y; end;
operator *(a,b:point) c:extended; inline; begin exit(extended(a.x)*b.y-extended(b.x)*a.y); end;
operator =(a,b:point) c:boolean; inline; begin exit((a.x=b.x)and(a.y=b.y)); end;

function min(i,j:int64):int64; inline; begin if i<j then exit(i) else exit(j); end;
function max(i,j:int64):int64; inline; begin if i>j then exit(i) else exit(j); end;

function sgn(r:extended):longint; inline;                begin
if r<-eps then exit(-1); if r>eps then exit(1); exit(0); end;

procedure insnbs(u,v:longint); inline;                                          begin
inc(memsize); mem[memsize].n:=v; mem[memsize].next:=g[u];  g[u]:=memsize;       end;

procedure treap_init;                                                                           begin
new(null); with null^ do begin v.x:=-1; v.y:=-1; p:=maxint; l:=null; r:=null; end; treap:=null; end;

procedure lrot(var i:pnode); inline; var j:pnode;
begin j:=i^.r; i^.r:=j^.l; j^.l:=i; i:=j; end;

procedure rrot(var i:pnode); inline; var j:pnode;
begin j:=i^.l; i^.l:=j^.r; j^.r:=i; i:=j; end;

procedure insert(var i:pnode;j:point);
begin
if i=null then begin
        new(i); with i^ do begin
                v:=j; p:=random(maxint); e:=nev; l:=null; r:=null;
        end;
end else if j<i^.v then begin
        insert(i^.l,j); if i^.l^.p<i^.p then rrot(i);
end else begin
        insert(i^.r,j); if i^.r^.p<i^.p then lrot(i);
end;
end;

procedure delete(var i:pnode;j:point);
begin
if j=i^.v then
        if i^.l=null then i:=i^.r
        else if i^.r=null then i:=i^.l
        else if i^.l^.p<i^.r^.p then begin
                rrot(i); delete(i^.r,j);
        end else begin
                lrot(i); delete(i^.l,j);
        end
else if j<i^.v then delete(i^.l,j) else delete(i^.r,j);
end;

function prev(i:pnode;j:point):pnode; inline;
begin
prev:=null; while i<>null do
        if not(i^.v<j) then i:=i^.l
        else begin prev:=i; i:=i^.r; end;
end;

function next(i:pnode;j:point):pnode; inline;
begin
next:=null; while i<>null do
        if (i^.v<j)or(i^.v=j) then i:=i^.r
        else begin next:=i; i:=i^.l; end;
end;

procedure update(i:point);
var t1,t2:pnode;
begin
t1:=treap; t2:=next(treap,i); while t1^.v<>i do
        if i<t1^.v then t1:=t1^.l else t1:=t1^.r;
if (t2=null)or(t1=null) then t1^.e:=nev else t1^.e:=t2^.v-t1^.v;
end;

procedure addpoint(a:point);
var rp,lp,np:point;
begin
lp:=prev(treap,a)^.v; if lp=nuv then begin
        rp:=next(treap,a)^.v; while true do begin
                np:=next(treap,rp)^.v; if np=nuv then break;
                if sgn((rp-a)*(np-a))>=0 then begin
                        delete(treap,rp); rp:=np;
                end else break;
        end; insert(treap,a); update(a); exit;
end;
rp:=next(treap,a)^.v; if rp=nuv then begin
        lp:=prev(treap,a)^.v; while true do begin
                np:=prev(treap,lp)^.v; if np=nuv then break;
                if sgn((lp-a)*(np-a))<=0 then begin
                        delete(treap,lp); lp:=np;
                end else break;
        end; insert(treap,a); if lp<>nuv then update(lp); exit;
end;
if sgn((a-lp)*(rp-lp))>=0 then exit;
while true do begin
        np:=prev(treap,lp)^.v; if np=nuv then break;
        if sgn((a-lp)*(np-lp))>=0 then begin
                delete(treap,lp); lp:=np;
        end else break;
end;
while true do begin
        np:=next(treap,rp)^.v; if np=nuv then break;
        if sgn((a-rp)*(np-rp))<=0 then begin
                delete(treap,rp); rp:=np;
        end else break;
end; insert(treap,a);
update(a); update(prev(treap,a)^.v);
end;

function tanpoint(a:point):point;
var t1:pnode;
begin
tanpoint.x:=0; tanpoint.y:=0;
if treap=null then begin tanpoint.x:=maxint; exit; end;
t1:=treap; while t1<>null do begin
        if sgn(t1^.e*a)<0 then t1:=t1^.r
        else begin tanpoint:=t1^.v; t1:=t1^.l; end;
end;
end;

function centre(root:longint):longint;
var i,j,head,tail,t1,ans:longint;
begin
frt:=0; rer:=1; q[1]:=root; while frt<rer do begin
        inc(frt); head:=q[frt]; t1:=g[head];
        while t1<>0 do begin tail:=mem[t1].n;
                if not flag[tail] then begin
                        inc(rer); q[rer]:=tail;
                end; t1:=mem[t1].next;
        end; size[head]:=0; sons[head]:=0;
end; ans:=maxint; for i:=rer downto 1 do begin
        j:=q[i]; inc(size[j]); sons[fa[j]]:=max(sons[fa[j]],size[j]);
        t1:=max(sons[j],rer-size[j]); if t1<ans then begin
                ans:=t1; centre:=j;
        end; inc(size[fa[j]],size[j]);
end;
end;

procedure qsort(l,r:longint);
var i,j,k,o:longint;
begin
i:=l; j:=r; k:=q[l+random(r-l+1)];
repeat
        while lim[q[i]]>lim[k] do inc(i);
        while lim[q[j]]<lim[k] do dec(j);
        if i<=j then begin
                o:=q[i]; q[i]:=q[j]; q[j]:=o;
                inc(i); dec(j);
        end;
until i>j;
if i<r then qsort(i,r);
if j>l then qsort(l,j);
end;

procedure update(u,root:longint);
var i,j,ac,head,tail,t1:longint;
    tp:point;
begin
frt:=0; rer:=1; q[1]:=u; while frt<rer do begin
        inc(frt); head:=q[frt]; t1:=g[head];
        while t1<>0 do begin tail:=mem[t1].n;
                if not flag[tail] then begin
                        inc(rer); q[rer]:=tail;
                end; t1:=mem[t1].next;
        end;
end; qsort(1,rer); treap:=null;
ac:=0; head:=u; while head<>root do begin
        head:=fa[head]; inc(ac); anc[ac]:=head;
end; if ac>0 then begin
        j:=1; for i:=1 to rer do begin u:=q[i];
                while (j<=ac)and(dr[anc[j]]>=lim[u]) do begin
                        tp.x:=f[anc[j]]; tp.y:=dr[anc[j]]; addpoint(tp); inc(j);
                end; if j>1 then begin
                        tp.x:=a[u]; tp.y:=1; tp:=tanpoint(tp);
                        f[u]:=min(f[u],dr[u]*a[u]+b[u]+tp.x-a[u]*tp.y);
                end;
        end;
end else begin
        for i:=1 to rer do begin u:=q[i];
                if dr[root]>=lim[u] then
                        f[u]:=min(f[u],dr[u]*a[u]+b[u]+f[root]-a[u]*dr[root]);
        end;
end;
end;

procedure init;
var i,head,t1:longint;
begin
fillchar(g,sizeof(g),0); memsize:=1;
readln(n,casetype); for i:=2 to n do begin
        readln(fa[i],dr[i],a[i],b[i],lim[i]); insnbs(fa[i],i);
end; frt:=0; rer:=1; q[1]:=1; while frt<rer do begin
        inc(frt); head:=q[frt]; inc(dr[head],dr[fa[head]]);
        t1:=g[head]; while t1<>0 do begin
                inc(rer); q[rer]:=mem[t1].n; t1:=mem[t1].next;
        end; lim[head]:=dr[head]-lim[head];
end; fillchar(flag,sizeof(flag),0); fillchar(f,sizeof(f),$3f); f[1]:=0;
end;

procedure work(root:longint);
var u,t1:longint;
begin
u:=centre(root); flag[u]:=true;
if u<>root then begin
        work(root); update(u,root); work(u);
end else begin
        update(u,root); t1:=g[u]; while t1<>0 do begin
                if not flag[mem[t1].n] then work(mem[t1].n);
                t1:=mem[t1].next;
        end;
end;
end;

procedure answer; var i:longint;
begin for i:=2 to n do writeln(f[i]); end;

begin
treap_init;
init;
work(1);
answer;
end.