bzoj1895: Pku3580 supermemo

傳送門

發現題目中的所有東西都可以用splay維護

然後就理所應當的成了splay裸題了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cmath>
#define N 300030
using namespace std;
int n,m,x,y,d,t,p,rt,cnt;
int a[N],f[N],ch[N][],sz[N],mn[N],key[N],add[N],rev[N];
char s[];
void clear(int x){
    f[x]=ch[x][]=ch[x][]=sz[x]=;
    mn[x]=key[x]=add[x]=rev[x]=;
}
int get(int x){
    return ch[f[x]][]==x;
}
void update(int x){
    sz[x]=sz[ch[x][]]+sz[ch[x][]]+;
    mn[x]=key[x];
    if (ch[x][]) mn[x]=min(mn[x],mn[ch[x][]]);
    if (ch[x][]) mn[x]=min(mn[x],mn[ch[x][]]);
}
void pushdown(int x){
    if (!x) return;
    if (rev[x]){
        rev[ch[x][]]^=;
        rev[ch[x][]]^=;
        swap(ch[x][],ch[x][]);
        rev[x]=;
    }
    if (add[x]){
        add[ch[x][]]+=add[x],add[ch[x][]]+=add[x];
        key[ch[x][]]+=add[x],key[ch[x][]]+=add[x];
        mn[ch[x][]]+=add[x],mn[ch[x][]]+=add[x];
        add[x]=;
    }
}
int build(int l,int r,int fa){
    if (l>r) return ;
    int mid=(l+r)/,x=++cnt;
    f[x]=fa; key[x]=a[mid];
    ch[x][]=build(l,mid-,x);
    ch[x][]=build(mid+,r,x);
    update(x);
    return x;
}
void rotate(int x){
    pushdown(f[x]); pushdown(x);
    int y=f[x],z=f[y],l=get(x),r=l^;
    if (z) ch[z][get(y)]=x;
    f[x]=z; f[y]=x; f[ch[x][r]]=y;
    ch[y][l]=ch[x][r]; ch[x][r]=y;
    update(y); update(x);
}
void splay(int x,int tar){
    for (;f[x]!=tar;rotate(x))
        if (f[f[x]]!=tar)
            rotate(get(x)==get(f[x])?f[x]:x);
    if (!tar) rt=x;
}
int find(int rk){
    int x=rt;
    while(){
        pushdown(x);
        if (rk<=sz[ch[x][]]) x=ch[x][];
        else{
            rk-=sz[ch[x][]]+;
            if (!rk) return x;
            x=ch[x][];
        }
    }
}
void pre(int x,int y){
    int a=find(x),b=find(y);
    splay(a,); splay(b,a);
}
void up(){
    update(ch[rt][]);
    update(rt);
}
int main(){
    scanf("%d",&n);
    a[]=; a[n+]=-;
    for (int i=;i<=n+;i++) scanf("%d",&a[i]);
    rt=build(,n+,);
    scanf("%d",&m);
    while (m--){
        scanf("%s",s);
        if (s[]=='A'){
            scanf("%d%d%d",&x,&y,&d);
            if (x>y) swap(x,y);
            pre(x,y+);
            mn[ch[ch[rt][]][]]+=d;
            add[ch[ch[rt][]][]]+=d;
            key[ch[ch[rt][]][]]+=d;
            up();
        }
        else if (s[]=='I'){
            scanf("%d%d",&x,&p);
            pre(x+,x+);
            ch[ch[rt][]][]=++cnt;
            f[cnt]=ch[rt][];
            key[cnt]=mn[cnt]=p;
            sz[cnt]=;
            up();
        }
        else if (s[]=='D'){
            scanf("%d",&x);
            pre(x,x+);
            int del=ch[ch[rt][]][];
            clear(del);
            ch[ch[rt][]][]=;
            up(); 
        }
        else if (s[]=='M'){
            scanf("%d%d",&x,&y);
            if (x>y) swap(x,y);
            pre(x,y+);
            printf("%d\n",mn[ch[ch[rt][]][]]);
        }
        else if (s[]=='E'){
            scanf("%d%d",&x,&y);
            if (x==y) continue;
            pre(x,y+);
            rev[ch[ch[rt][]][]]^=;
        }
        else{
            scanf("%d%d%d",&x,&y,&t);
            if (x>y) swap(x,y);
            t%=(y-x+);
            if (!t) continue;
            pre(y-t+,y+);
            int now=ch[ch[rt][]][];
            ch[ch[rt][]][]=;
            up();
            pre(x,x+);
            ch[ch[rt][]][]=now;
            f[now]=ch[rt][];
            up();
        }
    }
}