这道题要求区间反转。。。好东西。。
对于Splay：把l-1旋到根，把r+1旋到根的右儿子，这样r+1的左儿子就是整个区间了，然后对这个区间打个tg
注意要插-Inf和Inf到树里面，防止越界，坐标要+1
#include<cstdio>
#include<iostream>
#define R register int
using namespace std;
const int N=,Inf=0x3f3f3f3f;
inline int g() {
R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;
do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;
}
int n,m,tot,rt;
struct node{
int fa,ch[],sz,tg,vl;
#define fa(x) t[x].fa
#define ch(x,i) t[x].ch[i]
#define sz(x) t[x].sz
#define tg(x) t[x].tg
#define vl(x) t[x].vl
#define ls ch(x,0)
#define rs ch(x,1)
}t[N];
inline void upd(int x) {sz(x)=sz(ls)+sz(rs)+;}
inline void spread(int x) {if(tg(x)) tg(ls)^=,tg(rs)^=,tg(x)=,swap(ls,rs);}
inline void rot(int x) {
R y=fa(x),d=ch(y,)==x;
if(fa(y)) ch(fa(y),ch(fa(y),)==y)=x;
fa(x)=fa(y); fa(ch(y,d)=ch(x,d^))=y;
fa(ch(x,d^)=y)=x; upd(y);
}
inline void Splay(int x,int f) {
while(fa(x)!=f) {
R y=fa(x); if(fa(y)!=f)
rot((ch(y,)==x)==(ch(fa(y),)==y)?y:x);
rot(x);
} upd(x); if(!f) rt=x;
}
inline int build(int f,int l,int r) {
if(l>r) return ; R md=l+r>>,x=++tot;
fa(x)=f,++sz(x),vl(x)=md-;
ls=build(x,l,md-);rs=build(x,md+,r);
upd(x); return x;
}
inline int get(int pos) { R x=rt;
while() {spread(x); R s=sz(ls);
if(pos==s+) return x;
if(pos<=s) x=ls;
else x=rs,pos-=(s+);
}
}
inline void reverse(int l,int r) {
l=get(l),r=get(r+);
Splay(l,),Splay(r,l); tg(ch(r,))^=;
} int s;
inline void print(int x) { spread(x);
if(!x) return ; print(ls);
if(vl(x)>=&&vl(x)<=n) printf("%d ",vl(x)); print(rs);
}
signed main() {
n=g(),m=g(); rt=build(,,n+);
for(R i=;i<=m;++i) {R l=g(),r=g(); reverse(l,r);}
print(rt); putchar('\n');
}
对于FHQ Treap，先把[1,l-1]和[l,n]split出来，再把[l,r]和[r+1,n]split出来，在代表区间的子树的根节点打tg，注意这道题的的split是按rank的
不过split完忘了upd。。。我真实沙雕qwq。。。
#include<cstdio>
#include<iostream>
#include<cstdlib>
#define R register int
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]
using namespace std;
const int N=;
inline int g() {
R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;
do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;
}
int n,m,tot,rt;
int ch[N][],sz[N],vl[N],dat[N];
bool tg[N];
inline void upd(int x) {sz[x]=sz[ls(x)]+sz[rs(x)]+;}
inline int cre(int v) {R x=++tot; vl[x]=v,sz[x]=,dat[x]=rand(); upd(x); return x;}
inline void spread(int x) {if(tg[x]) swap(ls(x),rs(x)),tg[ls(x)]^=,tg[rs(x)]^=,tg[x]=;}
inline void split(int o,int rk,int& x,int& y) {
if(!o) {x=y=; return ;} spread(o);
if(sz[ls(o)]<rk) {x=o; split(rs(o),rk-sz[ls(o)]-,rs(o),y); upd(x);}
else {y=o; split(ls(o),rk,x,ls(o)); upd(y);}
}
inline int merge(int x,int y) {
if(!x||!y) return x+y;
if(dat[x]<dat[y]) {spread(x); rs(x)=merge(rs(x),y); upd(x); return x;}
else {spread(y); ls(y)=merge(x,ls(y)); upd(y); return y;}
}
inline void print(int x) {if(!x) return ; spread(x); print(ls(x)); printf("%d ",vl[x]); print(rs(x));}
signed main() { srand();
n=g(),m=g(); for(R i=;i<=n;++i) rt=merge(rt,cre(i)); R x=,y=,z=;
for(R i=;i<=m;++i) { R l=g(),r=g();
split(rt,l-,x,y); split(y,r-l+,y,z); tg[y]^=; rt=merge(x,merge(y,z));
} print(rt); while();
}
2019.05.06