---
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」一个简单的询问