[SCOI2014]方伯伯的OJ，洛谷P3285，splay

[SCOI2014]方伯伯的OJ，洛谷P3285，splay

正题

      方伯伯为什么要搞一个OJ呢emm

      强制在线又要加修改操作，明显想到伸展树动态开点。

      把编号理解成权值。

      一开始所有的权值就是排名。

     我们把排名连续且权值连续的看作为一个点（要是要改权值那就拿两个map映射一下）。

     每次有k操作就把一个点拆成[1,k-1],[k,k],[k+1,n]那么最多就有3m个点不会爆空间。

     同时我们要维护一个点在哪个区间，用set记录即可。

     可是无辜T了6个点，暂时想不到什么优化，留坑。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<set>
#include<map>
using namespace std;int n,m;
struct node{int y,d;bool operator<(node q)const{return y<q.y;}
};
set<node> f;
set<node>::iterator it;
map<int , int> image,fact;
map<int , int>::iterator p;
struct tree{int son[2],f,t;int l,r;
}s[1000010];
int root=1;
int tot=1;
int k;void update(int x){s[x].t=s[s[x].son[0]].t+s[s[x].son[1]].t+s[x].r-s[x].l+1;
}int findsomething(int x){p=image.lower_bound(x);if(p=&#d() || p->first!=x)k=x;else k=p->second;it=f.lower_bound((node){k,0});return it->d;
}void rotate(int x,int w){int f=s[x].f,ff=s[f].f;s[f].son[1-w]=s[x].son[w];if(s[x].son[w]!=0) s[s[x].son[w]].f=f;if(s[ff].son[0]==f) s[ff].son[0]=x;else s[ff].son[1]=x;s[x].f=ff;s[f].f=x;s[x].son[w]=f;update(f);update(x);
}void splay(int x,int tar){while(s[x].f!=tar){int f=s[x].f,ff=s[f].f;if(ff==tar){if(s[f].son[0]==x) rotate(x,1);else rotate(x,0);}else{if(s[ff].son[0]==f){if(s[f].son[0]==x) {rotate(f,1);rotate(x,1);}else {rotate(x,0);rotate(x,1);}}else{if(s[f].son[0]==x) {rotate(x,1);rotate(x,0);}else {rotate(f,0);rotate(x,0);}}}}if(tar==0) root=x;
}int get_tot(int x){splay(x,0);return s[s[x].son[0]].t+k-s[x].l+1;
}void del(int x){int ip=x;if(s[ip].son[0]==0 && s[ip].son[1]==0) root=0;else if(s[ip].son[0]!=0 && s[ip].son[1]==0) {root=s[ip].son[0];s[s[ip].son[0]].f=0;}else if(s[ip].son[0]==0 && s[ip].son[1]!=0) {root=s[ip].son[1];s[s[ip].son[1]].f=0;}else{int p=s[ip].son[0];while(s[p].son[1]!=0) p=s[p].son[1];splay(p,ip);root=p;s[p].f=0;s[s[ip].son[1]].f=p;s[p].son[1]=s[ip].son[1];update(p);}
}void add(int x){if(s[x].l<k && k<s[x].r){tot++;s[tot].l=k+1;s[tot].r=s[x].r;s[x].r=k-1;s[tot].son[1]=s[x].son[1];s[x].son[1]=tot;s[tot].f=x;if(s[tot].son[1]!=0) s[s[tot].son[1]].f=tot;update(tot);update(x);f.insert((node){s[tot].r,tot});}else if(k==s[x].r && s[x].l<k){s[x].r=k-1;update(x);}else if(k==s[x].l && k<s[x].r){s[x].l=k+1;update(x);}else if(s[x].l==k && k==s[x].r){del(x);return ;}f.insert((node){s[x].r,x});
}void put_top(int x){splay(x,0);f.erase(it);add(x);if(root==0) {s[x].l=s[x].r=k;root=x;update(x);f.insert((node){s[x].r,x});}else{tot++;s[tot].l=s[tot].r=k;s[tot].son[0]=s[tot].son[1]=0;int now=root;while(s[now].son[0]!=0) now=s[now].son[0];s[now].son[0]=tot;s[tot].f=now;f.insert((node){s[tot].r,tot});update(tot);update(now);while(s[now].f!=0) {now=s[now].f;update(now);}}
}void put_end(int x){splay(x,0);f.erase(it);add(x);tot++;if(root==0) {s[x].l=s[x].r=k;root=x;update(x);f.insert((node){s[x].r,x});}else{tot++;s[tot].l=s[tot].r=k;s[tot].son[0]=s[tot].son[1]=0;int now=root;while(s[now].son[1]!=0) now=s[now].son[1];s[now].son[1]=tot;s[tot].f=now;f.insert((node){s[tot].r,tot});update(tot);update(now);while(s[now].f!=0) {now=s[now].f;update(now);}}
}int find_num(int x){int now=root;while(1){if(x<=s[s[now].son[0]].t) now=s[now].son[0];else if(x>s[s[now].son[0]].t+s[now].r-s[now].l+1) x-=s[s[now].son[0]].t+s[now].r-s[now].l+1,now=s[now].son[1];else break;}return x-s[s[now].son[0]].t+s[now].l-1;
}int main(){scanf("%d %d",&n,&m);f.insert((node){n,1});s[1].son[0]=s[1].son[1]=0;s[1].f=0;s[1].t=n;s[1].l=1,s[1].r=n;s[0].t=0;int t,x,y;int op;int last=0;for(int i=1;i<=m;i++){scanf("%d %d",&t,&x);if(t==1) scanf("%d",&y);	x-=last,y-=last;if(t==1){op=findsomething(x);last=get_tot(op);printf("%dn",last);image[y]=k;fact[k]=ase(x);}else if(t==2){op=findsomething(x);last=get_tot(op);printf("%dn",last);put_top(op);}else if(t==3){op=findsomething(x);last=get_tot(op);printf("%dn",last);put_end(op);}else if(t==4){last=find_num(x);p=fact.lower_bound(last);if(p=&#d() || p->first!=last);else last=p->second;printf("%dn",last);}}
}