1251: 序列终结者
Time Limit: 20 Sec Memory Limit: 162 MBSubmit: 2301 Solved: 923
[Submit][Status]
Description
网上有许多题，就是给定一个序列，要你支持几种操作：A、B、C、D。一看另一道题，又是一个序列 要支持几种操作：D、C、B、A。尤其是我们这里的某人，出模拟试题，居然还出了一道这样的，真是没技术含量……这样 我也出一道题，我出这一道的目的是为了让大家以后做这种题目有一个“库”可以依靠，没有什么其他的意思。这道题目 就叫序列终结者吧。 【问题描述】 给定一个长度为N的序列，每个序列的元素是一个整数（废话）。要支持以下三种操作： 1. 将[L,R]这个区间内的所有数加上V。 2. 将[L,R]这个区间翻转，比如1 2 3 4变成4 3 2 1。 3. 求[L,R]这个区间中的最大值。 最开始所有元素都是0。
Input
第一行两个整数N，M。M为操作个数。 以下M行，每行最多四个整数，依次为K，L，R，V。K表示是第几种操作，如果不是第1种操作则K后面只有两个数。
Output
对于每个第3种操作，给出正确的回答。
Sample Input
4 4
1 1 3 2
1 2 4 -1
2 1 3
3 2 4
1 1 3 2
1 2 4 -1
2 1 3
3 2 4
Sample Output
2
【数据范围】
N<=50000，M<=100000。
【数据范围】
N<=50000，M<=100000。
HINT
Source
题解：
这题还没有维护数列BT，就敢叫序列终结者？
注意标记的传递和边界的处理，专门增加的两个节点不能影响到答案，0 也不能影响到答案
代码：
1 {$inline on} 2 {$M 1000000000,0,maxlongint} 3 const maxn=100000+1000; 4 var s,fa,mx,tag,v,id,a:array[0..maxn] of longint; 5 rev:array[0..maxn] of boolean; 6 c:array[0..maxn,0..1] of longint; 7 i,j,n,m,x,y,z,tot,rt,now,l,r:longint; 8 ch:longint; 9 procedure swap(var x,y:longint);inline; 10 var t:longint; 11 begin 12 t:=x;x:=y;y:=t; 13 end; 14 function max(x,y:longint):longint;inline; 15 begin 16 if x>y then exit(x) else exit(y); 17 end; 18 procedure pushup(x:longint);inline; 19 begin 20 l:=c[x,0];r:=c[x,1]; 21 s[x]:=s[l]+s[r]+1; 22 mx[x]:=max(v[x],max(mx[l],mx[r])); 23 end; 24 procedure rever(x:longint);inline; 25 begin 26 if x=0 then exit; 27 rev[x]:=not(rev[x]); 28 swap(c[x,0],c[x,1]); 29 end; 30 procedure change(x,val:longint);inline; 31 begin 32 if x=0 then exit; 33 inc(tag[x],val); 34 inc(v[x],val); 35 inc(mx[x],val); 36 end; 37 procedure pushdown(x:longint);inline; 38 var l,r:longint; 39 begin 40 l:=c[x,0];r:=c[x,1]; 41 if tag[x]<>0 then 42 begin 43 change(l,tag[x]);change(r,tag[x]); 44 tag[x]:=0; 45 end; 46 if rev[x] then 47 begin 48 rever(l);rever(r); 49 rev[x]:=false; 50 end; 51 end; 52 procedure rotate(x:longint;var k:longint);inline; 53 var y,z,l,r:longint; 54 begin 55 y:=fa[x];z:=fa[y]; 56 l:=ord(c[y,1]=x);r:=l xor 1; 57 if y=k then k:=x else c[z,ord(c[z,1]=y)]:=x; 58 fa[x]:=z;fa[y]:=x;fa[c[x,r]]:=y; 59 c[y,l]:=c[x,r];c[x,r]:=y; 60 pushup(y);pushup(x); 61 end; 62 procedure splay(x:longint;var k:longint);inline; 63 var y,z:longint; 64 begin 65 while x<>k do 66 begin 67 y:=fa[x];z:=fa[y]; 68 if y<>k then 69 if (c[z,0]=y) xor (c[y,0]=x) then rotate(x,k) 70 else rotate(y,k); 71 rotate(x,k); 72 end; 73 end; 74 procedure build(l,r,f:longint);inline; 75 var x,y,z,mid:longint; 76 begin 77 if l>r then exit; 78 mid:=(l+r)>>1; 79 x:=id[mid];y:=id[f]; 80 v[x]:=a[mid]; 81 c[y,ord(mid>f)]:=x;fa[x]:=y; 82 if l=r then 83 begin 84 s[x]:=1;mx[x]:=v[x]; 85 exit; 86 end; 87 build(l,mid-1,mid);build(mid+1,r,mid); 88 pushup(x); 89 end; 90 function find(x,rank:longint):longint;inline; 91 var l,r:longint; 92 begin 93 pushdown(x); 94 l:=c[x,0];r:=c[x,1]; 95 if s[l]+1=rank then exit(x) 96 else if s[l]>=rank then exit(find(l,rank)) 97 else exit(find(r,rank-s[l]-1)); 98 end; 99 procedure split(l,r:longint;var x,y:longint);inline; 100 begin 101 x:=find(rt,l);y:=find(rt,r); 102 splay(x,rt);splay(y,c[x,1]); 103 end; 104 procedure main; 105 begin 106 readln(n,m); 107 for i:=1 to n+2 do id[i]:=i; 108 fillchar(a,sizeof(a),0); 109 a[1]:=-maxlongint;a[n+2]:=-maxlongint; 110 mx[0]:=-maxlongint; 111 build(1,n+2,0);rt:=(n+3)>>1; 112 for i:=1 to m do 113 begin 114 read(ch); 115 case ch of 116 1:begin 117 readln(l,r,z);split(l,r+2,x,y); 118 change(c[y,0],z); 119 end; 120 2:begin 121 readln(l,r);split(l,r+2,x,y); 122 rever(c[y,0]); 123 end; 124 3:begin 125 readln(l,r);split(l,r+2,x,y); 126 writeln(mx[c[y,0]]); 127 end; 128 end; 129 end; 130 end; 131 begin 132 assign(input,'input.txt');assign(output,'output.txt'); 133 reset(input);rewrite(output); 134 main; 135 close(input);close(output); 136 end.