BZOJ5016 [Snoi2017]一个简单的询问

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 5e4 + 10;

int n, Q, siz, a[N];
LL res[N << 2] ,num[2][N];
struct Query {
	int l, r, num, block;
	bool operator < (const Query &b) const {
		if (block != b.block) return block < b.block;
		else return r < b.r;
	}
}q[N << 2];

int main(void) {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
	scanf("%d", &Q);
	siz = sqrt(Q * 4) + 1;
	for (int i = 1; i <= Q; ++i) {
		int l1, r1, l2, r2;
		scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
		q[i * 4 - 3] = (Query) {r1, r2};
		q[i * 4 - 2] = (Query) {l1 - 1, l2 - 1};
		q[i * 4 - 1] = (Query) {l1 - 1, r2};
		q[i * 4] = (Query) {r1, l2 - 1};
	}
	for (int i = 1; i <= Q * 4; ++i) {
		if (q[i].l > q[i].r) swap(q[i].l, q[i].r);
		q[i].num = i; q[i].block = q[i].l / siz;
	}
	sort(q + 1, q + Q * 4 +1);
	int l = 1, r = 1; LL ans = 1;
	num[0][a[1]] = num[1][a[1]] = 1;
	for (int i = 1; i <= Q * 4; ++i) {
		if (q[i].l == 0) continue;
		while (l < q[i].l) ++l, ++num[0][a[l]], ans += num[1][a[l]];
		while (l > q[i].l) --num[0][a[l]], ans -= num[1][a[l]], --l;
		while (r < q[i].r) ++r, ++num[1][a[r]], ans += num[0][a[r]];
		while (r > q[i].r) --num[1][a[r]], ans -= num[0][a[r]], --r;
		res[q[i].num] = ans;
	}
	for (int i = 1; i <= Q; ++i) {
		ans = res[i * 4 - 3] + res[i * 4 - 2] - res[i * 4 - 1] - res[i * 4];
		printf("%lld\n", ans);
	}
	return 0;
}