洛谷 P5268 [SNOI2017]一个简单的询问（莫队，差分）

题解：
https://www.luogu.com.cn/problem/solution/P5268
1、根据差分 get(L, R, x) = get(1, R, x) - get(1, L - 1, x)
从而， get(L1, R1, x) * get(L2, R2, x) 可以分为 4部分
q1 = get(1, R1, x) * get(1, R2, x)
q2 = get(1, L1 - 1, x) * get(1, L2 - 1, x)
q3 = get(1, L1 - 1, x) * get(1, R2, x)
q4 = get(1, R1, x) * get(1, L2 - 1, x)

2、 每次查询都输入 [L1, R1] 和 [L2, R2], 这里分拆为4个查询
[R1, R2]
[L1 -1, L2 - 1]
[L1 - 1, R2]
[R1, L2 - 1]
按照莫队的做法，排序
3、 后面就是 Add 和 Sub 函数了。
这里维护两个数组 cnt1[x] 和cnt2[x]
cnt1[x] 表示每个查询 query(L, R) 在区间 [1, L] x出现的次数
cnt2[x] 表示每个查询 query(L, R) 在区间 [1, R] x出现的次数

#include 
using namespace std;
const int N = 5e4 + 10;
int a[N], pos[N];
int n, m, l1, r1, l2, r2;
int cnt1[N], cnt2[N];
int ans[N], res;

struct Query
{
   
	int l, r;
	int type;	// 加还是减
	int idx;	//第几次查询
	Query(int left = 0, int right = 0, int t = 0, int index = 0)
	:l(left)
	 , r(right)
	 , type(t)
	 , idx(index
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18