BZOJ 1251: 序列终结者

 

1251: 序列终结者

Time Limit: 20 Sec  Memory Limit: 162 MB
Submit: 2971  Solved: 1188
[Submit][Status][Discuss]

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

  1 #include<cstdio>
  2 #include<algorithm>
  3 using namespace std;
  4 const int maxn = 50005;
  5 const int INF = 99999999;
  6 int read()
  7 {
  8     int ans = 0, s = 1;
  9     char ch = getchar();
 10     while(ch > '9' || ch < '0')
 11     {
 12         if(ch == '-') s = -1;
 13         ch = getchar();
 14     }
 15     while(ch >= '0' && ch <= '9')
 16     {
 17         ans = ans * 10 + ch - '0';
 18         ch = getchar();
 19     }
 20     return s * ans;
 21 }
 22 struct Splay
 23 {
 24     int fa, ch[2], size;
 25     int lazy, rev, maxl, val;
 26 } s[maxn];
 27 int n, m, root, a[maxn];
 28 void pushup(int x)
 29 {
 30     s[x].size = s[s[x].ch[0]].size + s[s[x].ch[1]].size + 1;
 31     s[x].maxl = max(s[x].val, max(s[s[x].ch[0]].maxl, s[s[x].ch[1]].maxl));
 32 }
 33 void pushdown(int x)
 34 {
 35     if(s[x].lazy)
 36     {
 37         if(s[x].ch[0])
 38         {
 39             s[s[x].ch[0]].lazy += s[x].lazy;
 40             s[s[x].ch[0]].maxl += s[x].lazy;
 41             s[s[x].ch[0]].val += s[x].lazy;
 42         }
 43         if(s[x].ch[1])
 44         {
 45             s[s[x].ch[1]].lazy += s[x].lazy;
 46             s[s[x].ch[1]].maxl += s[x].lazy;
 47             s[s[x].ch[1]].val += s[x].lazy;
 48         }
 49         s[x].lazy = 0;
 50     }
 51     if(s[x].rev)
 52     {
 53         if(s[x].ch[0])
 54         {
 55             s[s[x].ch[0]].rev ^= 1;
 56             swap(s[s[x].ch[0]].ch[0], s[s[x].ch[0]].ch[1]);
 57         }
 58         if(s[x].ch[1])
 59         {
 60             s[s[x].ch[1]].rev ^= 1;
 61             swap(s[s[x].ch[1]].ch[0], s[s[x].ch[1]].ch[1]);
 62         }
 63         s[x].rev = 0;
 64     }
 65 }
 66 int identify(int x)
 67 {
 68     return s[s[x].fa].ch[1] == x;
 69 }
 70 void connect(int son, int fa, int k)
 71 {
 72     s[son].fa = fa;
 73     s[fa].ch[k] = son;
 74 }
 75 void rotate(int x)
 76 {
 77     int y = s[x].fa;
 78     int z = s[y].fa;
 79     int yk = identify(x);
 80     int zk = identify(y);
 81     int b = s[x].ch[yk ^ 1];
 82     connect(b, y, yk);
 83     connect(y, x, yk ^ 1);
 84     connect(x, z, zk);
 85     pushup(y); pushup(x);
 86 }
 87 void splay(int x, int goal)
 88 {
 89     while(s[x].fa != goal)
 90     {
 91         int y = s[x].fa;
 92         int z = s[y].fa;
 93         if(z != goal) identify(x) == identify(y) ? rotate(y) : rotate(x);
 94         rotate(x);
 95     }
 96     if(goal == 0) root = x;
 97 }
 98 int kth(int k)
 99 {
100     int now = root;
101     while(2333)
102     {
103         pushdown(now);
104         int left = s[now].ch[0];
105         if(s[left].size + 1 < k)
106         {
107             k -= s[left].size + 1;
108             now = s[now].ch[1];
109         }
110         else if(s[left].size >= k) now = left;
111         else return now;
112     }
113 }
114 int build(int l, int r, int fa)
115 {
116     if(l > r) return 0;
117     if(l == r)
118     {
119         s[l].fa = fa;
120         s[l].maxl = s[l].val = a[l];
121         s[l].size = 1;
122         return l;
123     }
124     int mid = (l + r) >> 1;
125     s[mid].ch[0] = build(l, mid - 1, mid);
126     s[mid].ch[1] = build(mid + 1, r, mid);
127     s[mid].val = a[mid];
128     s[mid].fa = fa;
129     pushup(mid);
130     return mid;
131 }
132 int split(int l, int r)
133 {
134     l = kth(l); r = kth(r + 2);
135     splay(l, 0); splay(r, l);
136     return s[s[root].ch[1]].ch[0];
137 }
138 void update(int l, int r, int v)
139 {
140     int now = split(l, r);
141     s[now].lazy += v;
142     s[now].maxl += v;
143     s[now].val += v;
144     pushup(s[root].ch[1]);
145     pushup(root);
146 }
147 void reverse(int l, int r)
148 {
149     int now = split(l, r);
150     s[now].rev ^= 1;
151     swap(s[now].ch[0], s[now].ch[1]);
152     pushup(s[root].ch[1]);
153     pushup(root);
154 }
155 int querymax(int l, int r)
156 {
157     return s[split(l, r)].maxl;
158 }
159 int main()
160 {
161     n = read(), m = read();
162     a[1] = a[n + 2] = s[0].maxl = -INF;
163     root = build(1, n + 2, 0);
164     int k, l, r, v;
165     while(m--)
166     {
167         k = read(), l = read(), r = read();
168         if(k == 1)
169         {
170             v = read();
171             update(l, r, v);
172         }
173         else if(k == 2) reverse(l, r);
174         else if(k == 3) printf("%d\n", querymax(l, r));
175     }
176     return 0;
177 }