首页 > 代码库 > BZOJ1251: 序列终结者

BZOJ1251: 序列终结者

1251: 序列终结者

Time Limit: 20 Sec  Memory Limit: 162 MB
Submit: 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

Sample Output

2
【数据范围】
N<=50000,M<=100000。

HINT

 

Source

Splay

题解:
这题还没有维护数列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  begin101   x:=find(rt,l);y:=find(rt,r);102   splay(x,rt);splay(y,c[x,1]);103  end;104 procedure main;105  begin106   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 do113    begin114     read(ch);115     case ch of116     1:begin117       readln(l,r,z);split(l,r+2,x,y);118       change(c[y,0],z);119       end;120     2:begin121       readln(l,r);split(l,r+2,x,y);122       rever(c[y,0]);123       end;124     3:begin125       readln(l,r);split(l,r+2,x,y);126       writeln(mx[c[y,0]]);127       end;128     end;129    end;130  end;131 begin132   assign(input,input.txt);assign(output,output.txt);133   reset(input);rewrite(output);134   main;135   close(input);close(output);136 end. 
View Code