拼点游戏解题报告

1、拼点解题中山纪念中学【题源】本题来自NOI Wer C2011拼点。【前言】这类数据结构题平日拿来练练程序实现是不错的，但遇到的话，就。多做题，时才能得心应手。本题要求选手熟悉平衡树和线段树等数据结构的基本运用，其中涉及到的一些问题的转换是挺难的，考验选手的思维深度。在此使用sbt树或treap。【题目大意】给出一个有n个元素原始数列U=( , , )，以及q个修改和询问：修改：l,r,c，将u中第l至第r个元素同时增加c。询问：定义U的一个下标序列I=( , , )满足1 n，其对应的值D(I)= 。D(I)最大值对应的I记为Imax。每一次对Imax 操作，选择一个正整数k（2*k+1 m

2、），修改 和 的值。要保证Imax依然是下标序列。问，1，D(I)的最大值；2，至少需要操作多少次才能是D(I) 。样列输入：样例输出：25 99 10 7 6 810 4 5 20 3 5 410 2 5 -20 3 5 -30 4 5 -20 5 5 -433 15 -10 04 -14 -1【数据范围】对于10%的数据满足n，q对于30%的数据满足n，q 13； 1000；对于另外20%的数据满足T=1 且n 40000；对于100%的数据满足T 3 且n，q 105，同时初始序列U 满足0 ui 231，|c|正，并不会对负数区间产生影响。正-负，可能将左右两段的负数区间合并成一段负数

3、区间，需要将原本的两段负数区间得出的负数值从平衡树中去掉，然后新负数区间的负数值。负-正，可能将一段负数区间分成两段负数区间，需要将原本的一段负数区间得出的负数值从平衡树去掉，然后新的两段负数区间的负数值。负-负，虽然不影响负数区间的个数，但是会改变负数期间的负数值，需要将原本负数区间得出的负数值从平衡树去掉，然后负数区间新的负数值。那么如何快速寻找这些负数区间呢?可以建另一棵平衡树负数区间；亦可以使用记有区间最大值 max 的线段树进行，着所有，求该位置左右两边最靠近的正数值。两者都能在 O(logN)的时间复杂度内寻找出要求的负数期间。总地来说，第二问的求解比起第一问复杂得多，实现起来也复

4、杂得多，需要一定的思考深度以及对平衡树和线段树等数据结构灵活运用。各种数据结构的复杂度都是 O(logN)级别的，因此算法总时间复杂度约为 O(NlogN)。可在规定时间内求得解。【程序实现（pascal）】source by Ljnanest. type da=recordmax:long;sum: end;64;type dataE=recordsum,value:64;Num,L,R,ran:long end;varca,N,M,i,j,x,y,z,Q,NumE,Len,ge:long;ans,tmp:64;d:array0.1000000of T:array0.1000000of E:

5、array0.1000000oflong;da;dataE;function max(a,b:long beginif ab then exit(a) end;):long;else exit(b);/ 更新线段树上的结点. procedure chgT(x:long begin);Tx.max:=max(Tx*2.max,Tx*2+1.max);Tx.sum:=Tx*2.sum+Tx*2+1.sum;end;/ 线段树新的结点. procedure insT(x,y:long beginx:=Len-1+x;);Tx.sum:=y; while x1 dox:=x shr chgT(x);e

