---
layout: 「SNOI2017」一个简单的询问
title: 「SNOI2017」一个简单的询问
date: 2019-08-19 11:59:31
tags:
- 数据结构
- 莫队
categories:
- ACM
---
给你一个长度为 $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$ 出现了多少次。
<!--more-->
## 题目链接
[「SNOI2017」一个简单的询问](https://loj.ac/problem/2254)
## 输入输出格式
### 输入格式：
第一行，一个数字 $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$
这样，这题就解了。
## 代码
```cpp
#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;
}
```
「SNOI2017」一个简单的询问
