#include <bits/stdc++.h>
using namespace std;
void fastios() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
}
using ll = long long;
const ll inf = (1ll << 60);
const int maxn = 1e5;
struct Stuck {
int pos;
ll val;
ll sum;
int cand;
};
struct Node {
int sol;
ll sum;
vector <Stuck> pref;
vector <Stuck> suf;
};
Node seg[1 + 4 * maxn];
int N, Q;
int A[1 + maxn];
Node join(Node lnode, Node rnode, int lb, int rb) {
Node answer;
int ipref = 0, isuf = 0;
answer.sum = lnode.sum + rnode.sum;
int cand = 0;
ll sum = 0;
vector <int> candleft(lnode.suf.size()), candright(rnode.pref.size());
Stuck nowleft = lnode.suf[0], nowright = rnode.pref[0];
while (isuf + 1 < (int)lnode.suf.size() || ipref + 1 < (int)rnode.pref.size()) {
if (isuf + 1 < (int)lnode.suf.size() && ipref + 1 < (int)rnode.pref.size()) {
if (lnode.suf[isuf].val <= rnode.pref[ipref].val) {
isuf++;
nowleft = lnode.suf[isuf];
cand += nowleft.cand;
}
else {
ipref++;
nowright = rnode.pref[ipref];
cand += nowright.cand;
}
}
else if (isuf + 1 < (int)lnode.suf.size()) {
isuf++;
nowleft = lnode.suf[isuf];
cand += nowleft.cand;
}
else {
ipref++;
nowright = rnode.pref[ipref];
cand += nowright.cand;
}
sum = nowleft.sum + nowright.sum;
if (nowleft.pos == lb - 1)
candright[ipref] = cand;
if (nowright.pos == rb + 1)
candleft[isuf] = cand;
if (sum < min(nowleft.val, nowright.val) && min(nowleft.val, nowright.val) < inf)
cand = 0;
}
answer.sol = cand;
answer.pref = lnode.pref;
answer.pref.pop_back();
for (int i = 0; i < (int)rnode.pref.size(); i++) {
Stuck now = rnode.pref[i];
if (now.val > now.sum + lnode.sum)
answer.pref.push_back({now.pos, now.val, now.sum + lnode.sum, candright[i]});
}
answer.suf = rnode.suf;
answer.suf.pop_back();
for (int i = 0; i < (int)lnode.suf.size(); i++) {
Stuck now = lnode.suf[i];
if (now.val > now.sum + rnode.sum)
answer.suf.push_back({now.pos, now.val, now.sum + rnode.sum, candleft[i]});
}
return answer;
}
Node createNode(int pos, int val) {
Node answer;
answer.sum = val;
answer.sol = 1;
answer.pref.push_back({pos, val, 0, 0});
answer.pref.push_back({pos + 1, inf, val, 1});
answer.suf.push_back({pos, val, 0, 0});
answer.suf.push_back({pos - 1, inf, val, 1});
return answer;
}
void build(int node, int lb, int rb) {
if (lb == rb) {
seg[node] = createNode(lb, A[lb]);
return;
}
int mid = (lb + rb) / 2, lnode = node * 2, rnode = node * 2 + 1;
build(lnode, lb, mid);
build(rnode, mid + 1, rb);
seg[node] = join(seg[lnode], seg[rnode], lb, rb);
}
void updatePos(int node, int lb, int rb, int pos, int val) {
if (lb == rb) {
seg[node] = createNode(pos, val);
return;
}
int mid = (lb + rb) / 2, lnode = node * 2, rnode = node * 2 + 1;
if (pos <= mid)
updatePos(lnode, lb, mid, pos, val);
else
updatePos(rnode, mid + 1, rb, pos, val);
seg[node] = join(seg[lnode], seg[rnode], lb, rb);
}
Node queryRange(int node, int lb, int rb, int ql, int qr) {
if (ql <= lb && rb <= qr)
return seg[node];
int mid = (lb + rb) / 2, lnode = node * 2, rnode = node * 2 + 1;
if (qr <= mid)
return queryRange(lnode, lb, mid, ql, qr);
if (ql > mid)
return queryRange(rnode, mid + 1, rb, ql, qr);
Node L = queryRange(lnode, lb, mid, ql, mid);
Node R = queryRange(rnode, mid + 1, rb, mid + 1, qr);
return join(L, R, ql, qr);
}
int main() {
fastios();
cin >> N >> Q;
for (int i = 1; i <= N; i++)
cin >> A[i];
build(1, 1, N);
while (Q--) {
int type;
cin >> type;
if (type == 1) {
int pos, val;
cin >> pos >> val;
A[pos] = val;
updatePos(1, 1, N, pos, val);
}
else {
int l, r;
cin >> l >> r;
cout << queryRange(1, 1, N, l, r).sol << "\n";
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
25300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
25300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
25300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
25300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
25300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
25300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
