#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);
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;
}
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;
}
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.push_back(c.rig.back());
else if (c.rig.empty())
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;
}
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:45:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | if (j == b.lef.size()) {
| ~~^~~~~~~~~~~~~~~
fish2.cpp:51:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for (int i = 0, j = 0; i < b.lef.size(); i++) {
| ~~^~~~~~~~~~~~~~
fish2.cpp:52:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | while (j < a.rig.size() && b.lef[i].sum +
| ~~^~~~~~~~~~~~~~
fish2.cpp:55:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | if (j && i + 1 < b.lef.size() &&
| ~~~~~~^~~~~~~~~~~~~~
fish2.cpp:61:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | if (j == a.rig.size()) {
| ~~^~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
