题目链接

splay:

 #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+,inf=0x3f3f3f3f;
int ch[N][],val[N],siz[N],rev[N],tot,n,m,a[N],rt;
int newnode(int x) {int u=++tot; val[u]=x,siz[u]=,ch[u][]=ch[u][]=rev[u]=; return u;}
void pu(int u) {siz[u]=siz[ch[u][]]+siz[ch[u][]]+;}
void pd(int u) {if(rev[u])rev[u]=,swap(ch[u][],ch[u][]),rev[ch[u][]]^=,rev[ch[u][]]^=;}
void rot(int& u,int f) {
int v=ch[u][f];
ch[u][f]=ch[v][f^],ch[v][f^]=u;
pu(u),pu(v),u=v;
}
void splay(int& u,int k) {
pd(u);
if(siz[ch[u][]]+!=k) {
int f=k>siz[ch[u][]]+;
if(f)k-=siz[ch[u][]]+;
int& v=ch[u][f];
pd(v);
if(siz[ch[v][]]+!=k) {
int ff=k>siz[ch[v][]]+;
if(ff)k-=siz[ch[v][]]+;
splay(ch[v][ff],k),f==ff?rot(u,f):rot(v,ff);
}
rot(u,f);
}
}
void sp(int& u,int k,int& v) {splay(u,k),v=ch[u][],ch[u][]=,pu(u);}
void mg(int& u,int v) {splay(u,siz[u]),ch[u][]=v,pu(u);}
void rv(int& u,int l,int r) {
int lv,rv;
sp(u,r,rv),sp(u,l-,lv);
rev[lv]^=;
mg(u,lv),mg(u,rv);
}
#define mid ((l+r)>>1)
void build(int& u,int l=,int r=n) {
if(l>r) {u=; return;}
u=newnode(a[mid]);
build(ch[u][],l,mid-),build(ch[u][],mid+,r),pu(u);
}
int f;
void dfs(int u) {
if(!u)return;
pd(u);
dfs(ch[u][]);
if(val[u]!=) {
f?f=:printf(" ");
printf("%d",val[u]);
}
dfs(ch[u][]);
}
int main() {
scanf("%d%d",&n,&m);
for(int i=; i<=n; ++i)a[i]=i;
a[]=,build(rt);
while(m--) {
int l,r;
scanf("%d%d",&l,&r);
rv(rt,l+,r+);
}
f=,dfs(rt);
return ;
}

无旋treap(FHQ-treap):

 #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+,inf=0x3f3f3f3f;
int ch[N][],val[N],siz[N],rd[N],rev[N],tot,n,m,a[N],rt;
#define l(u) ch[u][0]
#define r(u) ch[u][1]
int newnode(int x) {int u=++tot; val[u]=x,siz[u]=,rd[u]=rand(),l(u)=r(u)=rev[u]=; return u;}
void flip(int u) {rev[u]^=,swap(l(u),r(u));}
void pu(int u) {siz[u]=siz[l(u)]+siz[r(u)]+;}
void pd(int u) {if(rev[u])rev[u]=,flip(l(u)),flip(r(u));}
void sp(int& u,int k,int& v) {
if(!u) {v=; return;}
pd(u);
if(k>=siz[l(u)]+)sp(r(u),k-(siz[l(u)]+),v),pu(u);
else v=u,u=l(u),sp(u,k,l(v)),pu(v);
}
void mg(int& u,int v) {
if(!u||!v) {u=u|v; return;}
if(rd[u]>rd[v])pd(u),mg(r(u),v);
else pd(v),mg(u,l(v)),l(v)=u,u=v;
pu(u);
}
void rv(int& u,int l,int r) {
int lv,rv;
sp(u,r,rv),sp(u,l-,lv);
flip(lv);
mg(u,lv),mg(u,rv);
}
int f;
void dfs(int u) {
if(!u)return;
pd(u);
dfs(l(u));
if(val[u]!=) {
f?f=:printf(" ");
printf("%d",val[u]);
}
dfs(r(u));
}
int main() {
srand(time());
scanf("%d%d",&n,&m);
rt=newnode();
for(int i=; i<=n; ++i)mg(rt,newnode(i));
while(m--) {
int l,r;
scanf("%d%d",&l,&r);
rv(rt,l+,r+);
}
f=,dfs(rt);
return ;
}
05-11 20:03
查看更多