「SNOI2017」一个简单的询问

给你一个长度为 $N$ 的序列 $a_i$，$1\leq i\leq N$，和 $q$ 组询问，每组询问读入 $l_1,r_1,l_2,r_2$，需输出

$$
\sum\limits_{x=0}^\infty \text{get}(l_1,r_1,x)\cdot \text{get}(l_2,r_2,x)
$$

$ \text{get}(l,r,x)$ 表示计算区间 $[l,r]$ 中，数字 $x$ 出现了多少次。

题目链接

「SNOI2017」一个简单的询问

输入输出格式

输入格式：

第一行，一个数字 $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{get}(l,r,x)$ 转化为 $\text{get}(1,r,x) - \text{get}(1,l-1,x)$ (类似与主席树？) 设 $s(i) = \text{get}(l,i,x)$。 则对于体中要求的式子，我们可以转化为
$$
\sum\limits_{x=0}^\infty (\text{get}(1,r_1,x) - \text{get}(1,l_1-1,x))\cdot(\text{get}(1,r_2,x) - \text{get}(1,l_2-1,x))
$$

                                             $\Downarrow$

$$\sum\limits_{x=0}^\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$ 出现个数的平方。
这样一来，再用莫队去做区间修改时，当减少一个数时就是从 $x^2 \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;
}