1251: 序列终结者
- Time Limit: 20 Sec Memory Limit: 162 MB
- Submit: 2971 Solved: 1188
- [Submit http://www.lydsy.com/JudgeOnline/submitpage.php?id=1251 ][Status http://www.lydsy.com/JudgeOnline/problemstatus.php?id=1251 ][Discuss http://www.lydsy.com/JudgeOnline/bbs.php?id=1251 ]
- Description
网上有许多题, 就是给定一个序列, 要你支持几种操作: ABCD 一看另一道题, 又是一个序列 要支持几种操作: DCBA 尤其是我们这里的某人, 出模拟试题, 居然还出了一道这样的, 真是没技术含量这样 我也出一道题, 我出这一道的目的是为了让大家以后做这种题目有一个库可以依靠, 没有什么其他的意思这道题目 就叫序列终结者吧 问题描述 给定一个长度为 N 的序列, 每个序列的元素是一个整数 (废话) 要支持以下三种操作: 1. 将 [L,R] 这个区间内的所有数加上 V 2. 将 [L,R] 这个区间翻转, 比如 1 2 3 4 变成 4 3 2 1 3. 求 [L,R] 这个区间中的最大值 最开始所有元素都是 0
Input
第一行两个整数 N,MM 为操作个数 以下 M 行, 每行最多四个整数, 依次为 K,L,R,VK 表示是第几种操作, 如果不是第 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
- http://www.lydsy.com/JudgeOnline/problemset.php?search=Splay
- #include<cstdio>
- #include<algorithm>
- using namespace std;
- const int maxn = 50005;
- const int INF = 99999999;
- int read()
- {
- int ans = 0, s = 1;
- char ch = getchar();
- while(ch> 9 || ch <0)
- {
- if(ch == -) s = -1;
- ch = getchar();
- }
- while(ch>= 0 && ch <= 9)
- {
- ans = ans * 10 + ch - 0;
- ch = getchar();
- }
- return s * ans;
- }
- struct Splay
- {
- int fa, ch[2], size;
- int lazy, rev, maxl, val;
- } s[maxn];
- int n, m, root, a[maxn];
- void pushup(int x)
- {
- s[x].size = s[s[x].ch[0]].size + s[s[x].ch[1]].size + 1;
- s[x].maxl = max(s[x].val, max(s[s[x].ch[0]].maxl, s[s[x].ch[1]].maxl));
- }
- void pushdown(int x)
- {
- if(s[x].lazy)
- {
- if(s[x].ch[0])
- {
- s[s[x].ch[0]].lazy += s[x].lazy;
- s[s[x].ch[0]].maxl += s[x].lazy;
- s[s[x].ch[0]].val += s[x].lazy;
- }
- if(s[x].ch[1])
- {
- s[s[x].ch[1]].lazy += s[x].lazy;
- s[s[x].ch[1]].maxl += s[x].lazy;
- s[s[x].ch[1]].val += s[x].lazy;
- }
- s[x].lazy = 0;
- }
- if(s[x].rev)
- {
- if(s[x].ch[0])
- {
- s[s[x].ch[0]].rev ^= 1;
- swap(s[s[x].ch[0]].ch[0], s[s[x].ch[0]].ch[1]);
- }
- if(s[x].ch[1])
- {
- s[s[x].ch[1]].rev ^= 1;
- swap(s[s[x].ch[1]].ch[0], s[s[x].ch[1]].ch[1]);
- }
- s[x].rev = 0;
- }
- }
- int identify(int x)
- {
- return s[s[x].fa].ch[1] == x;
- }
- void connect(int son, int fa, int k)
- {
- s[son].fa = fa;
- s[fa].ch[k] = son;
- }
- void rotate(int x)
- {
- int y = s[x].fa;
- int z = s[y].fa;
- int yk = identify(x);
- int zk = identify(y);
- int b = s[x].ch[yk ^ 1];
- connect(b, y, yk);
- connect(y, x, yk ^ 1);
- connect(x, z, zk);
- pushup(y); pushup(x);
- }
- void splay(int x, int goal)
- {
- while(s[x].fa != goal)
- {
- int y = s[x].fa;
- int z = s[y].fa;
- if(z != goal) identify(x) == identify(y) ? rotate(y) : rotate(x);
- rotate(x);
- }
- if(goal == 0) root = x;
- }
- int kth(int k)
- {
- int now = root;
- while(2333)
- {
- pushdown(now);
- int left = s[now].ch[0];
- if(s[left].size + 1 <k)
- {
- k -= s[left].size + 1;
- now = s[now].ch[1];
- }
- else if(s[left].size>= k) now = left;
- else return now;
- }
- }
- int build(int l, int r, int fa)
- {
- if(l> r) return 0;
- if(l == r)
- {
- s[l].fa = fa;
- s[l].maxl = s[l].val = a[l];
- s[l].size = 1;
- return l;
- }
- int mid = (l + r)>> 1;
- s[mid].ch[0] = build(l, mid - 1, mid);
- s[mid].ch[1] = build(mid + 1, r, mid);
- s[mid].val = a[mid];
- s[mid].fa = fa;
- pushup(mid);
- return mid;
- }
- int split(int l, int r)
- {
- l = kth(l); r = kth(r + 2);
- splay(l, 0); splay(r, l);
- return s[s[root].ch[1]].ch[0];
- }
- void update(int l, int r, int v)
- {
- int now = split(l, r);
- s[now].lazy += v;
- s[now].maxl += v;
- s[now].val += v;
- pushup(s[root].ch[1]);
- pushup(root);
- }
- void reverse(int l, int r)
- {
- int now = split(l, r);
- s[now].rev ^= 1;
- swap(s[now].ch[0], s[now].ch[1]);
- pushup(s[root].ch[1]);
- pushup(root);
- }
- int querymax(int l, int r)
- {
- return s[split(l, r)].maxl;
- }
- int main()
- {
- n = read(), m = read();
- a[1] = a[n + 2] = s[0].maxl = -INF;
- root = build(1, n + 2, 0);
- int k, l, r, v;
- while(m--)
- {
- k = read(), l = read(), r = read();
- if(k == 1)
- {
- v = read();
- update(l, r, v);
- }
- else if(k == 2) reverse(l, r);
- else if(k == 3) printf("%d\n", querymax(l, r));
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2546628.html