给你一个长度为 $N$ 的序列 $a_i$,$1\leq i\leq N$,和 $q$ 组询问,每组询问读入 $l_1,r_1,l_2,r_2$,需输出
$$
\sum\limits_^\infty \text(l_1,r_1,x)\cdot \text(l_2,r_2,x)
$$
$ \text(l,r,x)$ 表示计算区间 $[l,r]$ 中,数字 $x$ 出现了多少次。
题目链接
输入输出格式
输入格式:
第一行,一个数字 $N$,表示序列长度。
第二行,$N$ 个数字,表示 $a_1\sim a_N$。
第三行,一个数字 $Q$,表示询问个数。
第 $4\sim Q+3$ 行,每行四个数字 $l_1,r_1,l_2,r_2$,表示询问。
输出格式
对于每组询问,输出一行一个数字,表示答案。
输入输出样例
样例输入
5
1 1 1 1 1
2
1 2 3 4
1 1 4 4
样例输出
4
1
说明
对于 $20%$ 的数据,$1\leq N,Q\leq 1000$;
对于另外 $30%$ 的数据,$1\leq a_i\leq 50$;
对于 $100%$ 的数据,$N,Q\leq 50000$,$1\leq a_i\leq N$,$1\leq l_1\leq r_1\leq N$,$1\leq l_2\leq r_2\leq N$。
注意:答案有可能超过 int
的最大值。实测好像没有?数据水了?
题解
又是面向题解解题的一道题目。
看了一眼,这能是莫队?莫队不是用于单区间操作的么?难道用两个莫队?一个查询前面,一个查询后面?可是要怎么排序?怎么让排序过后的区间仍然保持匹配?种种问题,让我不会。第一次看题解,那么长的推到,好了不会,超过能力范围了。偶然看了一个代码,发现不长,去看看推倒过程还是很简单的。
题中要求 $[l_1,r_1] $ ~ $ [l_2,r_2]$ 区间内 $x$ 出现次数的乘积。对于 $[l_1,r_1] $ 区间,我们把 $\text(l,r,x)$ 转化为 $\text(1,r,x) - \text(1,l-1,x)$ (类似与主席树?) 设 $s(i) = \text(l,i,x)$。 则对于体中要求的式子,我们可以转化为
$$
\sum\limits_^\infty (\text(1,r_1,x) - \text(1,l_1-1,x))\cdot(\text(1,r_2,x) - \text(1,l_2-1,x))
$$
$\Downarrow$
$$\sum\limits_^\infty (s(r_1)- s(l_1-1))\cdot(s(r_2) - s(l_2-1)) $$
$\Downarrow$
$$s(r_1)\cdot s(r_2) + s(l_1-1)\cdot s(l_2-1) - s(r_1)\cdot s(l_2-1) - s(r_2)\cdot s(l_1-1) $$
由这个平方和公式 $a\cdot b=\dfrac {\left( a{2}+b{2}\right) -a{2}-b{2}}{2}$
$\Downarrow$
$\dfrac {\left( s\left( r_{1}\right) +s\left( r_{2}\right) \right) {2} + \left( s\left( l_{1}-1\right) +s\left( l_{2}-1\right) \right) {2} - \left( s\left( r_{2}\right) +s\left( l_{1}-1\right) \right) {2} - \left( s\left( r_{1}\right) +s\left( l_{2}-1\right) \right) {2}} {2}$
仔细观察这个式子,可以得到分子就是区间 $[r1,l2],[l1,r2],[l1,l2],[r1,r2]$ 中 $x$ 出现个数的平方。
这样一来,再用莫队去做区间修改时,当减少一个数时就是从 $x2 \to (x-1)2$,也就是每次减少了 $2\cdot x-1$ 增加就是加上 $2\cdot x+1$
这样,这题就解了。
代码
#include <bits/stdc++.h>
const int MAXN = 1e5 + 5;
using namespace std;
typedef long long ll;
int n, m, block, belong[MAXN], cnt[MAXN];
int tot, l1, l2, r1, r2;
ll sum;
struct Node {
int l, r, id, sgin;
} data[MAXN << 2];
int a[MAXN], ans[MAXN];
int cmp(Node a, Node b) {
return (belong[a.l] ^ belong[b.l]) ? belong[a.l] < belong[b.l]
: ((belong[a.l] & 1) ? a.r < b.r : a.r > b.r);
}
void put(int l, int r, int id, int sgin) {
data[++tot].l = min(l, r) + 1; //画完柿子后会发现变成了s(r大)-s(l小),也就是求l+1--r的x平方和
data[tot].r = max(l, r);
data[tot].id = id;
data[tot].sgin = sgin;
}
void add(int x) {
sum += cnt[x] * 2 + 1;
cnt[x]++;
}
void del(int x) {
sum -= cnt[x] * 2 - 1;
cnt[x]--;
}
void Build() {
block = sqrt(n);
for (int i = 1; i <= n; i++) belong[i] = (i - 1) / block + 1;
}
int main() {
scanf("%d", &n);
Build();
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
scanf("%d", &m);
for (int i = 1; i <= m; i++) {
scanf("%d %d %d %d", &l1, &r1, &l2, &r2);
l1--;
l2--;
put(r1, r2, i, 1); //把区间拆分
put(l1, l2, i, 1);
put(l1, r2, i, -1);
put(l2, r1, i, -1);
}
sort(data + 1, data + 1 + tot, cmp);
int L = 0, R = 0;
for (int i = 1; i <= tot; i++) {
int ql = data[i].l, qr = data[i].r;
while (L < ql) del(a[L++]);
while (R < qr) add(a[++R]);
while (L > ql) add(a[--L]);
while (R > qr) del(a[R--]);
ans[data[i].id] += sum * data[i].sgin;
}
for (int i = 1; i <= m; i++) printf("%d\n", -ans[i] / 2); //结果为啥时负的我也不知道
return 0;
}