1251: 序列终结者Time Limit:20 SecMemory Limit:162 MBSubmit:2971Solved:1188[Submit][Status][Discuss]Description
网上有许多题，就是给定一个序列，要你支持几种操作：A、B、C、D。一看另一道题，又是一个序列 要支持几种操作：D、C、B、A。尤其是我们这里的某人，出模拟试题，居然还出了一道这样的，真是没技术含量……这样 我也出一道题，我出这一道的目的是为了让大家以后做这种题目有一个“库”可以依靠，没有什么其他的意思。这道题目 就叫序列终结者吧。 【问题描述】 给定一个长度为N的序列，每个序列的元素是一个整数（废话）。要支持以下三种操作： 1. 将[L,R]这个区间内的所有数加上V。 2. 将[L,R]这个区间翻转，比如1 2 3 4变成4 3 2 1。 3. 求[L,R]这个区间中的最大值。 最开始所有元素都是0。
Input
第一行两个整数N，M。M为操作个数。 以下M行，每行最多四个整数，依次为K，L，R，V。K表示是第几种操作，如果不是第1种操作则K后面只有两个数。
Output
对于每个第3种操作，给出正确的回答。
Sample Input
4 41 1 3 21 2 4 -12 1 33 2 4
Sample Output
2【数据范围】N<=50000，M<=100000。
HINTSource
Splay
每次进行序列操作时，把l-1旋转到根，把r+1旋转到根的右儿子，r+1的左子树就是整个区间[l,r]。
我们可以用Splay的每个节点记录该节点对应子树的信息，那么每次询问只要输出r+1的左子树中的最大值，即代码中的mx[t[y][0]]。
为了避免Splay中有节点0，我们将所有节点的编号加1。又因为要旋转l-1和r+1，所以在Splay插入节点为1到n+2。(原因显然…大家自己脑补)
这道题用Splay的提根操作达到了区间操作的目的，方法很巧妙。
另外我觉得这道题有几点需要注意：
①要理解Splay中节点的含义以及节点所记录的信息。
②区间的翻转操作很巧妙，只需要将标记下传并且交换左右子树，并不需要修改节点的max和size。
③每次find操作都要pushdown，这样就可以保证节点x到根的路径上所有点都被更新，便于之后的旋转操作。
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cstdlib>#include<cmath>#define F(i,j,n) for(int i=j;i<=n;i++)#define D(i,j,n) for(int i=j;i>=n;i–)#define LL long long#define pa pair<int,int>#define MAXN 50005#define INF 1000000000using namespace std;int n,m,rt=0,tot=0;int a[MAXN],fa[MAXN],t[MAXN][2],mx[MAXN],tag[MAXN],size[MAXN];bool rev[MAXN];inline int read(){int ret=0,flag=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') flag=-1;ch=getchar();}while (ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}return ret*flag;}inline void pushup(int k){int l=t[k][0],r=t[k][1];mx[k]=max(max(mx[l],mx[r]),a[k]);size[k]=size[l]+size[r]+1;}inline void pushdown(int k){int l=t[k][0],r=t[k][1],tg=tag[k];if (tg){tag[k]=0;if (l){tag[l]+=tg;mx[l]+=tg;a[l]+=tg;}if (r){tag[r]+=tg;mx[r]+=tg;a[r]+=tg;}}if (rev[k]){rev[k]=0;rev[l]^=1;rev[r]^=1;swap(t[k][0],t[k][1]);}}inline void rotate(int &k,int x){int y=fa[x],z=fa[y],l,r;if (t[y][0]==x) l=0;else l=1;r=l^1;if (k==y) k=x;else{if (t[z][0]==y) t[z][0]=x;else t[z][1]=x;}fa[x]=z;fa[y]=x;fa[t[x][r]]=y;t[y][l]=t[x][r];t[x][r]=y;pushup(y);pushup(x);}inline void splay(int &k,int x){while (x!=k){int y=fa[x],z=fa[y];if (y!=k){if ((t[y][0]==x)^(t[z][0]==y)) rotate(k,x);else rotate(k,y);}rotate(k,x);}}inline int find(int k,int rank){if (tag[k]||rev[k]) pushdown(k);int l=t[k][0],r=t[k][1];if (size[l]+1==rank) return k;else if (size[l]>=rank) return find(l,rank);else return find(r,rank-size[l]-1);}inline void add(int l,int r,int val){int x=find(rt,l),y=find(rt,r+2);splay(rt,x);splay(t[x][1],y);int z=t[y][0];tag[z]+=val;mx[z]+=val;a[z]+=val;}inline void reverse(int l,int r){int x=find(rt,l),y=find(rt,r+2);splay(rt,x);splay(t[x][1],y);rev[t[y][0]]^=1;}inline void query(int l,int r){int x=find(rt,l),y=find(rt,r+2);splay(rt,x);splay(t[x][1],y);printf("%d\n",mx[t[y][0]]);}inline void build(int l,int r,int last){if (l>r) return;if (l==r){fa[l]=last;size[l]=1;if (l<last) t[last][0]=l;else t[last][1]=l;return;}int mid=(l+r)>>1;build(l,mid-1,mid);build(mid+1,r,mid);fa[mid]=last;pushup(mid);if (mid<last) t[last][0]=mid;else t[last][1]=mid;}int main(){mx[0]=-INF;n=read();m=read();build(1,n+2,0);rt=(n+3)>>1;F(i,1,m){int flag=read(),l=read(),r=read(),val;if (flag==1){val=read();add(l,r,val);}else if (flag==2) reverse(l,r);else query(l,r);}return 0;}
家!甜蜜的家!天下最美好的莫过於家
