联赛模拟测试20 C. Weed

肥料吸收两米下氮磷钾,掺坷垃小麦亩产一万八,日本资源埋在两千米下,没有坷垃日本怎么种庄稼
一看到这道题大脑就开始放歌了

这道题可以看出操作像是一个用栈的操作,(当然更像是一个主席树,但是主席树好像没有办法统计答案,就只剩下栈了.)于是我们可以联想到前一段做的一道线段树维护单调栈的题目,当然这道题的栈并不单调,我们只是借用那道题的思路,对于线段树上的每一个节点记录一下当前节点还需要删前面的区间多少层,这一个点里面一共有多少层,以及这个节点可以贡献的答案总和,每当两个区间进行合并的时候我们讨论一下,如果左儿子的总层数比右儿子要删的层数还少直接减去贡献即可.但是如果要大一些的话就需要我们另外写一个函数来计算从左儿子删去几层后剩下的贡献之和,需要注意的是左儿子的最后几层有可能是没法用的,有可能它在左区间就已经被删掉了,于是我们查询的是(ask(lson, cnt - tree[rson].cnt + tree[rson].del) - ask(lson, tree[rson].del))

#include <cstdio>
#include <cstring>
#include <algorithm>
const int N = 1e6 + 10;
#define lson (t << 1)
#define rson (t << 1 | 1)
#define mid ((l + r) >> 1)
struct Tree {
	int sum, del, cnt;
} tree[N];
struct Que {
	int op, x;
} a[N];
int ask(int t, int cnt) {
	if(cnt <= 0) return 0;
	if(tree[t].cnt == cnt) return tree[t].sum;
	if(tree[rson].cnt >= cnt) return ask(rson, cnt);
	else return ask(lson, cnt - tree[rson].cnt + tree[rson].del) - ask(lson, tree[rson].del)+ tree[rson].sum;
}
void pushup(int t) {
	if(tree[rson].del > tree[lson].cnt) {
		tree[t].sum = tree[rson].sum;
		tree[t].del = tree[rson].del - tree[lson].cnt + tree[lson].del;
		tree[t].cnt = tree[rson].cnt;
	}
	else {
		tree[t].cnt = tree[lson].cnt + tree[rson].cnt - tree[rson].del;
		tree[t].sum = tree[lson].sum + tree[rson].sum - ask(lson, tree[rson].del);
		tree[t].del = tree[lson].del;
	}
}
void build(int t, int l, int r) {
	if(l == r) {
		tree[t].sum = a[l].op ? 0 : a[l].x;
		tree[t].del = a[l].op ? a[l].x : 0;
		tree[t].cnt = a[l].op ? 0 : 1;
		return;
	}
	build(lson, l, mid);
	build(rson, mid + 1, r);
	pushup(t);
}
void change(int t, int l, int r, int pos, int op, int x) {
	if(l == r) {
		tree[t].sum = op ? 0 : x;
		tree[t].del = op ? x : 0;
		tree[t].cnt = op ? 0 : 1;
		return;
	}
	if(pos <= mid) change(lson, l, mid, pos, op, x);
	else change(rson, mid + 1, r, pos, op, x);
	pushup(t);
}
int main() {
	freopen("weed.in", "r", stdin);
	freopen("weed.out", "w", stdout);
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		a[i] = (Que){x, y};
	}
	build(1, 1, n);
	while(m--) {
		int pos, op, x;
		scanf("%d%d%d", &pos, &op, &x);
		change(1, 1, n, pos, op, x);
		printf("%d
", tree[1].sum);
	}
	return 0;
}