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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
|
#include <bits/stdc++.h>
using namespace std;
struct treap
{
typedef long long T;
treap *left = nullptr, *right = nullptr;
int rank, items = 1;
bool rev = false;
T value, sum;
treap(T val = T()) : value(val), sum(val), rank(rand()) { }
inline void update()
{
if(rev)
{
swap(left, right);
if(left) left->rev = !left->rev;
if(right) right->rev = !right->rev;
rev = false;
}
}
};
inline int items(treap *t) { return t ? t->items : 0; }
inline treap::T sum(treap *t) { return t ? t->sum : 0; }
inline void recalc(treap *t) {
t->items = items(t->left) + items(t->right) + 1;
t->sum = sum(t->left) + sum(t->right) + t->value;
}
pair<treap*, treap*> split(treap *t, int k) //dzieli na prefiks dlugosci k i reszte
{
if(!t) return make_pair(nullptr, nullptr);
//t = new treap(*t); //odkomentowac zeby zrobic strukture trwala
t->update();
if(items(t->left) < k)
{
auto p = split(t->right, k - items(t->left) - 1);
t->right = p.first;
recalc(t);
return make_pair(t, p.second);
}
else
{
auto p = split(t->left, k);
t->left = p.second;
recalc(t);
return make_pair(p.first, t);
}
}
treap* merge(treap *a, treap *b)
{
if(!a) return b;
if(!b) return a;
a->update();
b->update();
if(a->rank > b->rank) {
a->right = merge(a->right, b);
recalc(a);
return a;
}
else {
b->left = merge(a, b->left);
recalc(b);
return b;
}
}
treap::T select(treap *t, int k) //zwraca k-ty element
{
if(!t) return treap::T();
t->update();
int i = items(t->left);
if(i == k) return t->value;
if(i > k) return select(t->left, k);
return select(t->right, k - i - 1);
}
treap* insert(treap *t, treap::T val, int k) //wstaw val na pozycje k (liczac od 0)
{
auto p = split(t, k);
return merge(merge(p.first, new treap(val)), p.second);
}
void write(treap *t)
{
if(!t) return;
t->update();
write(t->left);
cout << "(" << t->value << ", " << t->sum << ") ";
write(t->right);
}
treap* erase(treap *t, int k)
{
auto p1 = split(t, k);
auto p2 = split(p1.second, 1);
return merge(p1.first, p2.second);
}
treap* reverse(treap *t, int a, int b) //odwroc przedzial <a, b)
{
auto p1 = split(t, b);
auto p2 = split(p1.first, a);
if(p2.second) p2.second->rev = !p2.second->rev;
return merge(merge(p2.first, p2.second), p1.second);
}
treap::T sum(treap* t, int l, int r) {
auto p1 = split(t, r);
auto p2 = split(p1.first, l);
treap::T ret = sum(p2.second);
merge(merge(p2.first, p2.second), p1.second);
return ret;
}
treap *root = 0;
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
char c;
scanf(" %c", &c);
if (c == 'I') {
int p, x;
scanf("%d%d", &p, &x);
root = insert(root, x, p);
}
if (c == 'D') {
int p;
scanf("%d", &p);
root = erase(root, p - 1);
}
if (c == 'S') {
int l, r;
scanf("%d%d", &l, &r);
printf("%lld\n", sum(root, l - 1, r));
}
// cout << "Treap:\n";
// write(root);
// cout << "\n";
}
}
|
