树套树是我写到至今最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.
2019年2月17日 20:53
The definition of the programmer is taught for the students. All the issues of the program and best dissertation writing are inducted for the security of the norms and flaws of the people.