题解【P5268 [SNOI2017]一个简单的询问】

$\texttt{Description}$

题面非常明了就不废话了，直接看题面

$\texttt{Solution}$

题目给了个需要依赖四个参数的式子，看起来不怎么可做。

这个式子好像也挺恶心，我们尝试把它展开以下看能不能变得好做。以下 $g$ 代表 $get$ 函数，令 $f(l_1,l_2,r_1,r_2)=\sum\limits^{\infty}_{i=1}g(l_1,r_1,i)\times g(l_2,r_2,i)$（就是题目里给的那坨）。

$$\begin{aligned} f(l_1,l_2,r_1,r_2)&=\sum\limits^{\infty}_{i=1}g(l_1,r_1,i)\times g(l_2,r_2,i)\\ &=\sum\limits^{\infty}_{i=1}[g(1,r_1,i)-g(1,l_1-1,i)]\times [g(1,r_2,i)-g(1,l_2-1,i)]\\ &=\sum\limits^{\infty}_{i=1}g(1,l_1,i)\times g(1,r_2,i)-g(1,l_1-1,i)\times g(1,r_2,i)-g(1,r_1,i)\times g(1,l_2-1,i)+g(1,l_1-1,i)\times g(1,r_2-1,i)\\ &=f(1,1,r_1,r_2)-f(1,1,l_1-1,r_2)-f(1,1,l_2-1,r_1)+f(1,1,l_1-1,r_1-1) \end{aligned}$$

最后整个柿子就变成了一个可口的二位数点的容斥柿子……

令 $f_0(x,y)=f(1,1,x,y)$。一看数据范围，五万，显然是个根号级别起步的算法。由于很容易根据 $f_0(x,y)$ 推出 $f_0(x+1,y)$ 等，那么直接莫队维护两个cnt数组即可。详见代码。

#include <cstdio>
#include <algorithm>
#include <cmath>

int a[50005], cnt[50005][2], Q[50005], ans, S, tot;
struct Question {
	int op, id, l, r;
	inline bool operator < (const Question a) const {
		int x((l - 1) / S), y((a.l - 1) / S);
		return x == y ? (r - 1) / S < (a.r - 1) / S + 1 : x < y;
	}
} q[200005];

inline void add(const int x, const int d) {
	ans += cnt[x][d ^ 1], ++ cnt[x][d];
}
inline void del(const int x, const int d) {
	ans -= cnt[x][d ^ 1], -- cnt[x][d];
}

int main() {
	int n, m, l(0), r(0);
	scanf("%d", &n);
	for (int i(1); i <= n; ++ i) scanf("%d", a + i);
	scanf("%d", &m);
	S = n / sqrt(m);
	for (int i(1); i <= m; ++ i) {
		int l1, l2, r1, r2;
		scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
		q[++ tot].op = 1, q[tot].id = i, q[tot].l = r1, q[tot].r = r2;
		q[++ tot].op = -1, q[tot].id = i, q[tot].l = l1 - 1, q[tot].r = r2;
		q[++ tot].op = -1, q[tot].id = i, q[tot].l = l2 - 1, q[tot].r = r1;
		q[++ tot].op = 1, q[tot].id = i, q[tot].l = l1 - 1, q[tot].r = l2 - 1;
		for (int j(tot - 3); j <= tot; ++ j)
			if (q[j].l > q[j].r) std::swap(q[j].l, q[j].r);
	}
	std::sort(q + 1, q + tot + 1);
	for (int i(1); i <= tot; ++ i) {
		while (l < q[i].l) add(a[++ l], 0);
		while (l > q[i].l) del(a[l --], 0);
		while (r < q[i].r) add(a[++ r], 1);
		while (r > q[i].r) del(a[r --], 1);
		Q[q[i].id] += q[i].op * ans;
	}
	for (int i(1); i <= m; ++ i) printf("%d\n", Q[i]);
	return 0;
}