P9741 题解
前言
大家好，本人并没有推出规律，但正好前几天学习了文艺平衡树，于是使用 FHQ-Treap 实现的文艺平衡树通过了本题。
前置知识：普通平衡树，文艺平衡树。
做法
模拟题意可知，维护一个
明显可以使用文艺平衡树来处理这个问题。
使用文艺平衡树维护一个
- 按下标翻转，很明显可以使用文艺平衡树自带的操作完成。
- 按值翻转，可以维护一个懒标记表示以这个点为根节点的子树内是否需要翻转权值，在下传操作时下传懒标记并翻转当前节点的权值。
#include<bits/stdc++.h>
using namespace std;
namespace wxh666{
#define f(a,b,c) for(int a=b;a<=c;a++)
#define ff(a,b,c) for(int a=b;a>=c;a--)
#define g(n) f(i,1,n)
#define df(n,m) g(n) f(j,1,m)
inline int read()
{
char ch=getchar();int f=1,ans=0;
for(;!isdigit(ch);ch=getchar()) ch=='-'?f=-1:f=1;
for(;isdigit(ch);ch=getchar()) ans=(ans<<3)+(ans<<1)+(ch&15);
return f*ans;
}
#define in read()
};using namespace wxh666;
mt19937 R(time(0));
inline int rnd(int l,int r){
return (R()>>1)%(r-l+1)+l;
}
struct FHQ_Treap{
struct node{
int l,r;
int val,key;
int size;
int lan,lann;//第一个标记按下标翻转，第二个标记按值翻转
}t[2000005];
int root,cnt;
inline int newnode(int v)
{
t[++cnt].val=v;
t[cnt].key=rnd(1,2e6);
t[cnt].size=1;
return cnt;
}
inline void pushup(int p)
{
t[p].size=t[t[p].l].size+t[t[p].r].size+1;
return;
}
inline void pushdown(int p)
{
if(t[p].lann)//处理按值翻转
{
t[p].val^=1;
t[t[p].l].lann^=1;
t[t[p].r].lann^=1;
t[p].lann=0;
}
if(!t[p].lan) return;
swap(t[p].l,t[p].r);//处理按下标翻转
t[t[p].l].lan^=1;
t[t[p].r].lan^=1;
t[p].lan=0;
}
void split(int p,int v,int &x,int &y)
{
if(!p) {x=y=0;return;}
pushdown(p);
if(v>t[t[p].l].size)
x=p,split(t[x].r,v-t[t[p].l].size-1,t[p].r,y);
else y=p,split(t[p].l,v,x,t[y].l);
pushup(p);
return;
}
int merge(int x,int y)
{
if(!x||!y) return x+y;
if(t[x].key<t[y].key)
{
pushdown(x);
t[x].r=merge(t[x].r,y);
pushup(x);return x;
}
else
{
pushdown(y);
t[y].l=merge(x,t[y].l);
pushup(y);return y;
}
}
void insert(int v)
{
root=merge(root,newnode(v));
return;
}
void output(int p)
{
if(!p) return;
pushdown(p);
output(t[p].l);
printf("%d ",t[p].val);
output(t[p].r);
}
}tr;
int n,m;
int x,y;
int main()
{
cin>>n;
g(n) tr.insert(in);
g(n)
{
int a,b;
tr.split(tr.root,i,a,b);
tr.t[a].lan^=1;//按下标翻转
tr.t[a].lann^=1;//按值翻转
tr.root=tr.merge(a,b);
}
tr.output(tr.root);
return 0;
}后记
由于平衡树的巨大常数以及