• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# [2019 ICPC 徐州 H] Yuuki and a problem

2周前 (04-08) 7次浏览

``````#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5 + 7;

int n, m, q, li, ri;
int a[N], rt[N];

inline int lowbit(int x) {
return x & -x;
}

struct Seg{
struct Node{
int ls, rs, cnt;
ll sum;
void init() {
ls = rs = cnt = 0;
sum = 0;
}
}t[N * 80];
int tot;
void init() {
tot = 0;
t[tot].init();
}
int newnode() {
t[++tot].init();
}
void build(int &id, int l, int r) {
if (!id) id = newnode();
if (l == r) {
return;
}
int mid = l + r >> 1;
build(t[id].ls, l, mid);
build(t[id].rs, mid + 1, r);
}
void modify(int &rt, int l, int r, int pos, ll v) {
if (!rt) rt = newnode();
t[rt].sum += v;
if (l == r) {
return;
}
int mid = l + r >> 1;
if (pos <= mid) {
modify(t[rt].ls, l, mid, pos, v);
} else {
modify(t[rt].rs, mid + 1, r, pos, v);
}
}
void update(int x, int pos, ll v) {
for (; x <= n; x += lowbit(x)) {
modify(rt[x], 1, m, pos, v);
}
}
ll query(int rt, int l, int r, ll k) {
if (!rt) return 0;
if (r <= k) {
//        	printf("%d %d %d %dn", l, r, k, t[rt].sum);
return t[rt].sum;
}
if (l > k) return 0;
int mid = l + r >> 1;
if (k <= mid) return query(t[rt].ls, l, mid, k);
else return query(t[rt].ls, l, mid, k) + query(t[rt].rs, mid + 1, r, k);
}

ll query(int l, int r, ll k) {
ll res = 0;
for (int i = r; i > 0; i -= lowbit(i)) {
res += query(rt[i], 1, m, k);
}
for (int i = l; i > 0; i -= lowbit(i)) {
res -= query(rt[i], 1, m, k);
}
return res;
}
}seg;

int main() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
m = 2e5;
seg.init();
rt[0] = 0;
seg.build(rt[0], 1, m);
for (int i = 1; i <= n; ++i) {
seg.update(i, a[i], a[i]);
}
ll pre = 0;
for (int i = 1, op; i <= q; ++i) {
scanf("%d%d%d", &op, &li, &ri);
if (op == 1) {
seg.update(li, a[li], -a[li]);
a[li] = ri;
seg.update(li, a[li], a[li]);
} else {
pre = 1;
ll tmp = seg.query(li - 1, ri, pre);
while (tmp >= pre) {
pre = tmp + 1;
tmp = seg.query(li - 1, ri, pre);
}
printf("%lldn", pre);
}
}
return 0;
}``````