大意：
維護(hù)一個(gè)數(shù)列 支持翻轉(zhuǎn)[l,r]，給[l,r]加上一個(gè)delta，求[l,r]的最大值
做法：
splay亂搞搞..
只需要知道3點(diǎn)：
1.整棵樹(shù)的中序遍歷序列便是當(dāng)前序列。
2.翻轉(zhuǎn)一個(gè)區(qū)間等價(jià)于交換子樹(shù)中所有節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)。
3.傳懶標(biāo)記要注意在正確的時(shí)候下傳，以及要將新改變的節(jié)點(diǎn)splay到根。
1 #include <cstdio>
2 #include <cstring>
3 struct Tsplay
4 {
5 #define Lch(t) T[t].l
6 #define Rch(t) T[t].r
7 #define Par(t) T[t].p
8 #define Max(t) T[t].max
9 #define Delt(t) T[t].delt
10 #define Val(t) T[t].val
11 #define Rev(t) T[t].rev
12 #define Size(t) T[t].size
13 int l,r,p,size;
14 int delt,max,val;
15 bool rev;
16 } T[50005];
17 int Stk[50005],root,Root;
18 int N,M,cmd,x,y,delt;
19 inline void Down(int t)
20 {
21 if (Delt(t))
22 {
23 if (Lch(t)) Delt(Lch(t))+=Delt(t),Val(Lch(t))+=Delt(t),Max(Lch(t))+=Delt(t);
24 if (Rch(t)) Delt(Rch(t))+=Delt(t),Val(Rch(t))+=Delt(t),Max(Rch(t))+=Delt(t);
25 Delt(t)=0;
26 }
27 if (Rev(t))
28 {
29 int tmp=Lch(t);Lch(t)=Rch(t);Rch(t)=tmp;
30 Rev(Lch(t))^=1,Rev(Rch(t))^=1,Rev(t)=0;
31 }
32 }
33 inline void Tupdate(int t)
34 {
35 Size(t)=1,Max(t)=Val(t);
36 if (Lch(t))
37 {
38 if (Max(Lch(t))>Max(t)) Max(t)=Max(Lch(t));
39 Size(t)+=Size(Lch(t));
40 }
41 if (Rch(t))
42 {
43 if (Max(Rch(t))>Max(t)) Max(t)=Max(Rch(t));
44 Size(t)+=Size(Rch(t));
45 }
46 }
47 inline void zig(int x)
48 {
49 int y=Par(x),z=Par(y);
50 Lch(y)=Rch(x),Par(Lch(y))=Rch(x)=y;
51 if (Lch(z)==y) Lch(z)=x;
52 else Rch(z)=x;
53 Par(x)=z,Par(y)=x;
54 Tupdate(y);
55 }
56 inline void zag(int x)
57 {
58 int y=Par(x),z=Par(y);
59 Rch(y)=Lch(x),Par(Rch(y))=Lch(x)=y;
60 if (Lch(z)==y) Lch(z)=x;
61 else Rch(z)=x;
62 Par(x)=z,Par(y)=x;
63 Tupdate(y);
64 }
65 inline void splay(int &root,int x)
66 {
67 Stk[++Stk[0]]=x;
68 for (int u=x;Par(u);u=Par(u))
69 Stk[++Stk[0]]=Par(u);
70 for (;Stk[0];--Stk[0])
71 Down(Stk[Stk[0]]);
72 for (int y,z;Par(x);)
73 {
74 y=Par(x),z=Par(y);
75 if (!z)
76 if (Lch(y)==x) zig(x);
77 else zag(x);
78 else
79 if (Lch(z)==y)
80 if (Lch(y)==x) zig(y),zig(x);
81 else zag(x),zig(x);
82 else
83 if (Rch(y)==x) zag(y),zag(x);
84 else zig(x),zag(x);
85 }
86 Tupdate(root=x);
87 }
88 inline int Findkth(int k)
89 {
90 if (k==0) return 0;
91 if (k>N) return N+1;
92 for (int p=root;;)
93 {
94 Down(p);
95 if (k<=Size(Lch(p))) p=Lch(p);
96 else
97 if (k<=Size(Lch(p))+1) return p;
98 else k-=Size(Lch(p))+1,p=Rch(p);
99 }
100 }
101 inline int Findintv(int l,int r)
102 {
103 int u=Findkth(l-1),v=Findkth(r+1),tmp;
104 if (l==1&&r==N) return root;
105 if (u<1) return splay(root,v),Lch(v);
106 if (v>N) return splay(root,u),Rch(u);
107 splay(root,v);
108 Par(Lch(v))=0;
109 splay(Lch(v),u);
110 Par(u)=v;
111 return Rch(u);
112 }
113 int main()
114 {
115 scanf("%d%d",&N,&M);
116 root=1;
117 for (int i=1;i<=N;++i)
118 Par(i)=i-1,Rch(i-1)=i,Size(i)=N-i+1;
119 for (int i=1;i<=M;++i)
120 {
121 scanf("%d%d%d",&cmd,&x,&y);
122 Root=Findintv(x,y);
123 if (cmd==1)
124 {
125 scanf("%d",&delt);
126 Delt(Root)+=delt,Max(Root)+=delt,Val(Root)+=delt;
127 splay(root,Root);
128 }
129 else
130 if (cmd==2) Rev(Root)^=1;
131 else printf("%d\n",Max(Root));
132 }
133 return 0;
134 }
135