Submission #65691220

---

Source Code Expand

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define MaxN 200005
int n, m, q;
struct Node{
	int a, b, id;
} p[MaxN], o[MaxN];

int tr[2000005];
long long ans[MaxN];

bool cmp1(Node x, Node y) {
	return x.a < y.a;
}

bool cmp2(Node x, Node y) {
	return x.b > y.b;
}

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

void add(int x) {
	while (x < MaxN) {
		tr[x]++;
		x += lowbit(x);
	}
}

int query(int x) {
	int re = 0;
	while (x > 0) {
		re += tr[x];
		x -= lowbit(x);
	}
	return re;
}

int main()
{
	cin >> n >> m;
	for(int i = 1; i <= m; i++) {
		cin >> p[i].a >> p[i].b;
	}
	cin >> q;
	for(int i = 1; i <= q; i++) {
		cin >> o[i].a >> o[i].b;
		o[i].id = i;
	}
	sort(p+1, p+m+1, cmp1);
	sort(o+1, o+q+1, cmp1);

	int h = 1;
	for(int i = 1; i <= q; i++) {
		// o[i].a ~ o[i].b
		while (h <= m && p[h].a < o[i].a) {
			add(p[h].b);
			h++;
		}
		ans[o[i].id] = query(o[i].b) - query(o[i].a);
	}

	sort(p+1, p+m+1, cmp2);
	sort(o+1, o+q+1, cmp2);

	h = 1;
	memset(tr, 0, sizeof(tr));
	for(int i = 1; i <= q; i++) {
		// o[i].a ~ o[i].b
		while (h <= m && p[h].b > o[i].b) {
			add(p[h].a);
			h++;
		}
		ans[o[i].id] += query(o[i].b) - query(o[i].a);
	}

	for(int i = 1; i <= q; i++) {
		cout << ans[i] << endl;
	}
	return 0;
}

Submission Info

Judge Result