fhqtreap的写法 操作其实都差不多哇
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=;
int read(){
int ans=,f=,c=getchar();
while(c<''||c>''){if(c=='-') f=-; c=getchar();}
while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}
return ans*f;
}
int n,m,sum;
struct node{
node *l,*r;
int sz,v,rnd,rev,tag,mn;
void init(int w){sz=; v=w; rnd=rand(); mn=w;}
void add(int w){tag+=w; v+=w; mn+=w;}
void revs(){rev^=; swap(l,r);}
void up(){
sz=; mn=v;
if(l) sz+=l->sz,mn=min(mn,l->mn);
if(r) sz+=r->sz,mn=min(mn,r->mn);
}
void dn(){
if(rev){if(l) l->revs(); if(r) r->revs(); rev=;}
if(tag){if(l) l->add(tag); if(r) r->add(tag); tag=;}
}
void split(node*&lw,node*&rw,int k){
if(!this){lw=; rw=; return ;}
dn();
int ls=l?l->sz:;
if(ls>=k){
l->split(lw,l,k);
rw=this;
}
else{
r->split(r,rw,k-ls-);
lw=this;
}
up();
}
}tr[M],*rt;
node *merge(node *a,node *b){
if(!a) return b;
if(!b) return a;
if(a->rnd>b->rnd){
a->dn();
a->r=merge(a->r,b);
a->up();
return a;
}{
b->dn();
b->l=merge(a,b->l);
b->up();
return b;
}
}
int main()
{
int l,r,w;
char ch[];
n=read();
for(int i=;i<=n;i++) w=read(),tr[i].init(w),rt=merge(rt,tr+i);
sum=n; m=read();
while(m--){
scanf("%s",ch);
if(ch[]=='A'){
node *p1,*p2,*p3;
l=read(); r=read(); w=read();
rt->split(p2,p3,r);
p2->split(p1,p2,l-);
p2->add(w);
rt=merge(merge(p1,p2),p3);
}
else if(ch[]=='M'){
node *p1,*p2,*p3;
l=read(); r=read();
rt->split(p2,p3,r);
p2->split(p1,p2,l-);
printf("%d\n",p2->mn);
rt=merge(merge(p1,p2),p3);
}
else if(ch[]=='R'&&ch[]=='R'){
node *p1,*p2,*p3;
l=read(); r=read();
if(l==r) continue;
rt->split(p2,p3,r);
p2->split(p1,p2,l-);
p2->revs();
rt=merge(merge(p1,p2),p3);
}
else if(ch[]=='O'){
node *p1,*p2,*p3,*p4;
l=read(); r=read(); w=read()%(r-l+);
if(l==r) continue;
rt->split(p2,p4,r);
p2->split(p1,p2,l-);
p2->split(p2,p3,r-w-l+);
rt=merge(merge(p1,p3),merge(p2,p4));
}
else if(ch[]=='I'){
node *p1,*p2;
l=read(); w=read();
tr[++sum].init(w);
rt->split(p1,p2,l);
rt=merge(merge(p1,tr+sum),p2);
}
else if(ch[]=='D'){
node *p1,*p2,*p3;
l=read();
rt->split(p2,p3,l);
p2->split(p1,p2,l-);
rt=merge(p1,p3);
}
}
return ;
}