题目：
我是超链接
题解：
昂......真是抵制手残......数组开小了会T啊！开两倍啊！
这次还是按照位置排名的，find（x）为找到排名为x的数字编号，findval（x）为找到排名为x的数字的值。
实现了区间max操作
开虚拟点的技巧：左边的实际点变为x+1，右边变为x+y+1
代码：
#include <cstdio> #include <iostream> #include <cstring> #define N 100005 #define INF 1e9 using namespace std; int key[N],size[N],maxn[N],ch[N][2],f[N],root,sz,a[N]; bool get(int x){return ch[f[x]][1]==x;} void updata(int x) { if (x){ size[x]=1; maxn[x]=key[x]; if (ch[x][0]){ size[x]+=size[ ch[x][0] ]; maxn[x]=max(maxn[x],maxn[ ch[x][0] ]); } if (ch[x][1]){ size[x]+=size[ ch[x][1] ]; maxn[x]=max(maxn[x],maxn[ ch[x][1] ]); } } } void rotate(int x) { int old=f[x],oldf=f[old],which=get(x); ch[old][which]=ch[x][which^1]; f[ch[x][which^1]]=old; ch[x][which^1]=old; f[old]=x; f[x]=oldf; if (oldf) ch[oldf][ch[oldf][1]==old]=x; updata(old); updata(x); } void splay(int x,int tar) { for (int fa;(fa=f[x])!=tar;rotate(x)) if (f[fa]!=tar) rotate((get(x)==get(fa))?fa:x); if (tar==0) root=x; } int find(int x) { int now=root; while (1) { if (x<=size[ch[now][0]]) now=ch[now][0]; else { x-=size[ch[now][0]]+1; if (!x) return now; now=ch[now][1]; } } } int findval(int x) { int now=root; while (1) { if (x<=size[ch[now][0]]) now=ch[now][0]; else { x-=size[ch[now][0]]+1; if (!x) return key[now]; now=ch[now][1]; } } } void del(int x) {//x-1-x+1 int aa=find(x),bb=find(x+2); splay(aa,0); splay(bb,aa); ch[ch[root][1]][0]=0; updata(ch[root][1]); updata(root); } void insert(int x,int tar) {//x-1--x int aa=find(x),bb=find(x+1); splay(aa,0); splay(bb,aa); ch[ch[root][1]][0]=++sz; f[sz]=ch[root][1]; key[sz]=tar; size[sz]=1; maxn[sz]=tar; updata(ch[root][1]); updata(root); } void yd(int a,int b) {//L-1-R+1 int x1=find(a),y1=find(b+2); splay(x1,0); splay(y1,x1); printf("%d\n",maxn[ch[ch[root][1]][0]]); updata(ch[root][1]); updata(root); } int build(int fa,int l,int r) { if (l>r) return 0; int mid=(l+r)>>1; int now=++sz; key[now]=a[mid]; f[now]=fa; maxn[now]=a[mid]; size[now]=1; ch[now][0]=build(now,l,mid-1); ch[now][1]=build(now,mid+1,r); updata(now); return now; } int main() { int n,m,i; scanf("%d%d",&n,&m); a[1]=-INF; a[n+2]=INF; for (i=1;i<=n;i++) scanf("%d",&a[i+1]); root=build(0,1,n+2); for (i=1;i<=m;i++) { int x,y;char chh; scanf("%d",&x); chh=getchar(); while (chh!='D' && chh!='L') chh=getchar(); scanf("%d",&y); if (chh=='D') { int ll=x+1,rr=x+y; yd(ll,rr); int val=findval(x+1); del(x); insert(rr,val); } else { int ll=x-y,rr=x-1; yd(ll,rr); int val=findval(x+1); del(x); insert(ll,val); } } }