@[mimi](/space/show?uid=36532) orzc
by WA鸭鸭 @ 2018-12-22 22:34:44
有毒吧
by localhost @ 2018-12-22 22:35:18
我只是想知道怎么写
by localhost @ 2018-12-22 22:35:39
其他人写的都是splay
by localhost @ 2018-12-22 22:35:51
一样的呀
by dodo @ 2018-12-26 22:02:21
```cpp
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
for(;!isdigit(ch);ch=='-'?f=-1:0,ch=getchar());
for(;isdigit(ch);x=x*10+ch-'0',ch=getchar());
return x*f;
}
struct T{int l,r;}treap[400005];
int pri[400005],size[400005],ls[400005],rs[400005],fa[400005],cnt,R,last;
map<int,int>mp;
void Update(int p){size[p]=size[ls[p]]+size[rs[p]]+treap[p].r-treap[p].l+1;}
void Split(int p,int k,int&rt1,int&rt2){
if(!p){rt1=rt2=0;return;}
if(k<=size[ls[p]])Split(ls[p],k,rt1,rt2),ls[p]=rt2,rt2=fa[rt2]=p;
else Split(rs[p],k-size[ls[p]]-treap[p].r+treap[p].l-1,rt1,rt2),rs[p]=rt1,rt1=fa[rt1]=p;
Update(p);
}
int Merge(int rt1,int rt2){
if(!rt1)return rt2;if(!rt2)return rt1;
if(pri[rt1]<pri[rt2]){int son=rs[rt1]=Merge(rs[rt1],rt2);fa[son]=rt1;Update(rt1);return rt1;}
else{int son=ls[rt2]=Merge(rt1,ls[rt2]);fa[son]=rt2;Update(rt2);return rt2;}
}
void Insert(int rk,int l,int r){
treap[++cnt]={l,r};
size[cnt]=r-l+1;pri[cnt]=rand();
mp[l]=cnt;
int rt1,rt2;
Split(R,rk-1,rt1,rt2);
R=Merge(Merge(rt1,cnt),rt2);
}
void Del(int l,int r){
int rt1,rt2,rt3,d;
Split(R,r,rt1,rt2);
Split(rt1,l-1,rt3,d);
R=Merge(rt3,rt2);
}
int Find(int p){
int res=size[p]-size[rs[p]];
while(p!=R){
if(rs[fa[p]]==p)res+=size[fa[p]]-size[rs[fa[p]]];
p=fa[p];
}
return res;
}
int Kth(int p,int k){
if(k<=size[ls[p]])return Kth(ls[p],k);
k-=size[ls[p]];
if(k-treap[p].r+treap[p].l-1<=0)return treap[p].l+k-1;
return Kth(rs[p],k-treap[p].r+treap[p].l-1);
}
int n,m,opt,x;
int main(){
srand(time(0));
n=read();m=read();
mp[1]=1;
Insert(1,1,n);
for(int i=1;i<=m;++i){
int opt=read(),x=read()-last,y;
if(opt==1){
y=read()-last;
int l=(--mp.lower_bound(x+1))->first;
int p=mp[l],r=treap[p].r;
int rk=last=Find(p)-r+x;
printf("%d\n",rk);
Del(rk-x+l,rk+r-x);
if(x>l)Insert(rk-x+l,l,x-1);
Insert(rk,y,y);
if(r>x)Insert(rk+1,x+1,r);
}
else if(opt==2){
int l=(--mp.lower_bound(x+1))->first;
int p=mp[l],r=treap[p].r;
int rk=last=Find(p)-r+x;
printf("%d\n",rk);
Del(rk-x+l,rk+r-x);
if(x>l)Insert(rk-x+l,l,x-1);
if(r>x)Insert(rk,x+1,r);
Insert(1,x,x);
}
else if(opt==3){
int l=(--mp.lower_bound(x+1))->first;
int p=mp[l],r=treap[p].r;
int rk=last=Find(p)-r+x;
printf("%d\n",rk);
Del(rk-x+l,rk+r-x);
if(x>l)Insert(rk-x+l,l,x-1);
if(r>x)Insert(rk,x+1,r);
Insert(n,x,x);
}
else printf("%d\n",last=Kth(R,x));
}
}
```
by dodo @ 2018-12-27 13:09:55
@[mimi](/space/show?uid=36532)
by dodo @ 2018-12-27 13:14:19
thx！！！
by localhost @ 2018-12-28 15:56:58
原来map可以这么用
by localhost @ 2018-12-28 15:58:11
哦对，还可以加一个垃圾回收
by localhost @ 2018-12-28 23:55:54