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 | #include <bits/stdc++.h>
using i64 = long long;
template <typename T>
struct Fenwick {
int n;
std::vector<T> a;
Fenwick(int n = 0) {
init(n);
}
void init(int n) {
this->n = n;
a.assign(n, T());
}
void add(int x, T v) {
for (int i = x + 1; i <= n; i += i & -i) {
a[i - 1] += v;
}
}
T sum(int x) {
auto ans = T();
for (int i = x; i > 0; i -= i & -i) {
ans += a[i - 1];
}
return ans;
}
T rangeSum(int l, int r) {
return sum(r) - sum(l);
}
int kth(T k) {
int x = 0;
for (int i = 1 << std::__lg(n); i; i /= 2) {
if (x + i <= n && k >= a[x + i - 1]) {
x += i;
k -= a[x - 1];
}
}
return x;
}
};
int main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
int N, Q;
std::cin >> N;
std::vector<int> a(N), b(N), v;
for (int i = 0; i < N; i++) {
std::cin >> a[i] >> b[i];
v.push_back(a[i]);
}
std::cin >> Q;
std::vector<std::array<int, 3>> qry(Q, std::array<int, 3> {});
for (int i = 0; i < Q; i++) {
int o, x, y;
std::cin >> o;
if (o == 1) {
std::cin >> x >> y;
x--;
v.push_back(y);
qry[i] = {o, x, y};
} else if (o == 2) {
std::cin >> x >> y;
x--;
qry[i] = {o, x, y};
} else {
std::cin >> x;
qry[i] = {o, x};
}
}
int M = v.size();
std::sort(v.begin(), v.end(), std::greater<>());
Fenwick<int> fc(M);
Fenwick<i64> fs(M);
for (int i = 0; i < N; i++) {
a[i] = std::lower_bound(v.begin(), v.end(), a[i], std::greater<>()) - v.begin();
fc.add(a[i], b[i]);
fs.add(a[i], 1ll * v[a[i]] * b[i]);
}
for (auto [o, x, y] : qry) {
if (o == 1) {
y = std::lower_bound(v.begin(), v.end(), y, std::greater<>()) - v.begin();
fc.add(a[x], -b[x]);
fs.add(a[x], -1ll * v[a[x]] * b[x]);
a[x] = y;
fc.add(a[x], b[x]);
fs.add(a[x], 1ll * v[a[x]] * b[x]);
} else if (o == 2) {
fc.add(a[x], -b[x]);
fs.add(a[x], -1ll * v[a[x]] * b[x]);
b[x] = y;
fc.add(a[x], b[x]);
fs.add(a[x], 1ll * v[a[x]] * b[x]);
} else {
int j = fc.kth(x);
int cnt = fc.sum(j);
if (cnt < x && j == M) {
std::cout << -1 << "\n";
} else {
i64 ans = fs.sum(j);
if (cnt < x) ans += 1ll * (x - cnt) * v[j];
std::cout << ans << "\n";
}
}
}
return 0;
}
|