LOJ 10115 校门外的树

题目链接

神仙思路。
每次g种树树把左端点插到一个树状数组\(a\)，右端点插\(b\)。
每次查询查\(qry(r,a)-qry(l-1,b)\)

为什么这样是对的呢？
\(qry(r,a)\)表示所有左端点在查询区间\(l\)右边的，这些树有可能会对答案产生贡献。
但是有些树没有贡献，只有这些区间右端点比\(l\)小的时候。

#include <bits/stdc++.h>
using namespace std;

const int N = 5e4 + 7;
int n, m, a[N], b[N];

void upd(int x, int *a) {for (; x <= n; x += x & -x) a[x] += 1;}
int qry(int x, int *a) {int res = 0; for (; x; x -= x & -x) res += a[x]; return res;} 

int main() {
    scanf("%d %d", &n, &m);
	while (m--) {
		int op, l, r;
		scanf("%d %d %d", &op, &l, &r);
		if (op == 1) upd(l, a), upd(r, b);
		else printf("%d\n", qry(r, a) - qry(l - 1, b));
	}
	return 0;
}