P4146 序列终结者

admin

https://www.luogu.com.cn/problem/P4146

题目背景
网上有许多题，就是给定一个序列，要你支持几种操作：A、B、C、D。一看另一道题，又是一个序列要支持几种操作：D、C、B、A。尤其是我们这里的某人，出模拟试题，居然还出了一道这样的，真是没技术含量……

这样我也出一道题，我出这一道的目的是为了让大家以后做这种题目有一个“库”可以依靠，没有什么其他的意思。

这道题目就叫序列终结者吧。

题目描述
给定一个长度为N的序列，每个序列的元素是一个整数（废话）。要支持以下三种操作：

将[L,R]这个区间内的所有数加上V。
将[L,R]这个区间翻转，比如1 2 3 4变成4 3 2 1。
求[L,R]这个区间中的最大值。
最开始所有元素都是0。

输入格式
第一行两个整数N，M。M为操作个数。

以下M行，每行最多四个整数，依次为K，L，R，V。K表示是第几种操作，如果不是第1种操作则K后面只有两个数。

输出格式
对于每个第3种操作，给出正确的回答。

输入输出样例
输入 #1复制
4 4
1 1 3 2
1 2 4 -1
2 1 3
3 2 4
输出 #1复制
2
说明/提示
N≤50000,M≤100000。

admin

这个题是序列上的问题，那些数据结果可以支持薛烈上的问题呢，线段树，SPLAY，
因为涉及到翻转，这个线段树就很为难了，所对我们就用 splay，毕竟他的名字叫伸展树，可以伸展，所以处理序列比较好。

建一个SPLAY树，

admin

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. const int inf=0X3FFFFFFF;
   
4. const int N=50100;
   
5. struct node
   
6. {
   
7.         int val,fa,s[2],sz,mx,rev,add;
   
8. } a[N];
   
9. int n, tot, root;
   
10. void ArrayPr()   /// 调试监视使用
    
11. {
    
12.         cout<<endl<<"  i ";
    
13.         for (int i=1; i<=tot; i++) cout<<setw(3)<<i;
    
14.         cout<<endl<<"val ";
    
15.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].val;
    
16.         cout<<endl<<" s0 ";
    
17.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[0];
    
18.         cout<<endl<<" s1 ";
    
19.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[1];
    
20.         cout<<endl<<" fa ";
    
21.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].fa;
    
22.         cout<<endl<<" sz ";
    
23.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].sz;
    
24.         cout<<endl<<" mx ";
    
25.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].mx;
    
26.         cout<<endl<<"add ";
    
27.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].add;
    
28.         cout<<endl<<"rev ";
    
29.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].rev;
    
30.         cout<<endl;
    
31. }
    
32. 
    
33. 
    
34. void pushdown(int rt)
    
35. {
    
36.         if (rt==0) return ;
    
37.         int V=a[rt].add,REV=a[rt].rev;
    
38.         int l=a[rt].s[0], r=a[rt].s[1];
    
39.         if (V!=0)
    
40.                 {
    
41.                         a[rt].val+=V,a[rt].mx+=V;
    
42.                         a[rt].add=0;
    
43.                         if (l>0)a[l].add+=V;
    
44.                         if (r>0)a[r].add+=V;
    
45.                 }
    
46.         if (REV>0)  /// 没写好！
    
47.                 {
    
48.                         a[rt].s[0]=r,a[rt].s[1]=l;
    
49.                         a[rt].rev=0;
    
50.                         if (l>0)a[l].rev^=1;
    
51.                         if (r>0)a[r].rev^=1;
    
52.                 }
    
53.         ///这里感觉写的不好 没必要全传  我要保证正确
    
54. 
    
55. 
    
56. 
    
57. }
    
58. void BSTPr(int rt)   ///中序输出以rt为根的BST
    
59. {
    
60.         pushdown(rt);
    
61.         if (rt>0)
    
62.                 {
    
63.                         BSTPr(a[rt].s[0]);
    
64.                         cout<<a[rt].val<<' ';
    
65.                         BSTPr(a[rt].s[1]);
    
66.                 }
    
67. }
    
68. void pushup(int rt)
    
69. {
    
70.         int l=a[rt].s[0], r=a[rt].s[1];       
    
71.         a[rt].sz=a[l].sz+a[r].sz+1;
    
72.         int mxl=-inf,mxr=-inf;
    
73.         if (l>0) mxl=a[l].mx+a[l].add;
    
74.         if (r>0) mxr=a[r].mx+a[r].add;
    
75.         a[rt].mx=max(a[rt].val,max(mxl,mxr))+a[rt].add;
    
76. }
    
77. int Son(int x)
    
78. {
    
79.         int y=a[x].fa;
    
80.         return  a[y].s[1]==x;
    
81. }
    
82. void R(int x)
    
