题意: 给定初始值都为0的一个序列，三种操作。 第一种区间增加一个值，第二种区间翻转，第三种询问区间最大值。 解析: 因为有第二种所以不能上线段树了，只好上splay了。 好久不写splay刚开始一顿蒙- -! 俩标记，，再维护个最值即可。 代码:
using namespace std;int siz[N],fa[N],ma[N],rev[N],col[N],val[N];int ch[N][2];int tot;int root;void newnode(int &rt,int p,int k){rt=++tot;siz[rt]=1,fa[rt]=p;ma[rt]=val[rt]=k;rev[rt]=col[rt]=ch[rt][0]=ch[rt][1]=0;}void pushup(int rt){siz[rt]=1,ma[rt]=val[rt];if(ch[rt][0]!=0)siz[rt]+=siz[ch[rt][0]],ma[rt]=max(ma[rt],ma[ch[rt][0]]);if(ch[rt][1]!=0)siz[rt]+=siz[ch[rt][1]],ma[rt]=max(ma[rt],ma[ch[rt][1]]);}void pushdown(int rt){if(!rt)return;if(col[rt]!=0){int l=ch[rt][0],r=ch[rt][1];if(l!=0)ma[l]+=col[rt],val[l]+=col[rt],col[l]+=col[rt];if(r!=0)ma[r]+=col[rt],val[r]+=col[rt],col[r]+=col[rt];col[rt]=0;}if(rev[rt]){int l=ch[rt][0],r=ch[rt][1];if(l!=0)rev[l]^=1,swap(ch[l][0],ch[l][1]);if(r!=0)rev[r]^=1,swap(ch[r][0],ch[r][1]);rev[rt]^=1;}}void rotate(int x){int y=fa[x],kind=ch[y][1]==x;pushdown(y),pushdown(x);ch[y][kind]=ch[x][!kind];fa[ch[y][kind]]=y;ch[x][!kind]=y;fa[x]=fa[y];fa[y]=x;ch[fa[x]][ch[fa[x]][1]==y]=x;pushup(y),pushup(x);}void build(int &rt,int l,int r,int p){if(l>r)return;int mid=(l+r)>>1;newnode(rt,p,0);build(ch[rt][0],l,mid-1,rt);build(ch[rt][1],mid+1,r,rt);pushup(rt);}void splay(int x,int goal){while(fa[x]!=goal){int y=fa[x],z=fa[y];if(z==goal)rotate(x);else if((ch[y][1]==x)==(ch[z][1]==y))rotate(y),rotate(x);else rotate(x),rotate(x);}if(goal==0)root=x;}int find(int x,int k){pushdown(x);int lsum=siz[ch[x][0]]+1;if(lsum==k)return x;else if(lsum<k)return find(ch[x][1],k-lsum);else return find(ch[x][0],k);}void update_col(int l,int r,int v){splay(find(root,l),0);splay(find(root,r+2),root);col[ch[ch[root][1]][0]]+=v;ma[ch[ch[root][1]][0]]+=v;val[ch[ch[root][1]][0]]+=v;}void update_rev(int l,int r){splay(find(root,l),0);splay(find(root,r+2),root);int tmp=ch[ch[root][1]][0];rev[tmp]^=1;swap(ch[tmp][0],ch[tmp][1]);}int get_max(int l,int r){splay(find(root,l),0);splay(find(root,r+2),root);return ma[ch[ch[root][1]][0]];}int n,m;int main(){scanf(“%d%d”,&n,&m);newnode(root,0,-1);newnode(ch[root][1],root,-1);build(ch[ch[root][1]][0],1,n,ch[root][1]);for(int i=1;i<=m;i++){int opt,l,r,v;scanf(“%d”,&opt);switch(opt){case 1:scanf(“,&l,&r,&v);update_col(l,r,v);break;case 2:scanf(“%d%d”,&l,&r);update_rev(l,r);break;case 3:scanf(“%d%d”,&l,&r);printf(“%d\n”,get_max(l,r));break;}}}
那里面非常漂亮，个个观景区都能看到奇形怪状的岩石。
