#include <bits/stdc++.h>
using namespace std;
#define il i + 1
#define ir i + (m - l + 1) * 2
using ll = long long;
struct item {
int pos, cnt; ll sum;
item(int pos, int cnt, ll sum):
pos(pos), cnt(cnt), sum(sum) {}
};
struct node {
vector<item> lef, rig;
};
const int N = 100005;
int val[N]; node seg[N * 2];
node res; int lo, hi;
void merge(int m, node a, node b, node &c) {
c.lef.clear(); c.rig.clear();
for (auto u : a.lef)
if (u.sum < val[u.pos + 1])
c.lef.push_back(u);
for (auto u : b.rig)
if (u.sum < val[u.pos - 1])
c.rig.push_back(u);
int ja, jb;
for (int i = 0, j = 0; i < a.rig.size(); i++) {
while (j < b.lef.size() && a.rig[i].sum +
(j ? b.lef[j - 1].sum : 0) >=
val[j ? b.lef[j - 1].pos + 1 : m + 1]) j++;
if (j && i + 1 < a.rig.size() &&
a.rig[i].sum + b.lef[j - 1].sum >=
val[a.rig[i].pos - 1]) {
a.rig[i + 1].cnt += a.rig[i].cnt;
continue;
}
ja = j;
if (j == b.lef.size()) {
item u = a.rig[i];
u.sum += b.lef[j - 1].sum;
c.rig.push_back(u);
}
}
for (int i = 0, j = 0; i < b.lef.size(); i++) {
while (j < a.rig.size() && b.lef[i].sum +
(j ? a.rig[j - 1].sum : 0) >=
val[j ? a.rig[j - 1].pos - 1 : m]) j++;
if (j && i + 1 < b.lef.size() &&
b.lef[i].sum + a.rig[j - 1].sum >=
val[b.lef[i].pos + 1]) {
b.lef[i + 1].cnt += b.lef[i].cnt;
continue;
}
jb = j;
if (j == a.rig.size()) {
item u = b.lef[i];
u.sum += a.rig[j - 1].sum;
c.lef.push_back(u);
}
}
if (c.lef.empty() || c.lef.back().pos != b.lef.back().pos)
c.lef.push_back(c.rig.back());
else if (c.rig.empty() || c.rig.back().pos != a.rig.back().pos)
c.rig.push_back(c.lef.back());
else c.lef.back().cnt = c.rig.back().cnt
= c.lef.back().cnt + c.rig.back().cnt;
c.lef.back().pos = b.lef.back().pos;
c.rig.back().pos = a.rig.back().pos;
if (ja && ja < b.lef.size()) {
ja--;
for (int i = 0; i < c.lef.size(); i++)
if (c.lef[i].pos >= b.lef[ja].pos) {
if (c.lef[i].pos == b.lef[ja].pos)
c.lef[i].cnt += a.lef.back().cnt;
else c.lef.insert(c.lef.begin() + i,
item(b.lef[ja].pos, a.lef.back().cnt,
a.lef.back().sum + b.lef[ja].sum));
break;
}
}
if (jb && jb < a.rig.size()) {
jb--;
for (int i = 0; i < c.rig.size(); i++)
if (c.rig[i].pos <= a.rig[jb].pos) {
if (c.rig[i].pos == a.rig[jb].pos)
c.rig[i].cnt += b.rig.back().cnt;
else c.rig.insert(c.rig.begin() + i,
item(a.rig[jb].pos, b.rig.back().cnt,
a.rig[jb].sum + b.rig.back().sum));
break;
}
}
}
void build(int i, int l, int r) {
if (l == r) {
seg[i].lef.emplace_back(l, 1, val[l]);
seg[i].rig.emplace_back(l, 1, val[l]);
} else {
int m = (l + r) / 2;
build(il, l, m); build(ir, m + 1, r);
merge(m, seg[il], seg[ir], seg[i]);
}
}
void update(int i, int l, int r, int p) {
if (l == r) {
seg[i].lef[0] = {l, 1, val[l]};
seg[i].rig[0] = {l, 1, val[l]};
} else {
int m = (l + r) / 2;
if (m >= p) update(il, l, m, p);
else update(ir, m + 1, r, p);
merge(m, seg[il], seg[ir], seg[i]);
}
}
void get(int i, int l, int r) {
if (l >= lo && r <= hi) {
if (l == lo) res = seg[i];
else merge(l - 1, res, seg[i], res);
} else {
int m = (l + r) / 2;
if (m >= lo) get(il, l, m);
if (m < hi) get(ir, m + 1, r);
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int n; cin >> n;
for (int i = 1; i <= n; i++)
cin >> val[i];
build(1, 1, n);
int q; cin >> q;
while (q--) {
int cmd; cin >> cmd;
if (cmd == 1) {
int p; cin >> p >> val[p];
update(1, 1, n, p);
} else {
cin >> lo >> hi; get(1, 1, n);
cout << res.lef.back().cnt << '\n';
}
}
}
Compilation message
fish2.cpp: In function 'void merge(int, node, node, node&)':
fish2.cpp:35:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for (int i = 0, j = 0; i < a.rig.size(); i++) {
| ~~^~~~~~~~~~~~~~
fish2.cpp:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | while (j < b.lef.size() && a.rig[i].sum +
| ~~^~~~~~~~~~~~~~
fish2.cpp:39:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | if (j && i + 1 < a.rig.size() &&
| ~~~~~~^~~~~~~~~~~~~~
fish2.cpp:46:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | if (j == b.lef.size()) {
| ~~^~~~~~~~~~~~~~~
fish2.cpp:52:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for (int i = 0, j = 0; i < b.lef.size(); i++) {
| ~~^~~~~~~~~~~~~~
fish2.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | while (j < a.rig.size() && b.lef[i].sum +
| ~~^~~~~~~~~~~~~~
fish2.cpp:56:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | if (j && i + 1 < b.lef.size() &&
| ~~~~~~^~~~~~~~~~~~~~
fish2.cpp:63:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | if (j == a.rig.size()) {
| ~~^~~~~~~~~~~~~~~
fish2.cpp:77:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | if (ja && ja < b.lef.size()) {
| ~~~^~~~~~~~~~~~~~
fish2.cpp:79:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for (int i = 0; i < c.lef.size(); i++)
| ~~^~~~~~~~~~~~~~
fish2.cpp:89:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | if (jb && jb < a.rig.size()) {
| ~~~^~~~~~~~~~~~~~
fish2.cpp:91:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for (int i = 0; i < c.rig.size(); i++)
| ~~^~~~~~~~~~~~~~
fish2.cpp:90:11: warning: 'jb' may be used uninitialized in this function [-Wmaybe-uninitialized]
90 | jb--;
| ~~^~
fish2.cpp:78:11: warning: 'ja' may be used uninitialized in this function [-Wmaybe-uninitialized]
78 | ja--;
| ~~^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 4 |
Correct |
5 ms |
9616 KB |
Output is correct |
| 5 |
Incorrect |
7 ms |
9776 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Incorrect |
64 ms |
30540 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 4 |
Correct |
5 ms |
9616 KB |
Output is correct |
| 5 |
Incorrect |
7 ms |
9776 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Incorrect |
64 ms |
30540 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Incorrect |
64 ms |
30540 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 4 |
Correct |
5 ms |
9616 KB |
Output is correct |
| 5 |
Incorrect |
7 ms |
9776 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
