【传送门：BZOJ1251】
简要题意：
给出一个长度为n的序列，有m个操作，3种操作：
1 l r k将l到r的数增加k
2 l r将l到r的数列翻转
3 l r求出l到r的最大值
题解：
裸SPLAY，直接下放两种标记，一种翻转，另一种增加值
而且对于求l到r的区间，我们需要l-1和r+1的节点，而且不能用到0这个敏感位置，所以建树的时候，序列编号要从1到n+2
参考代码：
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; struct node {int son[2],f,mx,lazy,c,d;bool fz; }tr[51000];int root,len; void pushdown(int x) {int lc=tr[x].son[0],rc=tr[x].son[1];if(lc!=0) tr[lc].mx+=tr[x].lazy,tr[lc].d+=tr[x].lazy,tr[lc].lazy+=tr[x].lazy;if(rc!=0) tr[rc].mx+=tr[x].lazy,tr[rc].d+=tr[x].lazy,tr[rc].lazy+=tr[x].lazy;tr[x].lazy=0; } void reverse(int x) {tr[x].fz=false;swap(tr[x].son[0],tr[x].son[1]);int lc=tr[x].son[0],rc=tr[x].son[1];tr[lc].fz^=1;tr[rc].fz^=1; } void update(int x) {int lc=tr[x].son[0],rc=tr[x].son[1];tr[x].mx=tr[x].d;if(lc!=0) tr[x].mx=max(tr[x].mx,tr[lc].mx);if(rc!=0) tr[x].mx=max(tr[x].mx,tr[rc].mx);tr[x].c=tr[lc].c+tr[rc].c+1; } void rotate(int x,int w) {int f=tr[x].f,ff=tr[f].f;int r,R;r=tr[x].son[w];R=f;tr[R].son[1-w]=r;if(r!=0) tr[r].f=R;r=x;R=ff;if(tr[R].son[0]==f) tr[R].son[0]=r;else tr[R].son[1]=r;tr[r].f=R;r=f;R=x;tr[R].son[w]=r;tr[r].f=R;update(f);update(x); } int tmp[51000],s; void splay(int x,int rt) {int i=x;s=0;while(tr[i].f!=rt){tmp[++s]=i;i=tr[i].f;}tmp[++s]=i;while(s!=0){i=tmp[s--];if(tr[i].fz==true) reverse(i);if(tr[i].lazy!=0) pushdown(i);}while(tr[x].f!=rt){int f=tr[x].f,ff=tr[f].f;if(ff==rt){if(tr[f].son[0]==x) rotate(x,1);else rotate(x,0);}else{if(tr[f].son[0]==x&&tr[ff].son[0]==f){rotate(f,1);rotate(x,1);continue;}if(tr[f].son[1]==x&&tr[ff].son[0]==f){rotate(x,0);rotate(x,1);continue;}if(tr[f].son[0]==x&&tr[ff].son[1]==f){rotate(x,1);rotate(x,0);continue;}if(tr[f].son[1]==x&&tr[ff].son[1]==f){rotate(f,0);rotate(x,0);continue;}}}if(rt==0) root=x; } int bt(int l,int r) {if(l>r) return 0;int now=++len;tr[now].mx=tr[now].lazy=tr[now].d=0;tr[now].lazy=false;int mid=(l+r)/2;tr[now].son[0]=bt(l,mid-1);tr[now].son[1]=bt(mid+1,r);int lc=tr[now].son[0],rc=tr[now].son[1];if(lc!=0) tr[lc].f=now;if(rc!=0) tr[rc].f=now;tr[now].c=tr[lc].c+tr[rc].c+1;return now; } int finddizhi(int k) {int x=root;while(1){if(tr[x].fz==true) reverse(x);if(tr[x].lazy!=0) pushdown(x);int lc=tr[x].son[0],rc=tr[x].son[1];if(k<=tr[lc].c) x=lc;else if(k>tr[lc].c+1){k-=tr[lc].c+1;x=rc;}else break;}return x; } void add(int l,int r,int k) {int lc=finddizhi(l-1),rc=finddizhi(r+1);splay(lc,0);splay(rc,lc);int x=tr[rc].son[0];tr[x].mx+=k;tr[x].d+=k;tr[x].lazy+=k;splay(x,0); } void fanzhuan(int l,int r) {int lc=finddizhi(l-1),rc=finddizhi(r+1);splay(lc,0);splay(rc,lc);int x=tr[rc].son[0];tr[x].fz^=1;splay(x,0); } void findmax(int l,int r) {int lc=finddizhi(l-1),rc=finddizhi(r+1);splay(lc,0);splay(rc,lc);int x=tr[rc].son[0];printf("%d\n",tr[x].mx); } int main() {int n,m;scanf("%d%d",&n,&m);len=0;root=bt(1,n+2);for(int i=1;i<=m;i++){int k,l,r,v;scanf("%d%d%d",&k,&l,&r);l++;r++;if(k==1){int v;scanf("%d",&v);add(l,r,v);}if(k==2) fanzhuan(l,r);if(k==3) findmax(l,r);}return 0; }
