给你一个数列，让你实现区间加上一个值，区间翻转，区间最大值
裸splay，懒标记一发即可
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
struct Node{
Node *ch[2];
int m, v, k, s, f;
inline int cmp(int x){
int o = 0;
if(ch[0] != NULL){
if(ch[0] -> s >= x) return 0;
o += ch[0] -> s;
}
if(o + 1 == x) return -1;
return 1;
}
inline void maintain(){
s = 1;
if(ch[0] != NULL) s += ch[0] -> s;
if(ch[1] != NULL) s += ch[1] -> s;
return;
}
inline void Back(){
m = v;
if(ch[0] != NULL) m = max(m, ch[0] -> m);
if(ch[1] != NULL) m = max(m, ch[1] -> m);
return;
}
inline void pushdown(){
if(f == 1){
if(ch[0] != NULL){
ch[0] -> f ^= 1;
swap(ch[0] -> ch[0], ch[0] -> ch[1]);
}
if(ch[1] != NULL){
ch[1] -> f ^= 1;
swap(ch[1] -> ch[0], ch[1] -> ch[1]);
}
f = 0;
}
if(ch[0] != NULL){
ch[0] -> k += k;
ch[0] -> m += k;
ch[0] -> v += k;
}
if(ch[1] != NULL){
ch[1] -> k += k;
ch[1] -> m += k;
ch[1] -> v += k;
}
k = 0;
return;
}
};
struct splay_tree{
Node ft[1000000];
int size;
Node *p;
int x, y;
inline void init(){
size = 0;
return;
}
inline void rotate(Node* &o, int d){
Node *k = o -> ch[d ^ 1];
k -> pushdown(); //注意这里
o -> ch[d ^ 1] = k -> ch[d];
k -> ch[d] = o;
o -> maintain();
k -> maintain();
o -> Back();
k -> Back();
o = k;
return;
}
inline void splay(Node* &o, int k){
o -> pushdown();
if(o -> ch[0] != NULL) o -> ch[0] -> pushdown();
if(o -> ch[1] != NULL) o -> ch[1] -> pushdown();
int d = o -> cmp(k);
if(d == 1 && o -> ch[0] != NULL) k = k - o -> ch[0] -> s - 1;
else if(d == 1) k --;
if(d != -1){
Node* w = o -> ch[d];
int d2 = w -> cmp(k);
int k2 = k;
if(d2 != 0){
k2 --;
if(w -> ch[0] != NULL) k2 -= w -> ch[0] -> s;
}
if(d2 != -1){
splay(w -> ch[d2], k2);
if(d == d2) rotate(o, d ^ 1);
else rotate(o -> ch[d], d);
}
rotate(o, d ^ 1);
}
if(o -> ch[0] != NULL) o -> ch[0] -> pushdown();
if(o -> ch[1] != NULL) o -> ch[1] -> pushdown();
o -> Back();
return;
}
inline Node* merge(Node *left, Node *right){
if(left == NULL) return right;
if(right == NULL) return left;
splay(left, left -> s);
left -> ch[1] = right;
left -> maintain();
left -> Back();
return left;
}
inline void split(Node* &o, int k, Node* &left, Node* &right){
if(k == 0){
left = NULL;
right = o;
return;
}
splay(o, k);
left = o;
right = o -> ch[1];
left -> ch[1] = NULL;
left -> maintain();
left -> Back();
return;
}
inline void insert(Node* &o, int l, int r){
if(r < l) return;
int mid = (l + r) / 2;
o = &ft[size]; size ++;
o -> ch[0] = o -> ch[1] = NULL;
o -> v = o -> m = o -> f = o -> k = 0;
if(l != r){
insert(o -> ch[0], l, mid - 1);
insert(o -> ch[1], mid + 1, r);
}
o -> maintain();
return;
}
inline void add1(Node* &o, int l, int r, int t){
if(r < l) return;
o -> pushdown();
if(y < l || r < x) return;
if(x <= l && r <= y){
o -> m += t;
o -> v += t;
o -> k += t;
return;
}
int mid = l;
if(o -> ch[0] != NULL) mid += o -> ch[0] -> s;
if(x <= mid && mid <= y) o -> v += t;
if(o -> ch[0] != NULL) add1(o -> ch[0], l, mid - 1, t);
if(o -> ch[1] != NULL) add1(o -> ch[1], mid + 1, r, t);
o -> Back();
return;
}
inline void add2(Node* &o, int l, int r){
Node *left, *mid, *right;
split(p, l - 1, left, mid);
split(mid, r - l + 1, mid, right);
swap(mid -> ch[0], mid -> ch[1]);
mid -> f ^= 1;//注意这里
p = merge(left, merge(mid, right));
return;
}
inline int query(Node* &o, int l, int r){
if(r < l) return -2147483640;
o -> pushdown();
if(y < l || r < x) return -214743640;
if(x <= l && r <= y) return o -> m;
int mid = l;
if(o -> ch[0] != NULL) mid += o -> ch[0] -> s;
int ret = -2147483640;
if(x <= mid && mid <= y) ret = o -> v;
if(o -> ch[0] != NULL) ret = max(ret, query(o -> ch[0], l, mid - 1));
if(o -> ch[1] != NULL) ret = max(ret, query(o -> ch[1], mid + 1, r));
o -> Back();
return ret;
}
} wt;
int main(){
/*freopen("seq1.in", "r", stdin);
freopen("seq.out", "w", stdout);*/
int n, m;
scanf("%d%d", &n, &m);
wt.insert(wt.p, 1, n);
for(int i = 1; i <= m; i ++){
int o;
int a, b, c;
scanf("%d", &o);
if(o == 1){
scanf("%d%d%d", &a, &b, &c);
wt.x = a; wt.y = b;
wt.add1(wt.p, 1, n, c);
}
else if(o == 2){
scanf("%d%d", &a, &b);
wt.add2(wt.p, a, b);
}
else{
scanf("%d%d", &a, &b);
wt.x = a; wt.y = b;
printf("%d\n", wt.query(wt.p, 1, n));
}
}
return 0;
}