Tony Zhao

题目大意

请你维护一个序列，支持：插入一个数，删除一个数，反转子序列，“旋转”子序列（就是把后面的X个数取出来按原顺序放在前面）,查询子序列最小值，子序列统一加上某个数。

这道题可以用Splay来做，但是刚学Splay的菜鸡真的是太菜了以至于调试调到忘寝废食不亦乐乎qwq

总结一下遇到的问题和启示：

永远不要相信你的数组下标。无论如何你想知道一个东西在哪里，用lookfor(pos,tx)获取下标而不是直接放上去。
哨兵节点"1"和"N+2"是节点之二，所以必须要算上所有的节点，在添加新点的时候尤其注意不能覆盖，在访问节点的时候也要注意第X号节点是搜索第X+1号节点的返回值。
辣鸡数据。可能“旋转”操作做的“很过分”——超出了要覆盖的范围。必须要%一下转正之后进行处理否则TLE.
GDB大法好，单步调试保平安
%GXZlegend感谢dalao帮菜鸡调代码%%%%%

调试一个下午啊……想起了被DFS支配的恐惧qwq

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=300010;
int son[maxn][2],fa[maxn],siz[maxn],inx,iny,inz,root,n,m;
long long val[maxn],minn[maxn],laz[maxn];
char mode[maxn];
bool rev[maxn];
void reverse(int pos)
{
	swap(son[pos][0],son[pos][1]);
	rev[pos]^=1;
	return;
}
void pushup(int pos)
{
	siz[pos]=siz[son[pos][0]]+siz[son[pos][1]]+1;
	minn[pos]=min(val[pos],min(minn[son[pos][0]],minn[son[pos][1]]));
	return;
}
void pushdown(int pos)
{
	if(rev[pos])
	{
		reverse(son[pos][0]),reverse(son[pos][1]);
		rev[pos]=0;
	}
	if(laz[pos])
	{
		minn[son[pos][0]]+=laz[pos],minn[son[pos][1]]+=laz[pos];
		val[son[pos][0]]+=laz[pos],val[son[pos][1]]+=laz[pos];
		laz[son[pos][0]]+=laz[pos],laz[son[pos][1]]+=laz[pos];
		laz[pos]=0;
	}
	return;
}
void rotate(int &rt,int x)
{
    int y=fa[x],z=fa[y],l=(son[y][1]==x),r=l^1;
    if(y==rt) rt=x;
    else son[z][son[z][1]==y]=x;
    fa[x]=z,fa[y]=x,fa[son[x][r]]=y,son[y][l]=son[x][r],son[x][r]=y;
    pushup(y),pushup(x);
}
void splay(int &k , int x)
{
    while(x != k)
    {
        int y = fa[x] , z = fa[y];
        if(y != k)
        {
            if((son[y][0] == x) ^ (son[z][0] == y)) rotate(k , x);
            else rotate(k , y);
        }
        rotate(k , x);
    }
}
void build(int l,int r,int rt)
{
	if(l>r) return;
	int mid=(l+r)>>1;
	build(l,mid-1,mid),build(mid+1,r,mid);
	fa[mid]=rt;
	son[rt][mid>rt]=mid;
	pushup(mid);
	return;
}
int lookfor(int pos,int tx)
{
	pushdown(pos);
	if(tx<=siz[son[pos][0]]) return lookfor(son[pos][0],tx);
	if(tx>siz[son[pos][0]]+1) return lookfor(son[pos][1],tx-siz[son[pos][0]]-1);
	return pos;
}
int split(int tx,int ty)
{
	splay(root,lookfor(root,tx)),splay(son[root][1],lookfor(root,ty+2));
	return son[son[root][1]][0];
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d",val+i+1);
	minn[0]=1<<30;
	build(1,n+2,0),root=(n+3)>>1;
	n+=2;
	scanf("%d",&m);
	while(m--)
	{
		scanf("%s",mode);
		switch(mode[0])
		{
			case 'A':
			{
				scanf("%d%d%d",&inx,&iny,&inz);
				int tmp=split(inx,iny);
				val[tmp]+=inz;
				laz[tmp]+=inz;
				minn[tmp]+=inz;
				pushup(son[root][1]);
				pushup(root);
				break;
			}
			case 'I':
			{
				scanf("%d%d",&inx,&inz);
				splay(root,lookfor(root,inx+1)),splay(son[root][1],lookfor(root,inx+2));
				++n;
				son[son[root][1]][0]=n;
				fa[n]=son[root][1];
				val[n]=inz;
				pushup(n);
				pushup(son[root][1]);
				pushup(root);
				break;
			}
			case 'D':
			{
				scanf("%d",&inx);
				int tmp=split(inx,inx);
				fa[tmp]=-1;
				son[son[root][1]][0]=0;
				pushup(son[root][1]);
				pushup(root);
				break;
			}
			case 'M':
			{
				scanf("%d%d",&inx,&iny);
				int tmp=split(inx,iny);
				printf("%lld\n",minn[tmp]);
				break;
			}
			default:
			{
				if(mode[4]=='R')
				{
					scanf("%d%d",&inx,&iny);
					reverse(split(inx,iny));
				}
				if(mode[4]=='L')
				{
					scanf("%d%d%d",&inx,&iny,&inz);
					inz%=iny-inx+1;
					if(inz<0) inz+=iny-inx+1;
					if(inz==0) continue;
					int tmp=split(iny-inz+1,iny);
					son[son[root][1]][0]=0;
					pushup(son[root][1]);
					pushup(root);
					split(inx,inx-1);
					fa[tmp]=son[root][1];
					son[son[root][1]][0]=tmp;
					pushup(son[root][1]);
					pushup(root);
				}
				break;
			}
		}
	}
	return 0;
}

BZOJ 1895 supermemo

题目大意