AC*2 WA*28 求条

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int MAXN = 3e6 + 1;

int n, m, sum, len, a[MAXN], cnt[MAXN];
struct node {
	int l, r, id, ans;
}q[MAXN];
bool cmp(node a, node b) {
	if(a.l / len == b.l / len) {
		return a.r < b.r;
	}
	return a.l < b.l;
}
bool cmp2(node a, node b) {
	return a.id < b.id;
}
void ADD(int x) {
	sum += (cnt[a[x]] % 2 == 1);
	cnt[a[x]]++;
}
void SUB(int x) {
	sum -= (cnt[a[x]] % 2 == 0);
	cnt[a[x]]--;
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	len = sqrt(n);
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	cin >> m;
	for(int i = 1; i <= m; i++) {
		cin >> q[i].l >> q[i].r;
		q[i].id = i;
	}
	sort(q + 1, q + m + 1, cmp);
	int l = 1, r = 0;
	for(int i = 1; i <= m; i++) {
		while(l < q[i].l) {
			SUB(l++);
		}
		while(l > q[i].l) {
			ADD(--l);
		}
		while(r > q[i].r) {
			SUB(r--);
		}
		while(r < q[i].r) {
			ADD(++r);
		}
		q[i].ans = sum;
	}
	sort(q + 1, q + m + 1, cmp2);
	for(int i = 1; i <= m; i++) {
		cout << q[i].ans << "\n";
	}
	return 0;
}