83. {
    
84.         int y=a[x].fa;
    
85.         int z=a[y].fa;
    
86.         pushdown(y);pushdown(x);///下传
    
87.         int k=Son(x);
    
88.         int v=a[x].s[k^1];///v是x另外一边的儿子将要被挂在y下面
    
89. 
    
90.         a[y].s[k]=v,a[v].fa=y;///v挂在y下
    
91.         a[z].s[Son(y)]=x,a[x].fa=z;///x挂在z下
    
92.         a[x].s[k^1]=y,a[y].fa=x;///y挂在x下
    
93.         pushup(y);pushup(x);///上传
    
94. }
    
95. inline void Splay(int x,int rt=root)  ///把x旋到rt的位置 默认rt是根
    
96. {
    
97.         rt=a[rt].fa;
    
98.         int y,z;
    
99.         ///沿途释放pushdown?
    
100. 
     
101.         while(a[x].fa!=rt)  /// y==rt就到位
     
102.                 {
     
103.                         y=a[x].fa,z=a[y].fa;;
     
104.                         if(z!=rt)
     
105.                                 if(Son(x)==Son(y))R(y); /// 一字
     
106.                                 else R(x);
     
107.                         R(x);
     
108.                 }
     
109.         if(rt==0)root=x;
     
110. }
     
111. int Getkth(int rt,int k) ///第k个的数的位置
     
112. {
     
113.         pushdown(rt);
     
114.         int l=a[a[rt].s[0]].sz;  /// RT的左儿子下的个数
     
115.         if(l+1==k) return rt;
     
116.         if(l+1>k) return Getkth(a[rt].s[0], k); ///左儿子里去找
     
117.         if(l+1<k) return Getkth(a[rt].s[1], k-(l+1));
     
118. }
     
119. int Build(int l,int r)
     
120. {
     
121.         if (l>r) return 0;
     
122.         if (l==r)
     
123.                 {
     
124.                         a[l].sz=1;
     
125.                         return  l;
     
126.                 }
     
127.         int m=(l+r)/2;
     
128.         int L=a[m].s[0]=Build(l,m-1);
     
129.         int R=a[m].s[1]=Build(m+1,r);
     
130.         a[m].sz=r-l+1;
     
131.         a[L].fa=a[R].fa=m;
     
132.         return m;
     
133. }
     
134. void Get(int x,int y) ///把 第x个转到根，y转到x的右子树
     
135. {
     
136.         int l=Getkth(root,x);
     
137.         int r=Getkth(root,y);
     
138.         Splay(l,root);
     
139.         Splay(r,a[root].s[1]);
     
140. }
     
141. int main()
     
142. {
     
143.         ///freopen("4146.in","r",stdin);
     
144.         ///freopen("4146.out","w",stdout);
     
145.         int m,x,opt,L,R,V;
     
146.         cin>>n>>m;
     
147. ///初始建树
     
148.         tot=n+2;
     
149.         root=Build(1,tot);
     
150.         a[0].val=a[1].val=a[n+2].val=-inf;///两个假节点
     
151.         while(m--)
     
152.                 {
     
153.                         cin>>opt>>L>>R;
     
154.                         Get(L,R+2);
     
155.                         int t=a[root].s[1];
     
156.                         t=a[t].s[0];
     
157.                         ///BSTPr(root);
     
158.                         if (opt==1)
     
159.                                 {
     
160.                                         cin>>V;
     
161.                                         a[t].add+=V;
     
162.                                 }
     
163.                         if (opt==2)a[t].rev^=1;
     
164.                         if (opt==3)
     
165.                                 {
     
166.                                         cout<<(a[t].mx+a[t].add)<<endl;
     
167.                                 }
     
168.                         if (opt==4)
     
169.                                 {
     
170.                                         BSTPr(root);
     
171.                                         for (int i=1; i<=tot; i++) Splay(i,root);
     
172.                                         BSTPr(root);
     
173.                                 }
     
174.                 }
     
175. 
     
176.         return 0;
     
177. }
     
178. /*
     
179. 10 3
     
180. 1 3 8 5
     
181. 2 3 9
     
182. 1 3 4 1
     
183. */
     
184. /* 先只测试加
     
185. 10 50
     
186. 1 3 8 -5
     
187. 1 5 9 -2
     
188. 1 1 3 -1
     
189. 3 3 6
     
190. 4 4 4
     
191. */
     
192. /* 只测试转
     
193. 10 17
     
194. 1 1 10 1
     
195. 1 2 10 1
     
196. 1 3 10 1
     
197. 1 4 10 1
     
198. 1 5 10 1
     
199. 1 6 10 1
     
200. 1 7 10 1
     
201. 1 8 10 1
     
202. 1 9 10 1
     
203. 1 10 10 1
     
204. 4 4 4
     
205. 2 3 8
     
206. 4 4 4
     
207. 2 3 6
     
208. 4 4 4
     
209. 2 6 9
     
210. 4 4 4
     
211. */
     

复制代码