P3391 【模板】文艺平衡树 —— FHQ Treap 区间反转模板

This way

题意：

题解：

存一个模板，先将l~r这个区间的treap分离出来，然后在根打上翻转标记，然后在merge,split,dfs等遍历树的时候先执行push_down，照旧还是用了并查集随机树的形状 当然，在数据范围特别大的时候，并查集会导致空间范围扩大很多，于是可以用另一种写法，并且由于用了mt19937，效率也是比较高的：

unordered_map<int,bool>vis; //int finds(int x){return fa.count(x)?fa[x]=finds(fa[x]):x;} int newnode(int v){ siz[++tot]=1;// 新开辟一个节点 val[tot]=v; int r=rnd(); while(vis.count(r))r=rnd(); pri[tot]=r; vis[r]=1; return tot; }

区间翻转的话，是按照位置进行建树，然后就像主席树一样查找第k大就行了

#include<bits/stdc++.h> using namespace std; const int N=2e5+5; int ch[N][2];// 0左孩子 1右孩子 int val[N];// 每一个点的权值 int pri[N];// 随机生成的附件权值 int siz[N];// 以i为节点的树的节点数量 int tot;// 总结点的数量 int f[N];//翻转标记 mt19937 rnd(time(NULL)); void update(int x){ siz[x]=1+siz[ch[x][0]]+siz[ch[x][1]]; } void push_down(int x){ swap(ch[x][0],ch[x][1]); if(ch[x][0]) f[ch[x][0]]^=1; if(ch[x][1]) f[ch[x][1]]^=1; f[x]=0; } unordered_map<int,int>fa; int finds(int x){return fa.count(x)?fa[x]=finds(fa[x]):x;} int newnode(int v){ siz[++tot]=1;// 新开辟一个节点 val[tot]=v; pri[tot]=finds(rnd()); fa[pri[tot]]=finds(pri[tot]+1); return tot; } int merge(int x,int y){ if(!x||!y)return x+y; if(f[x])push_down(x); if(f[y])push_down(y); if(pri[x]<pri[y]){ ch[x][1]=merge(ch[x][1],y); update(x); return x; } else { ch[y][0]=merge(x,ch[y][0]); update(y); return y; } } void split(int rt,int k,int &x,int &y){ if(!rt)x=y=0; else { if(f[rt])push_down(rt); if(siz[ch[rt][0]]+1<=k) x=rt,split(ch[rt][1],k-siz[ch[rt][0]]-1,ch[rt][1],y); else y=rt,split(ch[rt][0],k,x,ch[rt][0]); update(rt); } } void dfs(int rt){ if(f[rt])push_down(rt); if(ch[rt][0])dfs(ch[rt][0]); printf("%d ",val[rt]); if(ch[rt][1])dfs(ch[rt][1]); } int main() { int n,m; scanf("%d%d",&n,&m); int rt=0; for(int i=1;i<=n;i++) rt=merge(rt,newnode(i)); //dfs(rt); while(m--){ int l,r,x,y,z; scanf("%d%d",&l,&r); split(rt,l-1,x,y); split(y,r-l+1,y,z); f[y]^=1; rt=merge(x,merge(y,z)); } dfs(rt); return 0; }