把一次修改操作拆成两个操作:
减去原位置的值(相当于加它的负数
加上新的值
就没了
#include <bits/stdc++.h>
using namespace std;
// 把a[x]修改为y相当于先把[0,x]所有数-a[x],再加y
const int SIZE = 4e5 + 5;
const int inf = 1e9;
int n, m, cnt, num;
int ans[SIZE], tree[SIZE], a[SIZE];
struct question {
int l, r, val, opt;
} q[SIZE], lq[SIZE], rq[SIZE];
inline int read()
{
char ch = getchar();
int f = 1, x = 0;
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
return x * f;
}
inline int lowbit(int x) { return x & (-x); }
inline int query(int pos)
{
int ans = 0;
for ( ; pos; pos -= lowbit(pos)) ans += tree[pos];
return ans;
}
inline void modify(int pos, int val)
{
for ( ; pos <= n; pos += lowbit(pos)) tree[pos] += val;
}
inline void solve(int lval, int rval, int st, int ed)
{
// printf("%d\n", ++ num);
if (st > ed) return;
if (lval == rval) {
for (int i = st; i <= ed; ++ i) {
if (q[i].opt > 0) ans[q[i].opt] = lval;
}
return;
}
int mid = (lval + rval) >> 1;
int ltot = 0, rtot = 0;
for (int i = st; i <= ed; ++ i) {
if (q[i].opt == -1) {
if (q[i].r <= mid) modify(q[i].l, -1), lq[++ ltot] = q[i];
else rq[++ rtot] = q[i];
}
if (q[i].opt == 0) {
if (q[i].r <= mid) modify(q[i].l, 1), lq[++ ltot] = q[i];
else rq[++ rtot] = q[i];
}
if (q[i].opt > 0) {
int tot = query(q[i].r) - query(q[i].l - 1);
if (tot >= q[i].val) lq[++ ltot] = q[i];
else q[i].val -= tot, rq[++ rtot] = q[i];
}
}
for (int i = ed; i >= st; -- i) {
if (q[i].r > mid) continue;
if (q[i].opt == -1) modify(q[i].l, 1);
if (q[i].opt == 0) modify(q[i].l, -1);
}
for (int i = 1; i <= ltot; ++ i) q[st + i - 1] = lq[i];
for (int i = 1; i <= rtot; ++ i) q[st + ltot + i - 1] = rq[i];
solve(lval, mid, st, st + ltot - 1);
solve(mid + 1, rval, st + ltot, ed);
}
int main()
{
n = read(), m = read();
for (int i = 1; i <= n; ++ i) {
a[i] = read();
q[++ cnt].opt = 0, q[cnt].l = i, q[cnt].r = a[i];
}
int tim = 0;
for (int i = 1; i <= m; ++ i) {
char ch;
std::cin >> ch;
if (ch == 'Q') {
q[++ cnt].opt = ++ tim, q[cnt].l = read(), q[cnt].r = read(), q[cnt].val = read();
}
if (ch == 'C') {
int pos = read(), val = read();
q[++ cnt].opt = -1, q[cnt].l = pos, q[cnt].r = a[pos];
a[pos] = val;
q[++ cnt].opt = 0, q[cnt].l = pos, q[cnt].r = a[pos];
}
}
solve(-inf, inf, 1, cnt);
for (int i = 1; i <= tim; ++ i) printf("%d\n", ans[i]);
return 0;
}
Comments | NOTHING