VIJOS P1665
By Prominences_CJOIER
LMD
区间第k值 带修改
题目大意：
一个长度为n的序列，支持两种操作：
1.输出[A, B]区间第k小的数(从小到大排序后第k个)
2.修改第I个数为W
格式
输入：
第一行两个整数N（1<=N<=50000),M(1<=M<=10000),表示有N个数，M个操作
第二行N个数A(1<=A<=1000000000)
以下M行，每行一个操作
Q i j k（查询中第k小的数）或 C i W(把第I个数改成W）
（N，M 可改为【1，100000】）
输出：
对于每个查询操作，输出每个查询结果。
思路：
求带修改的区间第k值有几种方法。可以分块，可以用线段树套平衡树，也可以用树状数组套主席树。我用的是树状数组套主席树。那么就来浅谈树状数组套主席树吧。
首先，主席树就相当于添加节点的线段树的历史版本。在不带修改的区间第k值中，我们是利用两棵树的前缀信息（T[1][l-1], T[1][r]），来查找区间第k值的。那么，要维护前缀信息，就可以用树状数组。
这里的树状数组，并不是专门开一个数组来记录，也并不是创建N个树状数组，只是利用树状数组的lowbit思想，把各历史版本的线段树联系起来。如图：
一个长度为n的序列，支持两种操作：
1.输出[A, B]区间第k小的数(从小到大排序后第k个)
2.修改第I个数为W
格式
输入：
第一行两个整数N（1<=N<=50000),M(1<=M<=10000),表示有N个数，M个操作
第二行N个数A(1<=A<=1000000000)
以下M行，每行一个操作
Q i j k（查询中第k小的数）或 C i W(把第I个数改成W）
（N，M 可改为【1，100000】）
输出：
对于每个查询操作，输出每个查询结果。
思路：
求带修改的区间第k值有几种方法。可以分块，可以用线段树套平衡树，也可以用树状数组套主席树。我用的是树状数组套主席树。那么就来浅谈树状数组套主席树吧。
首先，主席树就相当于添加节点的线段树的历史版本。在不带修改的区间第k值中，我们是利用两棵树的前缀信息（T[1][l-1], T[1][r]），来查找区间第k值的。那么，要维护前缀信息，就可以用树状数组。
这里的树状数组，并不是专门开一个数组来记录，也并不是创建N个树状数组，只是利用树状数组的lowbit思想，把各历史版本的线段树联系起来。如图：
如果A[i]表示添加了第i个数之后的线段树（存离散化后的值的大小，这些树的结构一样），那么，根据树状数组的思想，A[1]有的节点，A[2]也有，同时A[4],A[8]...都有，但是，A[3],A[5],A[6]...没有。根据不带修改的区间第k值，要求区间【L，R】的第k值，要用两个指针，分指T【1】【L-1】 & T【1】【R】，通过比较两节点左子树权值之差与k，决定是到左孩子还是右孩子。这里与那里差不多，只不过，要求的T【1】【L-1】的左子树权值，需要把与这个节点相关（通过lowbit联系）的节点线段树中的对应节点的左权值都加起来。求T【1】【R】的是一样的。再通过比较两差与k，便可以知道是到左孩子，还是右孩子了。
为了方便，可以先开两个数组，储存当前考察的一系列节点的地址，就可以直接算左权值之和。算完了之后，再遍历数组中的每个点，更新为这个点的左孩子或右孩子（具体要看左权值之差与k的大小比较情况）。要注意的是，如果当前点没有左儿子（或右儿子），那么就要给这个点赋值，存一个每个域都为0的点，这样就可以避免运行错误和重复计算某个节点。
修改的话，若要修改第i个数，那么就先修改树S【i】，再向上lowbit，把跟它有关的树都要修改。具体的修改方法，先把这个点从树中删掉，再把修改后的值加入树中。删除的时候要注意，如果是用动态指针，删完回溯的时候，把空节点删掉，节省空间。
大概就这样了～～
还有一个问题，就是，在最初建树的时候，是根据每个数的离散值来存入线段树的，在把修改后的数加入树的时候，因为你不知到它的离散值是多少，所以不能知道这个数应该存在哪里。因此，在离散之前，先把所有命令全部读完，把要修改的值存在原序列数组的后面（就接在第N个数之后），做个标记，然后一起排序，一起离散。建树的时候只要根据标记来判断该数是否为原序列中的数。但是，这样的话，如果多次对同一个数进行修改，那么，就会出现这个问题，在修改中的删除操作中，找不到这个点（因为它之前已经被删掉了！）。因此，在每次修改后，要把这个数的离散值改为修改后的数的离散值，这样，就跟这个数没有任何关系了。（一开始没发现这个问题，就调了很久。。。）
代码（在下的程序风格很丑，特别长，有废话，不够简洁，还请多多包涵！）：
program p1665;
type
wv2=^wv1; //线段树；
wv1=record
lw,w,rw,data:longint; //为了节省空间，线段的左右端点就用递归传值，不单独开域存了；
lc,rc:wv2;
end;
wv3=record
i,j,k:longint;
end;
wv4=record
data:longint;
bb:boolean; //标记，true为是原序列中的元素；
end;
var
n,m,i,j,k,l,o,xx,
wei,//原序列元素数量与修改数量之和；
delta,topl,topr,suml,sumr,num:longint;
tree,tl,tr:array[0..60000] of wv2;
a:array[1..200000] of wv4;//序列；
b,c:array[1..200000] of longint;//c存离散值；
ttt:array[1..10000] of wv3;//每个命令；
ch1:char;
j1:wv2;//上文所说的“每个域都为0的点”；
function lowbit(x:longint):longint;
begin
exit(x and (x xor (x-1)));
end;
procedure quick(q1,q2:longint);
var i,j,t:longint;x:wv4;
begin
i:=q1;j:=q2;x:=a[i];
while i<j do
begin
while (i<j) and (x.data<=a[j].data) do j:=j-1;
if i<j then begin a[i]:=a[j];t:=b[i];b[i]:=b[j];b[j]:=t;i:=i+1;end;
while (i<j) and (a[i].data<=x.data) do i:=i+1;
if i<j then begin a[j]:=a[i];t:=b[i];b[i]:=b[j];b[j]:=t;j:=j-1;end;
a[i]:=x;
end;
if i>q1+1 then quick(q1,i-1);
if j<q2-1 then quick(j+1,q2);
end;
procedure init;
begin
for i:=1 to n do begin read(a[i].data);b[i]:=i;a[i].bb:=true;end;readln;wei:=n;
for i:=1 to m do
begin
read(ch1);
if ch1='Q' then readln(ttt[i].i,ttt[i].j,ttt[i].k) else
begin
readln(ttt[i].i,ttt[i].j);ttt[i].k:=-maxlongint;
inc(wei);a[wei].data:=ttt[i].j;b[wei]:=wei;
a[wei].bb:=false;//设标记；
end;
end;
quick(1,wei);c[b[1]]:=1;
for i:=2 to wei do//离散；
if a[i].data<>a[i-1].data then c[b[i]]:=i
else c[b[i]]:=c[b[i-1]];
end;
procedure build(j:wv2;l,r,x:longint);
var mid:longint;j1:wv2;
begin
if l=r then
begin
inc(j^.w);j^.data:=x;exit;
end;
mid:=(l+r)>>1;
if x<=mid then
begin
if j^.lc=nil then
begin
new(j^.lc);j1:=j^.lc;
j1^.lw:=0;j1^.rw:=0;j1^.w:=0;j1^.lc:=nil;j1^.rc:=nil;
end;
inc(j^.lw);
build(j^.lc,l,mid,x);
end else
begin
if j^.rc=nil then
begin
new(j^.rc);j1:=j^.rc;
j1^.lw:=0;j1^.rw:=0;j1^.w:=0;j1^.lc:=nil;j1^.rc:=nil;
end;
inc(j^.rw);
build(j^.rc,mid+1,r,x);
end;
end;
procedure bbuuiilldd;//建树；
begin
for i:=0 to n do tree[i]:=nil;
j:=0;new(tree[j]);tree[j]^.w:=0;tree[j]^.lw:=0;tree[j]^.rw:=0;tree[j]^.lc:=nil;tree[j]^.rc:=nil;
for i:=1 to n do
begin
j:=i;
while j<=n do
begin
if tree[j]=nil then
begin
new(tree[j]);tree[j]^.w:=0;tree[j]^.lw:=0;tree[j]^.rw:=0;tree[j]^.lc:=nil;tree[j]^.rc:=nil;
end;
build(tree[j],1,wei,c[i]);
delta:=lowbit(j);
j:=j+delta;
end;
end;
end;
procedure delayyy(j:wv2;o,l,r:longint); //删除节点；
var
mid,yoki:longint;
begin
if l=r then
begin
j^.data:=0;dec(j^.w);
exit;
end;
mid:=(l+r)>>1;
if o<=mid then
begin
yoki:=1;dec(j^.lw);
delayyy(j^.lc,o,l,mid);
end else
begin
yoki:=2;dec(j^.rw);
delayyy(j^.rc,o,mid+1,r);
end;
if j^.lw=0 then j^.lc:=nil;
if j^.rw=0 then j^.rc:=nil;
end;
procedure prominences;
var
l,r,mid,
oy:longint;//差；
begin
num:=n;
for xx:=1 to m do
if ttt[xx].k<>-maxlongint then
begin
l:=1;r:=wei;
topl:=0;topr:=0;k:=ttt[xx].k;
i:=ttt[xx].i-1;
while i>0 do
begin
topl:=topl+1;tl[topl]:=tree[i];
i:=i-lowbit(i);
end;
i:=ttt[xx].j;
while i>0 do//找相关的节点；
begin
topr:=topr+1;tr[topr]:=tree[i];
i:=i-lowbit(i);
end;
while l<>r do
begin
mid:=(l+r)>>1;
suml:=0;sumr:=0;
for i:=1 to topl do suml:=suml+tl[i]^.lw; //求左权值之和；
for i:=1 to topr do sumr:=sumr+tr[i]^.lw;
oy:=sumr-suml;
if oy>=k then
begin
r:=mid;
for i:=1 to topl do if tl[i]^.lc<>nil then tl[i]:=tl[i]^.lc else tl[i]:=j1;
for i:=1 to topr do if tr[i]^.lc<>nil then tr[i]:=tr[i]^.lc else tr[i]:=j1;
end else
begin
l:=mid+1;k:=k-oy;
for i:=1 to topl do if tl[i]^.rc<>nil then tl[i]:=tl[i]^.rc else tl[i]:=j1;
for i:=1 to topr do if tr[i]^.rc<>nil then tr[i]:=tr[i]^.rc else tr[i]:=j1;
end;
end;
writeln(a[l].data);
end else
begin
i:=ttt[xx].i;k:=ttt[xx].j;
num:=num+1;
while i<=n do
begin
delayyy(tree[i],c[ttt[xx].i],1,wei);
build(tree[i],1,wei,c[num]);
i:=i+lowbit(i);
end;
c[ttt[xx].i]:=c[num];//别忘了这个！
end;
end;
{============================}
begin
readln(n,m);
new(j1);
with j1^ do
begin
lw:=0;rw:=0;w:=0;lc:=nil;rc:=nil;
end;
init;
bbuuiilldd;
prominences;
end.
为了方便，可以先开两个数组，储存当前考察的一系列节点的地址，就可以直接算左权值之和。算完了之后，再遍历数组中的每个点，更新为这个点的左孩子或右孩子（具体要看左权值之差与k的大小比较情况）。要注意的是，如果当前点没有左儿子（或右儿子），那么就要给这个点赋值，存一个每个域都为0的点，这样就可以避免运行错误和重复计算某个节点。
修改的话，若要修改第i个数，那么就先修改树S【i】，再向上lowbit，把跟它有关的树都要修改。具体的修改方法，先把这个点从树中删掉，再把修改后的值加入树中。删除的时候要注意，如果是用动态指针，删完回溯的时候，把空节点删掉，节省空间。
大概就这样了～～
还有一个问题，就是，在最初建树的时候，是根据每个数的离散值来存入线段树的，在把修改后的数加入树的时候，因为你不知到它的离散值是多少，所以不能知道这个数应该存在哪里。因此，在离散之前，先把所有命令全部读完，把要修改的值存在原序列数组的后面（就接在第N个数之后），做个标记，然后一起排序，一起离散。建树的时候只要根据标记来判断该数是否为原序列中的数。但是，这样的话，如果多次对同一个数进行修改，那么，就会出现这个问题，在修改中的删除操作中，找不到这个点（因为它之前已经被删掉了！）。因此，在每次修改后，要把这个数的离散值改为修改后的数的离散值，这样，就跟这个数没有任何关系了。（一开始没发现这个问题，就调了很久。。。）
代码（在下的程序风格很丑，特别长，有废话，不够简洁，还请多多包涵！）：
program p1665;
type
wv2=^wv1; //线段树；
wv1=record
lw,w,rw,data:longint; //为了节省空间，线段的左右端点就用递归传值，不单独开域存了；
lc,rc:wv2;
end;
wv3=record
i,j,k:longint;
end;
wv4=record
data:longint;
bb:boolean; //标记，true为是原序列中的元素；
end;
var
n,m,i,j,k,l,o,xx,
wei,//原序列元素数量与修改数量之和；
delta,topl,topr,suml,sumr,num:longint;
tree,tl,tr:array[0..60000] of wv2;
a:array[1..200000] of wv4;//序列；
b,c:array[1..200000] of longint;//c存离散值；
ttt:array[1..10000] of wv3;//每个命令；
ch1:char;
j1:wv2;//上文所说的“每个域都为0的点”；
function lowbit(x:longint):longint;
begin
exit(x and (x xor (x-1)));
end;
procedure quick(q1,q2:longint);
var i,j,t:longint;x:wv4;
begin
i:=q1;j:=q2;x:=a[i];
while i<j do
begin
while (i<j) and (x.data<=a[j].data) do j:=j-1;
if i<j then begin a[i]:=a[j];t:=b[i];b[i]:=b[j];b[j]:=t;i:=i+1;end;
while (i<j) and (a[i].data<=x.data) do i:=i+1;
if i<j then begin a[j]:=a[i];t:=b[i];b[i]:=b[j];b[j]:=t;j:=j-1;end;
a[i]:=x;
end;
if i>q1+1 then quick(q1,i-1);
if j<q2-1 then quick(j+1,q2);
end;
procedure init;
begin
for i:=1 to n do begin read(a[i].data);b[i]:=i;a[i].bb:=true;end;readln;wei:=n;
for i:=1 to m do
begin
read(ch1);
if ch1='Q' then readln(ttt[i].i,ttt[i].j,ttt[i].k) else
begin
readln(ttt[i].i,ttt[i].j);ttt[i].k:=-maxlongint;
inc(wei);a[wei].data:=ttt[i].j;b[wei]:=wei;
a[wei].bb:=false;//设标记；
end;
end;
quick(1,wei);c[b[1]]:=1;
for i:=2 to wei do//离散；
if a[i].data<>a[i-1].data then c[b[i]]:=i
else c[b[i]]:=c[b[i-1]];
end;
procedure build(j:wv2;l,r,x:longint);
var mid:longint;j1:wv2;
begin
if l=r then
begin
inc(j^.w);j^.data:=x;exit;
end;
mid:=(l+r)>>1;
if x<=mid then
begin
if j^.lc=nil then
begin
new(j^.lc);j1:=j^.lc;
j1^.lw:=0;j1^.rw:=0;j1^.w:=0;j1^.lc:=nil;j1^.rc:=nil;
end;
inc(j^.lw);
build(j^.lc,l,mid,x);
end else
begin
if j^.rc=nil then
begin
new(j^.rc);j1:=j^.rc;
j1^.lw:=0;j1^.rw:=0;j1^.w:=0;j1^.lc:=nil;j1^.rc:=nil;
end;
inc(j^.rw);
build(j^.rc,mid+1,r,x);
end;
end;
procedure bbuuiilldd;//建树；
begin
for i:=0 to n do tree[i]:=nil;
j:=0;new(tree[j]);tree[j]^.w:=0;tree[j]^.lw:=0;tree[j]^.rw:=0;tree[j]^.lc:=nil;tree[j]^.rc:=nil;
for i:=1 to n do
begin
j:=i;
while j<=n do
begin
if tree[j]=nil then
begin
new(tree[j]);tree[j]^.w:=0;tree[j]^.lw:=0;tree[j]^.rw:=0;tree[j]^.lc:=nil;tree[j]^.rc:=nil;
end;
build(tree[j],1,wei,c[i]);
delta:=lowbit(j);
j:=j+delta;
end;
end;
end;
procedure delayyy(j:wv2;o,l,r:longint); //删除节点；
var
mid,yoki:longint;
begin
if l=r then
begin
j^.data:=0;dec(j^.w);
exit;
end;
mid:=(l+r)>>1;
if o<=mid then
begin
yoki:=1;dec(j^.lw);
delayyy(j^.lc,o,l,mid);
end else
begin
yoki:=2;dec(j^.rw);
delayyy(j^.rc,o,mid+1,r);
end;
if j^.lw=0 then j^.lc:=nil;
if j^.rw=0 then j^.rc:=nil;
end;
procedure prominences;
var
l,r,mid,
oy:longint;//差；
begin
num:=n;
for xx:=1 to m do
if ttt[xx].k<>-maxlongint then
begin
l:=1;r:=wei;
topl:=0;topr:=0;k:=ttt[xx].k;
i:=ttt[xx].i-1;
while i>0 do
begin
topl:=topl+1;tl[topl]:=tree[i];
i:=i-lowbit(i);
end;
i:=ttt[xx].j;
while i>0 do//找相关的节点；
begin
topr:=topr+1;tr[topr]:=tree[i];
i:=i-lowbit(i);
end;
while l<>r do
begin
mid:=(l+r)>>1;
suml:=0;sumr:=0;
for i:=1 to topl do suml:=suml+tl[i]^.lw; //求左权值之和；
for i:=1 to topr do sumr:=sumr+tr[i]^.lw;
oy:=sumr-suml;
if oy>=k then
begin
r:=mid;
for i:=1 to topl do if tl[i]^.lc<>nil then tl[i]:=tl[i]^.lc else tl[i]:=j1;
for i:=1 to topr do if tr[i]^.lc<>nil then tr[i]:=tr[i]^.lc else tr[i]:=j1;
end else
begin
l:=mid+1;k:=k-oy;
for i:=1 to topl do if tl[i]^.rc<>nil then tl[i]:=tl[i]^.rc else tl[i]:=j1;
for i:=1 to topr do if tr[i]^.rc<>nil then tr[i]:=tr[i]^.rc else tr[i]:=j1;
end;
end;
writeln(a[l].data);
end else
begin
i:=ttt[xx].i;k:=ttt[xx].j;
num:=num+1;
while i<=n do
begin
delayyy(tree[i],c[ttt[xx].i],1,wei);
build(tree[i],1,wei,c[num]);
i:=i+lowbit(i);
end;
c[ttt[xx].i]:=c[num];//别忘了这个！
end;
end;
{============================}
begin
readln(n,m);
new(j1);
with j1^ do
begin
lw:=0;rw:=0;w:=0;lc:=nil;rc:=nil;
end;
init;
bbuuiilldd;
prominences;
end.
RSS Feed