code1:
#include <cstdio>
#include <algorithm>
#define int long long
#define maxn 200000
#define inf 2100000000
struct code {
int left, x;
} a[maxn + 10], m;
int tree[(maxn << 1) + 10];
void add(int id, int l, int r, int w, int x) {
if (l == r) {
tree[id] = x;
return;
}
int mid = l + r >> 1;
if (w <= mid) add(id << 1, l, mid, w, x);
else add((id << 1) + 1, mid + 1, r, w, x);
tree[id] = std :: max(tree[id << 1], tree[(id << 1) + 1]);
return;
}
void kill(int id, int l, int r, int maxr) {
if (l == r) {
tree[id] = -inf;
return;
}
int mid = l + r >> 1;
if (maxr <= mid) kill(id << 1, l, mid, maxr);
else tree[id << 1] = -inf, kill((id << 1) + 1, mid + 1, r, maxr);
tree[id] = std :: max(tree[id << 1], tree[(id << 1) + 1]);
return;
}
int l = 1, r, n, suml[maxn + 10], del;
signed main(void) {
int id, Q, p, x; scanf("%lld %lld", &id, &Q);
n = Q;
while (Q--) {
scanf("%lld", &p);
if (p == 1) {
scanf("%lld", &x);
m.left = m.x = x;
a[++r] = m;
suml[r] = suml[r - 1] + x;
add(1, 1, n, r, m.x);
} else if (p == 2) {
scanf("%lld", &x);
del += x;
while (a[l].left <= x && x)
x -= a[l++].left;
a[l].left -= x;
kill(1, 1, n, l - 1);
} else if (p == 3) {
scanf("%lld", &x);
int ll = l, rr = r;
while (ll < rr) {
int mid = ll + rr >> 1;
if (suml[mid] < del + x) ll = mid + 1;
else rr = mid;
}
printf("%lld\n", del + x - suml[ll - 1]);
} else {
printf("%lld\n", tree[1]);
}
}
return 0;
}
code2:
#include <cstdio>
#include <algorithm>
#define int long long
#define maxn 200000
#define inf 2100000000
struct code {
int left, x;
} a[maxn + 10], m;
int tree[(maxn << 1) + 10];
void add(int id, int l, int r, int w, int x) {
if (l == r) {
tree[id] = x;
return;
}
int mid = l + r >> 1;
if (w <= mid) add(id << 1, l, mid, w, x);
else add((id << 1) + 1, mid + 1, r, w, x);
tree[id] = std :: max(tree[id << 1], tree[(id << 1) + 1]);
return;
}
void kill(int id, int l, int r, int maxr) {
if (l == r) {
if (maxr >= r) tree[id] = -inf; // here
return;
}
int mid = l + r >> 1;
if (maxr <= mid) kill(id << 1, l, mid, maxr);
else tree[id << 1] = -inf, kill((id << 1) + 1, mid + 1, r, maxr);
tree[id] = std :: max(tree[id << 1], tree[(id << 1) + 1]);
return;
}
int l = 1, r, n, suml[maxn + 10], del;
signed main(void) {
int id, Q, p, x; scanf("%lld %lld", &id, &Q);
n = Q;
while (Q--) {
scanf("%lld", &p);
if (p == 1) {
scanf("%lld", &x);
m.left = m.x = x;
a[++r] = m;
suml[r] = suml[r - 1] + x;
add(1, 1, n, r, m.x);
} else if (p == 2) {
scanf("%lld", &x);
del += x;
while (a[l].left <= x && x)
x -= a[l++].left;
a[l].left -= x;
kill(1, 1, n, l - 1);
} else if (p == 3) {
scanf("%lld", &x);
int ll = l, rr = r;
while (ll < rr) {
int mid = ll + rr >> 1;
if (suml[mid] < del + x) ll = mid + 1;
else rr = mid;
}
printf("%lld\n", del + x - suml[ll - 1]);
} else {
printf("%lld\n", tree[1]);
}
}
return 0;
}
感觉这句话没用因为l==r时maxr>=r应该是必然成立的 但就这样才能过 求解释