6、nd;Tx.max:=y; begin1;end;/ 线段树求区间x,y的最大值. function getT_max(k,L,R,x,y:long begin):long;if (Rx)or(yL) then exit(-maxlong);if (x=L)and(R=y) then exit(Tk.max); exit(max(getT_max(k*2,L,(L+R)shr1,x,y),getT_max(k*2+1,(L+R)shr 1+1,R,x,y); end;/ 线段树求区间x,y的和function getT_sum(k,L,R,x,y:long): beginif (Rx)or(y

7、L) then exit(0);64;if (x=L)and(R=y) then exit(Tk.sum);exit(getT_sum(k*2,L,(L+R)shr 1+1,R,x,y);end;1,x,y)+getT_sum(k*2+1,(L+R)shr/ 线段树求1,x中最靠近 x 的正数位置.function find_L(k,L,R,x:long begin):long;if if if(xL) then exit(-1); Tk.max=0 then exit(-1); (L=R) then exit(L);find_L:=find_L(k*2+1,(L+R)shr 1+1,R,x)

8、;if find_L=-1 then find_L:=find_L(k*2,L,(L+R)shr 1,x);end;/ 线段树求x,n中最靠近 x 的正数位置.function find_R(k,L,R,x:long begin):long;if if if(Rx) then exit(-1); Tk.max=0 then exit(-1); (L=R) then exit(L);find_R:=find_R(k*2,L,(L+R)shr 1,x);if find_R=-1 then find_R:=find_R(k*2+1,(L+R)shr 1+1,R,x);end;/ 更新平衡树上的结点.

9、 procedure chgE(x:long begin);Ex.sum:=EEx.L.sum+EEx.R.sum+Ex.value;Ex.Num:=EEx.L.Num+EEx.R.Num+1;end;/ 右旋.function turn_right(x:long):long;vartmp:long begin;tmp:=Ex.L; Ex.L:=Etmp.R;Etmp.R:=x;chgE(x); chgE(tmp); exit(tmp);end;/ 左旋.function turn_left(x:long):long;var tmp:long begin;tmp:=Ex.R; Ex.R:=Et

10、mp.L;Etmp.L:=x;chgE(x); chgE(tmp); exit(tmp);end;/ 平衡树上新的数 y.function insE(x:long; y: beginif x=0 then begin inc(NumE); ENumE.sum:=y; ENumE.value:=y; ENumE.Num:=1;64):long;ENumE.L:=0; ENumE.R:=0;ENumE.ran:=random(maxlong exit(NumE););end;if Ex.valueEx.ran then exit(turn_right(x); end else beginEx.R:

11、=insE(Ex.R,y);if EEx.R.ranEx.ran then exit(turn_left(x);end;chgE(x); exit(x);end;/ 平衡树上删除数 y. function delE(x:long; y:64):long;var tmp:long begin;if Ex.value=y then beginif (Ex.L=0)and(Ex.R=0) then exit(0);if (EEx.L.ranEEx.R.ran) then begin tmp:=turn_right(x); Etmp.R:=delE(x,y);end else begin tmp:=t

12、urn_left(x); Etmp.L:=delE(x,y);end;chgE(tmp); exit(tmp);end;ifEx.value=y then exit(findE(Ex.L,y);y:=y-EEx.L.sum; findE:=EEx.L.Num; if Ex.value=y then exit(findE); exit(findE+1+findE(Ex.R,y-Ex.value);end;/ 修改 d 值后,对负数区间影响的 4 种情况.procedure updata(x,y:long);varnd,L,R:long;tmp:64;beginif (xN) then exit;

13、 nd:=dx+y;if (nd0)and(dx0) then begin ans:=ans-dx+nd;dx:=nd; end elseif (nd=0)and(dx=0) then begin L:=find_L(1,1,Len,x);R:=find_R(1,1,Len,x);if (L-1)and(R-1) then begintmp:=getT_sum(1,1,Len,L+1,R-1)-getT_max(1,1,Len,L+1,R-1); ge:=delE(ge,-tmp);end;dx:=nd;insT(x,dx);if (L-1)and(R-1) then begintmp:=ge

14、tT_sum(1,1,Len,L+1,R-1)-getT_max(1,1,Len,L+1,R-1); ge:=insE(ge,-tmp);end; end elseif (nd=0) then begin L:=find_L(1,1,Len,x-1);R:=find_R(1,1,Len,x+1);if (L-1)and(L+1x) then begintmp:=getT_sum(1,1,Len,L+1,x-1)-getT_max(1,1,Len,L+1,x-1); ge:=delE(ge,-tmp);end;if (R-1)and(R-1x) then begintmp:=getT_sum(1

15、,1,Len,x+1,R-1)-getT_max(1,1,Len,x+1,R-1); ge:=delE(ge,-tmp);end;ans:=ans-dx; dx:=nd;insT(x,dx);if (L-1)and(R-1) then begintmp:=getT_sum(1,1,Len,L+1,R-1)-getT_max(1,1,Len,L+1,R-1); ge:=insE(ge,-tmp);end;end else begin L:=find_L(1,1,Len,x-1);R:=find_R(1,1,Len,x+1);if (L-1)and(R-1) then begintmp:=getT

16、_sum(1,1,Len,L+1,R-1)-getT_max(1,1,Len,L+1,R-1); ge:=delE(ge,-tmp);end;dx:=nd; insT(x,dx);ans:=ans+dx;if (L-1)and(L+1x) then begintmp:=getT_sum(1,1,Len,L+1,x-1)-getT_max(1,1,Len,L+1,x-1); ge:=insE(ge,-tmp);end;if (R-1)and(R-1x) then begintmp:=getT_sum(1,1,Len,x+1,R-1)-getT_max(1,1,Len,x+1,R-1); ge:=

17、insE(ge,-tmp);end;end;end;begin randomize;assign(input,joy.in); reset(input); assign(output,joy.out); rewrite(output);readln(ca);forca:=1 to ca do begin readln(N,M); N:=N-1;for i:=0 to N do read(di); readln; for i:=N downto 1 do di:=di-di-1; Len:=1 shl trunc(ln(n-1)/ln(2)+1);for i:=1 to 2*Len-1 do begin Ti.sum:=0;d0:=0;Ti.max:=-maxlong;end;ge:=0; NumE:=0; E0.sum:=0; E0.value:=0; E0.Num:=0;for i:=1 to NnsT(i,di);i:=1;whileifans:=0;i0 then begin ans:=ans+di; inc(i);end else beginj:=find_R(1,1,Len,i); if j=-1 then break; if i1 then begintmp:=getT_sum(1,1,Len,i,j-1)-getT_max(1,1,Len,i,j-1);ge:=