【莫队】洛谷 P5268 一个简单的询问
2021-10-25 20:15:00 # ACM

题链

题目解析

给一个数组，多次询问 $\sum_{x=0}^{\infty}get(l_1,r_1,x)·get(l_2,r_2,x)$，$get$ 是指区间 $[l,r]$ 中 $x$ 出现的次数；

可以将式子转化变为 $[get(1,r_1,x)-get(1,l_1-1,x)]·[get(1,r_2,x)-get(1,l_2-1,x)]$，
再化开变为
$get(1,r_1,x)get(1,r_2,x)-get(1,l_1-1,x)get(1,r_2,x)-get(1,r_1,x)get(1,l_2-1,x)+get(1,l_1-1,x)get(1,l_2-1,x)$

这样对每个式子跑莫队，4遍~

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;
	#define gg(x) cout << #x << ": " << x << "\n";
	#define LL long long 
	#define MAXN 9e18
	#define MS 50009
	
LL n,m,k,T;
LL a[MS];
LL ask[MS][4];
struct node{
	LL l,r,id;
}tsk[MS];
LL cnt[2][MS];
LL ac[MS];

bool cmp(node t1, node t2){
	if(t1.l/T == t2.l/T) return t1.r < t2.r;
	return t1.l < t2.l;
}

void init_tsk(LL l,LL r){
	for(int i=1;i<=m;i++){
		tsk[i] = {ask[i][l], ask[i][r], i};
		if(tsk[i].l > tsk[i].r) swap(tsk[i].l, tsk[i].r);
	} 
}

void modify(LL t, LL val, LL w, LL &res){
	res -= cnt[t][val]*cnt[t^1][val];
	cnt[t][val] += w;
	res += cnt[t][val]*cnt[t^1][val];
}

void cal(LL t){
	sort(tsk+1, tsk+m+1, cmp);
	memset(cnt, 0, sizeof cnt);
	LL res = 0;
	for(int i=1,L=0,R=0;i<=m;i++){
		while(R < tsk[i].r) modify(1, a[++R], 1, res);
		while(R > tsk[i].r) modify(1, a[R--],-1, res);
		while(L < tsk[i].l) modify(0, a[++L], 1, res);
		while(L > tsk[i].l) modify(0, a[L--],-1, res);
		ac[tsk[i].id] += t*res;
	}
}

void solve(){
	cin >> n; T = sqrt(n);
	for(int i=1;i<=n;i++) cin >> a[i];
	cin >> m;
	for(int i=1;i<=m;i++){
		for(int j=0;j<4;j++) cin >> ask[i][j];
		ask[i][0]--, ask[i][2]--;
	}
	init_tsk(1,3); cal( 1);
	init_tsk(1,2); cal(-1);
	init_tsk(0,3); cal(-1);
	init_tsk(0,2); cal( 1);
	for(int i=1;i<=m;i++) cout << ac[i] << "\n";
} 

int main(){
	ios::sync_with_stdio(false);
	int ce = 1;
//	cin >> ce;
	while(ce--) solve();
	
	return 0;
}
Prev
2021-10-25 20:15:00 # ACM
Next