CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
题目链接 比较全面的一个题了，FhqTreap 真是好用啊。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
struct FhqTreap
{
struct Node
{
int ch[2],siz,rev;
ll key,val,min,add;
void REV()
{
rev^=1,swap(ch[0],ch[1]);
}
void ADD(ll v)
{
val+=v,min+=v,add+=v;
}
};
vector<Node> v;
int root;
FhqTreap():v(1),root(0) {}
void push_down(int k)
{
if(!k)return;
for(int i=0,*ch=v[k].ch; i<2; ++i)
if(ch[i])
{
v[ch[i]].ADD(v[k].add);
if(v[k].rev)v[ch[i]].REV();
}
v[k].add=v[k].rev=0;
}
void push_up(int k)
{
if(!k)return;
v[k].siz=1,v[k].min=v[k].val;
for(int i=0,*ch=v[k].ch; i<2; ++i)
if(ch[i])
v[k].siz+=v[ch[i]].siz,v[k].min=min(v[k].min,v[ch[i]].min);
}
int merge(int a,int b)
{
if(!a||!b)return a+b;
if(v[a].key<v[b].key)
return push_down(a),v[a].ch[1]=merge(v[a].ch[1],b),push_up(a),a;
return push_down(b),v[b].ch[0]=merge(a,v[b].ch[0]),push_up(b),b;
}
void split(int a,int s,int &l,int &r)
{
if(!s)l=0,r=a;
else if(v[v[a].ch[0]].siz<s)
push_down(a),split(v[a].ch[1],s-v[v[a].ch[0]].siz-1,v[a].ch[1],r),push_up(l=a);
else
push_down(a),split(v[a].ch[0],s,l,v[a].ch[0]),push_up(r=a);
}
void push_back(ll d)
{
v.push_back(Node { {0,0},1,0,rand(),d,d,d});
root=merge(root,v.size()-1);
}
void insert(int x,ll d)
{
v.push_back(Node { {0,0},1,0,rand(),d,d,d});
int a,b,c;
split(root,x-1,a,b);
root=merge(merge(a,v.size()-1),b);
}
void erase(int x)
{
int a,b,c;
split(root,x,a,b),split(a,x-1,a,c),root=merge(a,b);
}
void add(int l,int r,ll d)
{
int a,b,c;
split(root,r,b,c),split(b,l-1,a,b),v[b].ADD(d),root=merge(merge(a,b),c);
}
Node ask(int l,int r)
{
int a,b,c;
split(root,r,b,c),split(b,l-1,a,b);
Node ret=v[b];
return root=merge(merge(a,b),c),ret;
}
void reverse(int l,int r)
{
int a,b,c;
split(root,r,b,c),split(b,l-1,a,b),v[b].REV(),root=merge(merge(a,b),c);
}
void revolve(int l,int r,int d)
{
int a,b,c,e=r-l+1;
split(root,r,b,c),split(b,l-1,a,b),split(b,(e-d%e)%e,b,e);
root=merge(merge(a,merge(e,b)),c);
}
};
int main()
{
int n,x,y,d;
char s[9];
FhqTreap t;
for(scanf("%d",&n); n--;)scanf("%d",&d),t.push_back(d);
for(scanf("%d",&n); n--;)
{
scanf("%s%d",s,&x);
if(s[0]=='A')scanf("%d%d",&y,&d),t.add(x,y,d);
else if(s[0]=='I')scanf("%d",&d),t.insert(x+1,d);
else if(s[0]=='D')t.erase(x);
else if(s[0]=='M')scanf("%d",&y),printf("%d\n",t.ask(x,y).min);
else if(s[3]=='E')scanf("%d",&y),t.reverse(x,y);
else scanf("%d%d",&y,&d),t.revolve(x,y,d);
}
}