题目描述
给定一个长度为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。
主要思路：FHQ Treap区间操作
算是一道模板题吧。主要是在维护区间加和区间翻转上。
重点就是打标记。其实区间翻转的标记方式在文艺平衡树那道题里面有用到过。就是在做一个标记，标记区间是否翻转。然后在有标记的节点上交换左右子树即可。部分代码如下：
// z[rt].col表示区间加的懒标记
// z[rt].coll表示区间翻转的懒标记
// z[rt].ch[0]表示rt节点的左子树
// z[rt].ch[1]表示rt节点的右子树
// 这个代码是下方标记的函数
inline void push_col(int rt) {
if(z[rt].col) {
if(z[rt].ch[0]) { // 分类讨论
z[z[rt].ch[0]].col += z[rt].col;
z[z[rt].ch[0]].maxx += z[rt].col;
z[z[rt].ch[0]].w += z[rt].col;
}
if(z[rt].ch[1]) {
z[z[rt].ch[1]].col += z[rt].col;
z[z[rt].ch[1]].maxx += z[rt].col;
z[z[rt].ch[1]].w += z[rt].col;
}
z[rt].col = 0; // 最后去掉标记
}
if(z[rt].coll) {
if(z[rt].ch[0]) z[z[rt].ch[0]].coll ^= 1;
if(z[rt].ch[1]) z[z[rt].ch[1]].coll ^= 1;
swap(z[rt].ch[0], z[rt].ch[1]); // 交换
z[rt].coll = 0; // 去标记
}
} 要注意的是在split和merge时加上push_col和update的操作。
code：
附带debug代码。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <queue>
#include <map>
#include <vector>
using namespace std;
#define go(i, j, n, k) for(int i = j; i <= n; i += k)
#define fo(i, j, n, k) for(int i = j; i >= n; i -= k)
#define rep(i, x) for(int i = h[x]; i; i = e[i].nxt)
#define mn 50010
#define inf 1 << 30
#define ll long long
inline int read(){
int x = 0, f = 1; char ch = getchar();
while(ch > '9' || ch < '0') { if(ch == '-') f = -f; ch = getchar(); }
while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
struct tree{
int ch[2], pri, sze, w;
int maxx;
int col, coll;
} z[mn];
inline void update(int rt) {
z[rt].sze = 1;
z[rt].maxx = z[rt].w;
if(z[rt].ch[0]) {
z[rt].sze += z[z[rt].ch[0]].sze;
z[rt].maxx = max(z[rt].maxx, z[z[rt].ch[0]].maxx);
}
if(z[rt].ch[1]) {
z[rt].sze += z[z[rt].ch[1]].sze;
z[rt].maxx = max(z[rt].maxx, z[z[rt].ch[1]].maxx);
}
}
inline void push_col(int rt) {
if(z[rt].col) {
if(z[rt].ch[0]) {
z[z[rt].ch[0]].col += z[rt].col;
z[z[rt].ch[0]].maxx += z[rt].col;
z[z[rt].ch[0]].w += z[rt].col;
}
if(z[rt].ch[1]) {
z[z[rt].ch[1]].col += z[rt].col;
z[z[rt].ch[1]].maxx += z[rt].col;
z[z[rt].ch[1]].w += z[rt].col;
}
z[rt].col = 0;
// update(rt);
}
if(z[rt].coll) {
if(z[rt].ch[0]) z[z[rt].ch[0]].coll ^= 1;
if(z[rt].ch[1]) z[z[rt].ch[1]].coll ^= 1;
swap(z[rt].ch[0], z[rt].ch[1]);
z[rt].coll = 0;
}
}
int cnt;
inline int newnode(int w = 0) {
z[++cnt].maxx = w;
z[cnt].w = w;
z[cnt].pri = rand();
z[cnt].sze = 1;
z[cnt].col = z[cnt].coll = 0;
return cnt;
}
inline int merge(int x, int y) {
if(!x || !y) return x + y;
if(z[x].pri < z[y].pri) {
push_col(x);
z[x].ch[1] = merge(z[x].ch[1], y);
update(x);
return x;
} else {
push_col(y);
z[y].ch[0] = merge(x, z[y].ch[0]);
update(y);
return y;
}
}
inline void split(int rt, int k, int &x, int &y) {
if(!rt) x = y = 0;
else {
push_col(rt);
if(k <= z[z[rt].ch[0]].sze) {
y = rt, split(z[rt].ch[0], k, x, z[rt].ch[0]);
} else {
x = rt, split(z[rt].ch[1], k - z[z[rt].ch[0]].sze - 1, z[rt].ch[1], y);
}
update(rt);
}
}
inline void debug(int rt) {
if(!rt) return;
if(z[rt].ch[0]) debug(z[rt].ch[0]);
printf("%d %d %d %d\n", z[rt].w, z[rt].maxx, z[rt].pri, z[rt].sze);
if(z[rt].ch[1]) debug(z[rt].ch[1]);
}
int n, m, rot, xx, yy, zz;
int main() {
n = read(), m = read();
go(i, 1, n, 1) {
rot = merge(rot, newnode(0));
}
go(i, 1, m, 1) {
int s = read(), l = read(), r = read(), v;
if(s == 1) {
v = read();
split(rot, r, xx, zz);
split(xx, l - 1, xx, yy);
z[yy].col += v;
z[yy].maxx += v;
z[yy].w += v;
rot = merge(merge(xx, yy), zz);
} else if(s == 2) {
split(rot, r, xx, zz);
split(xx, l - 1, xx, yy);
z[yy].coll ^= 1;
rot = merge(merge(xx, yy), zz);
} else if(s == 3) {
split(rot, r, xx, zz);
split(xx, l - 1, xx, yy);
printf("%d\n", z[yy].maxx);
rot = merge(merge(xx, yy), zz);
}
}
// debug(rot);
return 0;
}
京公网安备 11010502036488号