luogu P2184 贪婪大陆

乍一不咋会

╭(╯3╰)╮

把地雷L到R看成一条线段

要求的就是区间内有多少条线段经过

很明显是要用[1,R]内的起点个数-[1,L-1]的终点个数

然后这起点和终点个数可以用简单的差分线段树来维护一下

其实树状数组更适合一些

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#define ls rt<<1

#define rs rt<<1|1

using namespace std;

const int maxn = 1e5 + 7;

const int maxm = 4e5 + 7;

int n, m;

struct node {

	int l, r, size;

	int sum;

};

struct seg_tree {

	node e[maxm];

	void pushup(int rt) {

		e[rt].sum = e[ls].sum + e[rs].sum;

	}

	void build(int l, int r, int rt) {

		e[rt].l = l, e[rt].r = r;

		if (l == r) {

			return;

		}

		int mid = (l + r) >> 1;

		build(l, mid, ls);

		build(mid + 1, r, rs);

		pushup(rt);

	}

	void update(int L, int rt) {

		if (e[rt].l == e[rt].r) {

			e[rt].sum++;

			return;

		}

		int mid = (e[rt].l + e[rt].r) >> 1;

		if (L <= mid) update(L, ls);

		else update(L, rs);

		pushup(rt);

	}

	int query(int L, int R, int rt) {

		if (L <= e[rt].l && e[rt].r <= R) {

			return e[rt].sum;

		}

		int mid = (e[rt].l + e[rt].r) >> 1, ans = 0;

		if (L <= mid) ans += query(L, R, ls);

		if (R > mid) ans += query(L, R, rs);

		pushup(rt);

		return ans;

	}

} seg1, seg2;

int read() {

	int x = 0, f = 1; char s = getchar();

	for (; s > '9' || s < '0'; s = getchar()) if (s == '-') f = -1;

	for (; s >= '0' && s <= '9'; s = getchar()) x = x * 10 + s - '0';

	return x * f;

}

int main() {

	int n = read(), m = read();

	seg1.build(1, n, 1);

	seg2.build(1, n, 1);

	for (; m--;) {

		int tmp = read(), x = read(), y = read();

		if (tmp == 1) {

			seg1.update(x,1);

			seg2.update(y,1);

		} else {

			int ans = seg1.query(1,y,1) - seg2.query(1,x-1,1);

			printf("%d\n", ans);

		}

	}

	return 0;

}