CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
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
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
struct FhqTreap
{
struct Node
{
int ch[2], siz, rev;
ll key, val, max, add;
void REV()
{
rev ^= 1, swap(ch[0], ch[1]);
}
void ADD(ll v)
{
val += v, max += 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].max = 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].max = max(v[k].max, v[ch[i]].max);
}
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 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);
}
};
int main()
{
int n, k, l, r;
FhqTreap t;
for (scanf("%d", &n); n--;)
t.push_back(0);
for (scanf("%d", &n); n--;)
{
scanf("%d%d%d", &k, &l, &r);
if (k == 1)
scanf("%d", &k), t.add(l, r, k);
else if (k == 2)
t.reverse(l, r);
else
printf("%d\n", t.ask(l, r).max);
}
}