树套树是我写到至今最DT的数据库结构了吧。。。
【BZOJ3196】【Tyvj 1730】二逼平衡树
线段树套TREAP，nlog3n
program p3196;
type
tree=record
l,r,w,f,size:longint;
end;
var
t:array[0..4000000] of tree;
x,root:array[0..500000] of longint;
i,j,n,m,len,ans,l,r,mid,k1,k2,k3,k4,k5,k6:longint;
ch:char;
function min(k1,k2:longint):longint;
begin
if k1<k2 then exit(k1) else exit(k2);
end;
function max(k1,k2:longint):longint;
begin
if k1<k2 then exit(k2) else exit(k1);
end;
procedure zig(pf,f,k:longint);
begin
if t[pf].l=f then t[pf].l:=k else if t[pf].r=f then t[pf].r:=k;
t[f].l:=t[k].r; t[k].r:=f; t[f].size:=t[t[f].l].size+t[t[f].r].size+1;
t[k].size:=t[t[k].l].size+t[t[k].r].size+1;
end;
procedure zag(pf,f,k:longint);
begin
if t[pf].l=f then t[pf].l:=k else if t[pf].r=f then t[pf].r:=k;
t[f].r:=t[k].l; t[k].l:=f; t[f].size:=t[t[f].l].size+t[t[f].r].size+1;
t[k].size:=t[t[k].l].size+t[t[k].r].size+1;
end;
procedure insert(f,k1,k2:longint);
begin
inc(t[k1].size);
if t[k1].w>t[k2].w then begin
if t[k1].l=0 then t[k1].l:=k2 else insert(k1,t[k1].l,k2);
if t[k1].f<t[k2].f then zig(f,k1,k2);
end else begin
if t[k1].r=0 then t[k1].r:=k2 else insert(k1,t[k1].r,k2);
if t[k1].f<t[k2].f then zag(f,k1,k2);
end;
end;
procedure buildtree(k1,k2,k3:longint);
var
now,i,j:longint;
begin
root[k1]:=len+1; now:=len-k2+1; len:=len+k3-k2+1;
for i:=k2 to k3 do begin
t[i+now].w:=x[i]; t[i+now].size:=1; t[i+now].f:=random(1000000);
if i<>k2 then begin
insert(0,root[k1],i+now);
if (t[i+now].l=root[k1]) or (t[i+now].r=root[k1]) then root[k1]:=i+now;
end;
end;
if k2<>k3 then begin
buildtree(k1*2,k2,(k2+k3) shr 1);
buildtree(k1*2+1,(k2+k3) shr 1+1,k3);
end;
end;
function findallnum(k1,k2:longint):longint;
begin
if k1=0 then exit(0);
if k2<t[k1].w then exit(findallnum(t[k1].l,k2));
exit(findallnum(t[k1].r,k2)+1+t[t[k1].l].size);
end;
function pd(k1,k2,k3,k4,k5,k6:longint):longint;
var
k:longint;
begin
if (k2>k5) or (k3<k4) then exit(0);
if (k2>=k4) and (k3<=k5) then exit(findallnum(root[k1],k6));
exit(pd(k1*2,k2,(k2+k3) shr 1,k4,k5,k6)+pd(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5,k6));
end;
function findwhere(k,k1,k2,f:longint):longint;
var
k3,k4:longint;
begin
if t[k1].w=k2 then begin
while true do begin
if t[k1].l=0 then begin
if f=0 then root[k]:=t[k1].r else begin
if k1=t[f].l then t[f].l:=t[k1].r else t[f].r:=t[k1].r;
end;
t[k1].r:=0;
exit(k1);
end else if t[k1].r=0 then begin
if f=0 then root[k]:=t[k1].l else begin
if k1=t[f].l then t[f].l:=t[k1].l else t[f].r:=t[k1].l;
end;
t[k1].l:=0;
exit(k1);
end else begin
k3:=f;
if t[t[k1].l].f>t[t[k1].r].f then begin f:=t[k1].l; zig(k3,k1,t[k1].l); end else begin f:=t[k1].r; zag(k3,k1,t[k1].r); end;
if k3=0 then root[k]:=f;
dec(t[f].size);
end;
end;
end;
dec(t[k1].size);
if t[k1].w>k2 then exit(findwhere(k,t[k1].l,k2,k1)) else exit(findwhere(k,t[k1].r,k2,k1));
end;
procedure change(k1,k2,k3,k4,k6,k5:longint);
var
k:longint;
begin
if (k2>k4) or (k3<k4) then exit;
if (k2=k3) then begin
t[root[k1]].w:=k5; exit;
end;
k:=findwhere(k1,root[k1],k6,0); t[k].size:=1;
t[k].w:=k5; insert(0,root[k1],k);
if (t[k].l=root[k1]) or (t[k].r=root[k1]) then root[k1]:=k;
change(k1*2,k2,(k2+k3) shr 1,k4,k6,k5);
change(k1*2+1,(k2+k3) shr 1+1,k3,k4,k6,k5);
end;
function findnum(k1,k2,k3,k4,k5,k6:longint):longint;
begin
if (k2>k5) or (k3<k4) then exit(0);
if (k2>=k4) and (k3<=k5) then exit(findallnum(root[k1],k6));
exit(findnum(k1*2,k2,(k2+k3) shr 1,k4,k5,k6)+findnum(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5,k6));
end;
function findlesss(k1,k2:longint):longint;
begin
if k1=0 then exit(-maxlongint);
if k2<=t[k1].w then exit(findlesss(t[k1].l,k2));
exit(max(findlesss(t[k1].r,k2),t[k1].w));
end;
function findmore(k1,k2:longint):longint;
begin
if k1=0 then exit(maxlongint);
if k2>=t[k1].w then exit(findmore(t[k1].r,k2));
exit(min(findmore(t[k1].l,k2),t[k1].w));
end;
function findmax(k1,k2,k3,k4,k5,k6:longint):longint;
begin
if (k2>k5) or (k3<k4) then exit(-maxlongint);
if (k2>=k4) and (k3<=k5) then {begin
writeln(k2,' ',k3,' ',k4,' ',k5,' ',k6,' ',findlesss(root[k1],k6));}
exit(findlesss(root[k1],k6));
{end;}
exit(max(findmax(k1*2,k2,(k2+k3) shr 1,k4,k5,k6),findmax(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5,k6)));
end;
function findmin(k1,k2,k3,k4,k5,k6:longint):longint;
begin
if (k2>k5) or (k3<k4) then exit(maxlongint);
if (k2>=k4) and (k3<=k5) then exit(findmore(root[k1],k6));
exit(min(findmin(k1*2,k2,(k2+k3) shr 1,k4,k5,k6),findmin(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5,k6)));
end;
begin
readln(n,m);
for i:=1 to n do read(x[i]); readln;
len:=0; buildtree(1,1,n);
for i:=1 to m do begin
read(k6);
if k6=2 then begin
readln(k1,k2,k3);
l:=0; r:=1000000001;
while l<r do begin
mid:=(l+r) shr 1; k4:=pd(1,1,n,k1,k2,mid);
if k4>=k3 then begin
ans:=mid; r:=mid;
end else l:=mid+1;
end;
writeln(ans);
end else if k6=3 then begin
readln(k1,k2);
change(1,1,n,k1,x[k1],k2);
x[k1]:=k2;
end else if k6=1 then begin
readln(k1,k2,k3);
writeln(findnum(1,1,n,k1,k2,k3-1)+1);
end else if k6=4 then begin
readln(k1,k2,k3);
writeln(findmax(1,1,n,k1,k2,k3));
end else if k6=5 then begin
readln(k1,k2,k3);
writeln(findmin(1,1,n,k1,k2,k3));
end;
end;
end.
【BZOJ2141】排队
用树套树来维护逆序对个数。挺巧妙的。nlog2n
program p2141;
type
tree=record
father,l,r,w,size:longint;
end;
var
t:array[0..2000000] of tree;
w,root,x,y:array[0..3000000] of longint;
i,j,n,m,len,k1,k2:longint;
tot:int64;
procedure zig(k:longint);
var
f:longint;
begin
f:=t[k].father; t[k].father:=t[f].father;
if f=t[t[f].father].l then t[t[f].father].l:=k else if f=t[t[f].father].r then t[t[f].father].r:=k;
t[f].l:=t[k].r; t[t[f].l].father:=f; t[k].r:=f; t[f].father:=k;
t[f].size:=t[t[f].l].size+t[t[f].r].size+1; t[k].size:=t[t[k].l].size+t[t[k].r].size+1;
end;
procedure zag(k:longint);
var
f:longint;
begin
f:=t[k].father; t[k].father:=t[f].father;
if f=t[t[f].father].l then t[t[f].father].l:=k else if f=t[t[f].father].r then t[t[f].father].r:=k;
t[f].r:=t[k].l; t[t[f].r].father:=f; t[k].l:=f; t[f].father:=k;
t[f].size:=t[t[f].l].size+t[t[f].r].size+1; t[k].size:=t[t[k].l].size+t[t[k].r].size+1;
end;
procedure up(k,k1:longint);
var
f1,f2:longint;
begin
while (k<>k1) do begin
f1:=t[k].father; f2:=t[f1].father;
if f1=k1 then begin
if k=t[f1].l then zig(k) else zag(k);
exit;
end;
if k=t[f1].l then begin
if f1=t[f2].l then begin zig(f1); zig(k); end else begin zig(k); zag(k); end;
end else if f1=t[f2].l then begin zag(k); zig(k); end else begin zag(f1); zag(k); end;
if f2=k1 then exit;
end;
end;
procedure insert(k1,k2:longint);
begin
inc(t[k1].size);
if t[k2].w>t[k1].w then begin
if t[k1].r=0 then begin t[k1].r:=k2; t[k2].father:=k1; end else insert(t[k1].r,k2);
end else begin
if t[k1].l=0 then begin t[k1].l:=k2; t[k2].father:=k1; end else insert(t[k1].l,k2);
end;
end;
procedure buildtree(k1,k2,k3:longint);
var
now,i,j:longint;
begin
inc(len); root[k1]:=len; now:=len-k2; len:=len+k3-k2;
for i:=k2 to k3 do begin
t[now+i].w:=w[i]; t[now+i].size:=1;
if i<>k2 then begin
insert(root[k1],now+i);
{if k1=1 then begin
writeln(root[k1]);
for j:=1 to n do
writeln(t[j].l,' ',t[j].r,' ',t[j].size,' ',t[j].father,' ',t[j].w);
readln;
end;}
up(now+i,root[k1]); root[k1]:=now+i;
end;
end;
if k2<>k3 then begin
buildtree(k1*2,k2,(k2+k3) shr 1);
buildtree(k1*2+1,(k2+k3) shr 1+1,k3);
end;
end;
procedure sort(first,en:longint);
var
i,j:longint;
begin
i:=first; j:=en; x[0]:=x[i];
while i<j do begin
while (i<j) and ((w[x[j]]>w[x[0]]) or ((w[x[j]]=w[x[0]]) and (x[j]>=x[0]))) do dec(j);
if i<j then x[i]:=x[j];
while (i<j) and ((w[x[i]]<w[x[0]]) or ((w[x[i]]=w[x[0]]) and (x[i]<x[0]))) do inc(i);
if i<j then x[j]:=x[i];
end;
x[i]:=x[0];
if i>first+1 then sort(first,i-1);
if i<en-1 then sort(i+1,en);
end;
function lowbit(k:longint):longint;
begin
exit(k and (-k));
end;
procedure addin(k:longint);
var
i:longint;
begin
i:=k;
while i<=n do begin
x[i]:=x[i]+1;
i:=i+lowbit(i);
end;
end;
function addup(k:longint):longint;
var
i,j:longint;
begin
j:=0; i:=k;
while i>0 do begin
j:=j+x[i];
i:=i-lowbit(i);
end;
exit(j);
end;
procedure swap(var k1,k2:longint);
var
i:longint;
begin
i:=k1; k1:=k2; k2:=i;
end;
function findallless(k1,k2:longint):longint;
begin
if k1=0 then exit(0);
if t[k1].w>k2 then exit(findallless(t[k1].l,k2));
exit(findallless(t[k1].r,k2)+t[t[k1].l].size+1);
end;
function findallmore(k1,k2:longint):longint;
begin
if k1=0 then exit(0);
if t[k1].w<k2 then exit(findallmore(t[k1].r,k2));
exit(findallmore(t[k1].l,k2)+t[t[k1].r].size+1);
end;
function findless(k1,k2,k3,k4,k5,k6:longint):longint;
begin
if (k2>k5) or (k3<k4) then exit(0);
if (k2>=k4) and (k3<=k5) then exit(findallless(root[k1],k6));
exit(findless(k1*2,k2,(k2+k3) shr 1,k4,k5,k6)+findless(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5,k6));
end;
function findmore(k1,k2,k3,k4,k5,k6:longint):longint;
begin
if (k2>k5) or (k3<k4) then exit(0);
if (k2>=k4) and (k3<=k5) then exit(findallmore(root[k1],k6));
exit(findmore(k1*2,k2,(k2+k3) shr 1,k4,k5,k6)+findmore(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5,k6));
end;
function findwhere(k1,k2:longint):longint;
begin
if t[k1].w=k2 then exit(k1);
if t[k1].w<k2 then exit(findwhere(t[k1].r,k2));
exit(findwhere(t[k1].l,k2));
end;
function findleft(k:longint):longint;
begin
while t[k].l<>0 do k:=t[k].l;
exit(k);
end;
function findright(k:longint):longint;
begin
while t[k].r<>0 do k:=t[k].r;
exit(k);
end;
procedure change(k1,k2,k3,k4,k5:longint);
var
k,i,j,k6,k7:longint;
begin
if (k2>k4) or (k3<k4) then exit;
if (k2=k3) then begin
t[root[k1]].w:=k5; exit;
end;
k:=findwhere(root[k1],w[k4]); up(k,root[k1]); root[k1]:=k;
if t[k].l=0 then begin
t[k].size:=1; t[t[k].r].father:=0; root[k1]:=t[k].r; t[k].r:=0;
end else if t[k].r=0 then begin
t[k].size:=1; t[t[k].l].father:=0; root[k1]:=t[k].l; t[k].l:=0;
end else begin
k6:=findright(t[k].l); k7:=findleft(t[k].r);
up(k6,k); up(k7,t[k6].r); root[k1]:=k6; t[k7].l:=0;
dec(t[k7].size); dec(t[k6].size); t[k].father:=0;
end;
t[k].w:=k5; insert(root[k1],k);
change(k1*2,k2,(k2+k3) shr 1,k4,k5); change(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5);
end;
begin
{assign(input,'data.in'); reset(input);
assign(output,'dat1a.out'); rewrite(output);}
readln(n);
for i:=1 to n do read(w[i]);
len:=0;
fillchar(t,sizeof(t),0);
fillchar(root,sizeof(root),0);
buildtree(1,1,n);
for i:=1 to n do x[i]:=i;
sort(1,n);
for i:=1 to n do y[x[i]]:=i;
fillchar(x,sizeof(x),0);
for i:=n downto 1 do begin
tot:=tot+addup(y[i]-1);
addin(y[i]);
end;
writeln(tot);
readln(m);
{while true do begin
read(i); writeln(findmore(1,1,n,1,n,i)); writeln(findless(1,1,n,1,n,i)); end;}
for i:=1 to m do begin
{writeln(root[1]);}{
for j:=1 to n do
writeln(t[j].l,' ',t[j].r,' ',t[j].size,' ',t[j].father,' ',t[j].w);}
readln(k1,k2);
if w[k1]=w[k2] then begin writeln(tot); continue; end;
if k1>k2 then swap(k1,k2);
{ writeln(findmore(1,1,n,1,n,w[k1]+1),' ',findless(1,1,n,1,n,w[k1]-1),' ',findless(1,1,n,1,n,w[k2]-1),' ',findmore(1,1,n,1,n,w[k2]+1));
} if k1+1<>k2 then tot:=tot+findmore(1,1,n,k1+1,k2-1,w[k1]+1)-findless(1,1,n,k1+1,k2-1,w[k1]-1)+findless(1,1,n,k1+1,k2-1,w[k2]-1)-findmore(1,1,n,k1+1,k2-1,w[k2]+1);
if w[k1]<w[k2] then inc(tot) else dec(tot);
change(1,1,n,k1,w[k2]);
{for j:=1 to n do
writeln(t[j].l,' ',t[j].r,' ',t[j].size,' ',t[j].father,' ',t[j].w);}
change(1,1,n,k2,w[k1]);
swap(w[k1],w[k2]);
writeln(tot);
end;
end.
【BZOJ2120】数颜色
用颜色种类个数的SPLAY来维护同种颜色的下一只画笔的位置。用树套树来求解。nlog2n。据说树状数组套主席树也可以做，但我太弱了不会。
program p2120;
type
tree=record
l,r,father,w,size:longint;
end;
var
root,first:array[0..800000] of longint;
ro:array[0..2000000] of longint;
t:array[0..4000000] of tree;
w,x:array[0..20000] of longint;
i,j,n,m,k1,k2,len:longint;
ch:char;
procedure zig(k:longint);
var
f:longint;
begin
f:=t[k].father; t[k].father:=t[f].father;
if f=t[t[f].father].l then t[t[f].father].l:=k else if f=t[t[f].father].r then t[t[f].father].r:=k;
t[f].father:=k; t[f].l:=t[k].r; t[t[f].l].father:=f; t[k].r:=f;
t[f].size:=t[t[f].l].size+t[t[f].r].size+1; t[k].size:=t[t[k].l].size+t[t[k].r].size+1;
end;
procedure zag(k:longint);
var
f:longint;
begin
f:=t[k].father; t[k].father:=t[f].father;
if f=t[t[f].father].l then t[t[f].father].l:=k else if f=t[t[f].father].r then t[t[f].father].r:=k;
t[f].father:=k; t[f].r:=t[k].l; t[t[f].r].father:=f; t[k].l:=f;
t[f].size:=t[t[f].l].size+t[t[f].r].size+1; t[k].size:=t[t[k].l].size+t[t[k].r].size+1;
end;
procedure up(k1,k2:longint);
var
f1,f2:longint;
begin
while (k1<>k2) and (t[k1].father<>k2) do begin
f1:=t[k1].father; f2:=t[f1].father;
if f2=k2 then begin
if k1=t[f1].l then zig(k1) else zag(k1);
exit;
end;
if k1=t[f1].l then begin
if f1=t[f2].l then begin zig(f1); zig(k1); end else begin zig(k1); zag(k1); end;
end else if f1=t[f2].l then begin zag(k1); zig(k1); end else begin zag(f1); zag(k1); end;
end;
end;
procedure insert(k1,k2:longint);
begin
if k1=0 then exit;
inc(t[k1].size);
if t[k1].w<t[k2].w then begin
if t[k1].r=0 then begin t[k1].r:=k2; t[k2].father:=k1; end else insert(t[k1].r,k2);
end else if t[k1].l=0 then begin t[k1].l:=k2; t[k2].father:=k1; end else insert(t[k1].l,k2);
end;
function min(k1,k2:longint):longint;
begin
if k1<k2 then exit(k1) else exit(k2);
end;
function findless(k1,k2:longint):longint;
begin
if k1=0 then exit(maxlongint);
if t[k1].w<=k2 then exit(findless(t[k1].r,k2));
exit(min(findless(t[k1].l,k2),t[k1].w));
end;
procedure buildtree(k1,k2,k3:longint);
var
i,j,now:longint;
begin
now:=len-k2; root[k1]:=len; len:=len+k3-k2+1; first[k1]:=now;
for i:=k2 to k3 do begin
t[now+i].w:=x[i]; t[now+i].size:=1;
if i<>k2 then begin
insert(root[k1],now+i); up(now+i,0); root[k1]:=now+i;
end;
end;
if k2<>k3 then begin
buildtree(k1*2,k2,(k2+k3) shr 1);
buildtree(k1*2+1,(k2+k3) shr 1+1,k3);
end;
end;
procedure getchar(var ch:char);
begin
repeat
read(ch);
until(ch>='A') and (ch<='Z');
end;
function findbig(k1,k2:longint):longint;
begin
if k1=0 then exit(0);
if t[k1].w>k2 then exit(findbig(t[k1].l,k2)+1+t[t[k1].r].size);
exit(findbig(t[k1].r,k2));
end;
function findanswer(k1,k2,k3,k4,k5:longint):longint;
begin
if (k2>k5) or (k3<k4) then exit(0);
if (k2>=k4) and (k3<=k5) then exit(findbig(root[k1],k5));
exit(findanswer(k1*2,k2,(k2+k3) shr 1,k4,k5)+findanswer(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5));
end;
function findmorewhere(k1,k2:longint):longint;
var
k:longint;
begin
if k1=0 then exit(0);
if t[k1].w>=t[k2].w then exit(findmorewhere(t[k1].l,k2));
k:=findmorewhere(t[k1].r,k2);
if k=0 then exit(k1) else exit(k);
end;
function findleft(k:longint):longint;
begin
while t[k].l<>0 do k:=t[k].l;
exit(k);
end;
function findright(k:longint):longint;
begin
while t[k].r<>0 do k:=t[k].r;
exit(k);
end;
procedure delete(k1,k2:longint);
var
l,r:longint;
begin
up(k2,0); root[k1]:=k2;
if t[k2].l=0 then begin
t[t[k2].r].father:=0; t[k2].size:=1; root[k1]:=t[k2].r; t[k2].r:=0;
end else if t[k2].r=0 then begin
t[t[k2].l].father:=0; t[k2].size:=1; root[k1]:=t[k2].l; t[k2].l:=0;
end else begin
l:=findright(t[k2].l); r:=findleft(t[k2].r);
up(l,0); up(r,l); root[k1]:=l;
dec(t[l].size); dec(t[r].size);
t[r].l:=0; t[k2].father:=0;
end;
end;
procedure changetreew(k1,k2,k3:longint);
var
k:longint;
begin
k:=first[k1]+k2;
delete(k1,k); t[k].w:=k3;
insert(root[k1],k); up(k,0); root[k1]:=k;
end;
procedure changew(k1,k2,k3,k4,k5:longint);
begin
if (k2>k4) or (k3<k4) then exit;
changetreew(k1,k4,k5);
if k2=k3 then exit;
changew(k1*2,k2,(k2+k3) shr 1,k4,k5);
changew(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5);
end;
procedure changex(k,color:longint);
var
l,r:longint;
begin
up(k,0); ro[w[k]]:=k;
if t[k].l=0 then begin
t[t[k].r].father:=0; t[k].size:=1; ro[w[k]]:=t[k].r; t[k].r:=0;
end else if t[k].r=0 then begin
t[t[k].l].father:=0; t[k].size:=1; ro[w[k]]:=t[k].l;
l:=findright(t[k].l); x[l]:=n+1;
changew(1,1,n,l,n+1); t[k].l:=0;
end else begin
l:=findright(t[k].l); r:=findleft(t[k].r);
up(l,0); up(r,l); ro[w[k]]:=l;
dec(t[l].size); dec(t[r].size);
t[r].l:=0; t[k].father:=0;
x[l]:=r; changew(1,1,n,l,r);
end;
insert(ro[color],k); up(k,0); ro[color]:=k;
if t[k].l<>0 then begin
l:=findright(t[k].l); changew(1,1,n,k,x[l]); changew(1,1,n,l,k); x[k]:=x[l]; x[l]:=k;
end else if t[k].r<>0 then begin
r:=findleft(t[k].r); changew(1,1,n,k,r); x[k]:=r;
end else begin
x[k]:=n+1; changew(1,1,n,k,n+1);
end;
end;
begin
readln(n,m);
fillchar(root,sizeof(root),0);
fillchar(ro,sizeof(ro),0);
fillchar(t,sizeof(t),0);
for i:=1 to n do begin
read(w[i]);
t[i].w:=i; t[i].size:=1;
insert(ro[w[i]],i); up(i,0); ro[w[i]]:=i;
end;
for i:=1 to n do begin
up(i,0);
if t[i].r=0 then x[i]:=n+1 else x[i]:=findleft(t[i].r);
end;
len:=n+1;
buildtree(1,1,n);
for i:=1 to m do begin
{for j:=1 to n do writeln(x[j],' ',w[j]);
for j:=1 to 6 do writeln(ro[j]);
for j:=1 to n do writeln(j,' ',t[j].l,' ',t[j].r,' ',t[j].size,' ',t[j].w,' ',ro[w[j]]);
writeln;
for j:=1 to n*2 do writeln(first[j],' ',root[j]);
for j:=1+n to n*2 do writeln(j,' ',t[j].l,' ',t[j].r,' ',t[j].size,' ',t[j].w);
}getchar(ch);
if ch='Q' then begin
readln(k1,k2);
writeln(findanswer(1,1,n,k1,k2));
end else begin
readln(k1,k2);
if w[k1]=k2 then continue;
changex(k1,k2); w[k1]:=k2;
end;
end;
end.
，尼玛我这么弱还搞什么省选
，直接切腹自尽算了
。看着那么蓝名和1664的rating真是想一头撞死
。