平衡树系列终于完结，撒花
裸的树套树，扔代码跑
const mo=;
var w,b,s,key,fa:array[..] of longint;
son:array[..,..] of longint;
a,root:array[..*] of longint;
i,n,m,x,y,k,ch,ans,t:longint; function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; procedure open(x:longint);
begin
inc(t);
b[t]:=x;
w[t]:=; s[t]:=;
key[t]:=trunc(random*mo)+;
end; procedure update(x:longint);
begin
s[x]:=s[son[x,]]+s[son[x,]]+w[x];
end; procedure rotate(i,x,w:longint);
var y:longint;
begin
y:=fa[x];
if fa[y]<> then
begin
if son[fa[y],]=y then son[fa[y],]:=x
else son[fa[y],]:=x;
end
else root[i]:=x;
fa[x]:=fa[y];
son[y,-w]:=son[x,w];
if son[x,w]<> then fa[son[x,w]]:=y;
son[x,w]:=y;
fa[y]:=x;
update(y);
update(x);
end; procedure up(i,x:longint);
var y:longint;
begin
y:=fa[x];
while (y<>) and (key[y]>key[x]) do
begin
if son[y,]=x then rotate(i,x,)
else rotate(i,x,);
y:=fa[x];
end;
end; procedure add(i,x:longint);
var p:longint;
begin
if root[i]= then
begin
open(x);
root[i]:=t;
end
else begin
p:=root[i];
repeat
inc(s[p]);
if b[p]=x then
begin
inc(w[p]);
exit;
end
else if b[p]>x then
begin
if son[p,]= then break;
p:=son[p,];
end
else begin
if son[p,]= then break;
p:=son[p,];
end;
until false;
open(x);
fa[t]:=p;
if b[p]>x then son[p,]:=t else son[p,]:=t;
up(i,t);
end;
end; procedure sift(i,x:longint);
var j1,j2:longint;
begin
repeat
j1:=son[x,]; j2:=son[x,];
if j1+j2= then break;
if (j2<>) and ((key[j1]>key[j2]) or (j1=)) then
begin
rotate(i,j2,);
dec(s[j2]);
end
else begin
rotate(i,j1,);
dec(s[j1]);
end;
until false;
if son[fa[x],]=x then son[fa[x],]:= else son[fa[x],]:=;
fa[x]:=; w[x]:=; s[x]:=;
end; procedure del(i,x:longint);
var p:longint;
begin
p:=root[i];
repeat
dec(s[p]);
if b[p]=x then
begin
if w[p]= then sift(i,p)
else dec(w[p]);
break;
end
else if b[p]>x then p:=son[p,]
else p:=son[p,];
until false;
end; procedure build(i,l,r,x:longint);
var m:longint;
begin
add(i,a[x]);
if l<>r then
begin
m:=(l+r) shr ;
if x<=m then build(i*,l,m,x)
else build(i*+,m+,r,x);
end;
end; procedure change(i,l,r,x,y:longint);
var m:longint;
begin
add(i,y);
del(i,a[x]);
if l<>r then
begin
m:=(l+r) shr ;
if x<=m then change(i*,l,m,x,y)
else change(i*+,m+,r,x,y);
end;
end; function rank(i,x:longint):longint;
var p:longint;
begin
p:=root[i];
rank:=;
while p<> do
begin
if b[p]=x then
begin
rank:=rank+s[son[p,]];
break;
end
else if b[p]>x then p:=son[p,]
else begin
rank:=rank+s[son[p,]]+w[p];
p:=son[p,];
end;
end;
end; procedure getrank(i,l,r,k:longint);
var m:longint;
begin
if (x<=l) and (y>=r) then ans:=ans+rank(i,k)
else begin
m:=(l+r) shr ;
if x<=m then getrank(i*,l,m,k);
if y>m then getrank(i*+,m+,r,k);
end;
end; function what(k:longint):longint;
var l,r,m:longint;
begin
l:=;
r:=;
what:=;
while l<=r do
begin
m:=(l+r) shr ;
ans:=; getrank(,,n,m);
if ans<=k then
begin
what:=m;
l:=m+;
end
else r:=m-;
end;
end; procedure pre(i,x:longint);
var p:longint;
begin
p:=root[i];
while p<> do
begin
if b[p]>=x then p:=son[p,]
else begin
ans:=max(ans,b[p]);
p:=son[p,];
end;
end;
end; procedure suffix(i,x:longint);
var p:longint;
begin
p:=root[i];
while p<> do
begin
if b[p]<=x then p:=son[p,]
else begin
ans:=min(ans,b[p]);
p:=son[p,];
end;
end;
end; procedure askpre(i,l,r:longint);
var m:longint;
begin
if (x<=l) and (y>=r) then pre(i,k)
else begin
m:=(l+r) shr ;
if x<=m then askpre(i*,l,m);
if y>m then askpre(i*+,m+,r);
end;
end; procedure asksuf(i,l,r:longint);
var m:longint;
begin
if (x<=l) and (y>=r) then suffix(i,k)
else begin
m:=(l+r) shr ;
if x<=m then asksuf(i*,l,m);
if y>m then asksuf(i*+,m+,r);
end;
end; begin
randomize;
readln(n,m);
for i:= to n do
read(a[i]);
for i:= to n do
build(,,n,i);
for i:= to m do
begin
read(ch);
if ch= then
begin
readln(x,y,k);
ans:=; getrank(,,n,k);
writeln(ans+);
end
else if ch= then
begin
readln(x,y,k);
writeln(what(k-));
end
else if ch= then
begin
readln(x,k);
change(,,n,x,k);
a[x]:=k;
end
else if ch= then
begin
readln(x,y,k);
ans:=; askpre(,,n);
writeln(ans);
end
else if ch= then
begin
readln(x,y,k);
ans:=; asksuf(,,n);
writeln(ans);
end;
end;
end.