【莫队】洛谷 P4168 蒲公英
2021-05-12 16:20:00 # ACM

题链

——

题意在线求区间众数，若有多个输出权值最小的那个；

离线可采用莫队，在线由于区间众数不满足区间可加性（或许我不知道，不会维护），所以采用分块方式来写；

——

对于数据范围首先离散化，对长度为 $n$ 的数组分为 $\sqrt(n)$ 块，预处理出第 $i$ 块到第 $j$ 块的区间众数答案；

预处理出数组每一个不同值的位置，$vector$存储；

对于一个询问$[l,r]$，若 $l$ 所在的块和 $r$ 所在的块距离 $<= 1$，则暴力求解 $[l,r]$ 的答案；

否则可以将 $[l,r]$ 划分为 $[l,L)$,$[L,R]$,$(R,r]$ 三个块，其中 $[L,R]$ 是指 $[l,r]$ 之间所有的块；

可以发现ans要么是预处理出的 $[L,R]$ 的答案，要么$ans$是在，$[l,L)$ ,$(R,r]$ 之中，对于这两个区间，遍历每个值，用刚才存位置的 $vector$ 二分查找出现次数；

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ll long long
#define ULL unsigned long long
#define Pair pair<LL,LL>
#define ls rt<<1
#define rs rt<<1|1
#define Pi acos(-1.0)
#define eps 1e-6
#define DBINF 1e100
#define mod 998244353
#define MAXN 1e18
#define MS 40009
const int sqMS = sqrt(MS)+5;

int n,m;
int a[MS]; // 原数组 
int b[MS],tb;
int c[MS]; // 离散化数组 

int size,bknum; 		// 块大小，块数 
int bkl[MS],bkr[MS]; 	// 第 i 块左右区间 
int belong[MS]; 		// i 位置所属块号 

vector<int > vc[MS]; // 存 c[i] 位置 

int cnt[MS]; // 计数 
int p[sqMS][sqMS]; // i 块 ~ j 块 的区间众数 

void a_hash_c(){ // 离散化 
	sort(b+1,b+n+1);
	tb = 1;
	for(int i=2;i<=n;i++){
		if(b[i] != b[i-1]) b[++tb] = b[i];
	}
	for(int i=1;i<=n;i++){
		c[i] = lower_bound(b+1,b+tb+1,a[i]) - b;
	}
}

void init_bk(){ // 预处理块 
	size = sqrt(n);
	bknum = n/size;
	for(int i=1;i<=bknum;i++){
		bkl[i] = (i-1)*size+1;
		bkr[i] = i*size;
	}
	if(bkr[bknum] < n){
		bknum++;
		bkl[bknum] = bkr[bknum-1]+1;
		bkr[bknum] = n;
	}
	for(int i=1;i<=bknum;i++){
		for(int j=bkl[i];j<=bkr[i];j++){
			belong[j] = i;
		}
	}
}

void init_numpos(){ // 存每个数位置 
	for(int i=1;i<=n;i++){
		vc[c[i]].push_back(i);
	}
}

void init_p(){ // 预处理 i 块 ~ j 块 的区间众数 
	for(int i=1;i<=bknum;i++){
		int ans = 0;
		int cntans = 0;
		memset(cnt,0,sizeof cnt);
		for(int j=bkl[i];j<=n;j++){
			cnt[c[j]]++;
			if(cntans < cnt[c[j]] || (cntans == cnt[c[j]] && ans > c[j])){
				ans = c[j];
				cntans = cnt[c[j]];
			}
			p[i][belong[j]] = ans;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		cin >> a[i];
		b[i] = a[i];
	}
	a_hash_c();
	init_bk();
	init_numpos();
	init_p();
	int lastans = 0;
	while(m--){
		int l,r;
		cin >> l >> r;
		l = (l+lastans-1)%n+1;
		r = (r+lastans-1)%n+1;
		if(l > r) swap(l,r);
		
		if(belong[r] - belong[l] <= 1){ // l,r之间没有完整块 
			int ans = 0;
			int cntans = 0;
			for(int i=l;i<=r;i++){
				int lpos = lower_bound(vc[c[i]].begin(),vc[c[i]].end(),l) - vc[c[i]].begin();
				int rpos = upper_bound(vc[c[i]].begin(),vc[c[i]].end(),r) - vc[c[i]].begin();
				int cc = rpos - lpos;
				if(cc > cntans || (cc == cntans && c[i] < ans)){
					ans = c[i];
					cntans = cc;
				}
			}
			cout << b[ans] << "\n";
			lastans = b[ans];
			continue;
		}
		int L = belong[l]+1;
		int R = belong[r]-1;
		int ans = p[L][R]; // 初始化为 l,r 之间的块的区间众数 
		int lanspos = lower_bound(vc[ans].begin(),vc[ans].end(),l) - vc[ans].begin();
		int ranspos = lower_bound(vc[ans].begin(),vc[ans].end(),r) - vc[ans].begin();
		int cntans = ranspos - lanspos; // [l,r] 区间内 ans 出现次数 
		
		for(int i=l;i<=bkl[L]-1;i++){ // 暴力处理左边不完整块 
			int lpos = lower_bound(vc[c[i]].begin(),vc[c[i]].end(),l) - vc[c[i]].begin();
			int rpos = upper_bound(vc[c[i]].begin(),vc[c[i]].end(),r) - vc[c[i]].begin();
			int cc = rpos - lpos;
			if(cc > cntans || (cc == cntans && c[i] < ans)){
				ans = c[i];
				cntans = cc;
			}
		}
		
		for(int i=bkr[R]+1;i<=r;i++){ // 暴力处理右边不完整块
			int lpos = lower_bound(vc[c[i]].begin(),vc[c[i]].end(),l) - vc[c[i]].begin();
			int rpos = upper_bound(vc[c[i]].begin(),vc[c[i]].end(),r) - vc[c[i]].begin();
			int cc = rpos - lpos;
			if(cc > cntans || (cc == cntans && c[i] < ans)){
				ans = c[i];
				cntans = cc;
			}
		}
		
		cout << b[ans] << "\n";
		lastans = b[ans];
	}
	
	return 0;
}
Prev
2021-05-12 16:20:00 # ACM
Next