FHQ 板子,自认为马蜂良好。
FHQ 缺点:常数大
FHQ 优点:只有常数大
首先,支持旋转操作的平衡树叫文艺平衡树,可用 FHQ 实现。
文艺平衡树是在给定的序列上操作,
我们无法按照权值 val 分裂合并,而是按照子树大小 size 分裂合并,这样才能分裂出需要操作的区间。
对于 add 和 min 操作:
FHQ 其实是可以当作线段树用的,对于区间操作,我们只需要下穿标记即可。可参考线段树。
对于 REVERSE l r 操作:
旋转两次相当于没有旋转。
我们下传 rev 标记,若 rev=1,则交换 lc 和 rc ,同时 rev[lc]^=1,rev[rc]^=1。
对于 REVOLVE l r T 操作:
在 l~r 区间内,定义区间长度为 n。
先考虑向右移动 n 位其实和原序列相同,所以先让 T%n。
然后我们发现,移动 T 位后,后面 T 个数移动到了前面来。
我们分裂前 n-T%n 个数,将这个区间放在后面,就完成了。
细节已标注释。
#include<iostream>
#include<cstring>
using namespace std;
const int N=2e5+5;
int n,m,rt,tot;
struct FHQ_Treap{
int lc[N],rc[N],v[N],s[N],p[N],mi[N],add[N],rev[N];
FHQ_Treap() {memset(mi,0x3f,sizeof(mi));}//初始 min 定义为极大值
inline int min(int x,int y) {return x<y?x:y;}
inline int New(int val)
{
++tot;//不要写成 v[++tot],不然会出现未定义错误 (debug_time+=40 min)
v[tot]=mi[tot]=val,s[tot]=1,p[tot]=rand();
return tot;
}
inline void pushup(int k)
{
//上传标记时更新 min 和 size
//为什么是 v[k] 而不是 mi[k]?当 lc[k] 和 rc[k] 变化的时候,之前的 mi[k] 可能已非法 (debug_time+=1.5 h)
mi[k]=min(v[k],min(mi[lc[k]],mi[rc[k]]));
s[k]=s[lc[k]]+s[rc[k]]+1;
}
inline void pushdown(int k)
{
//注意下传 add 的时候要更新三个值,并且这个儿子存在的时候才能下穿 (debug_time+=10min)
if(add[k])
{
int x=add[k];
if(lc[k]) add[lc[k]]+=x,v[lc[k]]+=x,mi[lc[k]]+=x;
if(rc[k]) add[rc[k]]+=x,v[rc[k]]+=x,mi[rc[k]]+=x;
add[k]=0;
}
if(rev[k])
{
swap(lc[k],rc[k]);
if(lc[k]) rev[lc[k]]^=1;
if(rc[k]) rev[rc[k]]^=1;
rev[k]=0;
}
}
void split(int k,int p,int &x,int &y)
{
if(!k) {x=y=0;return;}
//分裂之前下传标记
pushdown(k);
if(s[lc[k]]<p) //小于号:不要考虑掉了 k 这个节点本身
x=k,split(rc[k],p-s[lc[k]]-1,rc[x],y);
else
y=k,split(lc[k],p,x,lc[y]);
pushup(k);
}
int merge(int x,int y)
{
if(!x||!y) return x+y;
//为什么不同时下传 x和y ?
//我们一次 merge 只递归一棵子树
if(p[x]<p[y])
{
//合并之前下传标记
pushdown(x);
rc[x]=merge(rc[x],y);
pushup(x);
return x;
}
else
{
//合并之前下传标记
pushdown(y);
lc[y]=merge(x,lc[y]);
pushup(y);
return y;
}
}
inline void Insert(int p,int x)
{
//在 p 之后插入,分裂出 1~p 和 p+1~n 两个区间,插入即可
int a,b;
split(rt,p,a,b);
rt=merge(merge(a,New(x)),b);
}
inline void Delete(int p)
{
//删除时无需考虑重复的 val,因为我们是按下标操作的
int a,b,c;
split(rt,p,a,c);
split(a,p-1,a,b);
rt=merge(a,c);
}
inline void Add(int l,int r,int x)
{
int a,b,c;
split(rt,r,a,c);
split(a,l-1,a,b);
add[b]+=x,v[b]+=x,mi[b]+=x;
pushdown(b);
rt=merge(merge(a,b),c);
}
inline int Min(int l,int r)
{
int a,b,c,res;
split(rt,r,a,c);
split(a,l-1,a,b);
res=mi[b];
rt=merge(merge(a,b),c);
return res;
}
inline void rotate(int l,int r)
{
int a,b,c;
split(rt,r,a,c);
split(a,l-1,a,b);
rev[b]^=1;
rt=merge(merge(a,b),c);
}
inline void move(int l,int r,int k)
{
int a,b,c,d,n=r-l+1;
split(rt,r,a,d);
split(a,l-1,a,b);
k=n-k%n;
split(b,k,b,c);
rt=merge(merge(a,merge(c,b)),d);
}
}T;
inline int read()
{
int x=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^48);
return x;
}
int main()
{
n=read();
for(int i=1,x;i<=n;i++) x=read(),T.Insert(i,x);
m=read();
while(m--)
{
char s[10];scanf("%s",s+1);
int x=read(),y,z;
if(s[1]!='D') y=read();//小trick,除了Delete其他都读入至少两个数
if(s[1]=='A') z=read(),T.Add(x,y,z);
else if(s[1]=='R'&&s[4]=='E') T.rotate(x,y);
else if(s[1]=='R'&&s[4]=='O') z=read(),T.move(x,y,z);
else if(s[1]=='I') T.Insert(x,y);
else if(s[1]=='D') T.Delete(x);
else if(s[1]=='M') printf("%d\n",T.Min(x,y));
}
}