【回滚莫队】AT1219 歴史の研究
2021-05-10 14:19:00 # ACM

题链

题意询问区间最大价值，最大价值指区间中 $a[i]$出现次数$*a[i]$ 的最大值；

莫队解决：发现新增一个数字很好维护最大值（计数就行），但是删除一个数字困难，所以用到回滚莫队

这篇博客看的通俗易懂，代码也是~

回滚莫队

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
//#include <bits/stdc++.h>
#include <iostream> 
#include <algorithm>
#include <cmath>
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 1000000007
#define MAXN 1e18
#define MS 1000009

LL n,m;
LL a[MS]; 	// 原数组 
LL b[MS],tb;// 离散化所用临时数组 
LL c[MS];	// 离散化后的数组 
struct node{
	int l,r,id;
}ask[MS];
LL sizee,bknum; // 每块大小，总块数 
LL belong[MS]; // 下标 i 所属区块标号 
LL bkl[MS],bkr[MS]; // 区块 i 的左右区间 

LL cnp[MS]; // 询问的左右区间所属同一块时暴力处理所用临时数组 
LL cnt[MS]; // cnt[i]表示 i 出现次数 
LL ac[MS];  // 记录答案 

bool cmp(node t1,node t2){
	if(belong[t1.l] ^ belong[t2.l]) return t1.l < t2.l;
	return t1.r < t2.r;
}

void init_block(){
	sizee = sqrt(n);
	bknum = n/sizee;
	for(int i=1;i<=bknum;i++){
		bkl[i] = (i-1)*sizee+1;
		bkr[i] = i*sizee;
	}
	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;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		cin >> a[i];
		b[i] = a[i];
	}
	// 离散化 c[]为离散化后处理数组，a[]为原数组 
	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;
	}
	// 离线处理询问，分块排序 
	for(int i=1;i<=m;i++){
		int l,r;
		cin >> l >> r;
		ask[i] = {l,r,i};
	}
	init_block(); // 预处理下标所属的块，每块的区间 
	sort(ask+1,ask+m+1,cmp);
	// 回滚莫队 
	int L = 1,R = 0;
	int lastbk = 0;
	LL ans = 0;
	for(int i=1;i<=m;i++){ 
		if(belong[ask[i].l] == belong[ask[i].r]){ // 所属同一块的情况暴力处理 
			LL tmp = 0;
			for(int j=ask[i].l;j<=ask[i].r;j++){
				cnp[c[j]]++;
				tmp = max(tmp,cnp[c[j]]*a[j]);
			} 
			ac[ask[i].id] = tmp;
			for(int j=ask[i].l;j<=ask[i].r;j++){
				cnp[c[j]] = 0;
			}
			continue;
		}
		if(belong[ask[i].l] != lastbk){ // 询问的左区间 与上一次询问左区间不同时 更新左右指针 
			for(;L<=bkr[belong[ask[i].l]];L++) cnt[c[L]]--; // L 更新到区块右区间+1 
			for(;R> bkr[belong[ask[i].l]];R--) cnt[c[R]]--; // R 更新到区块右区间 
			lastbk = belong[ask[i].l]; // 更新区块 
			ans = 0; // 记录ans归零 
		}
		// 右指针直接右移，因为询问左区间同属于一个块的时，对于右区间排序是按照从小到大 
		while(R < ask[i].r){
			cnt[c[++R]]++;
			ans = max(ans,cnt[c[R]]*a[R]);
		}
		// 由于询问的左区间同属于一个块，但可能不是有序的，所以临时记录答案，之后左指针得归位 
		LL tmp = ans;
		while(L > ask[i].l){
			cnt[c[--L]]++;
			tmp = max(tmp,cnt[c[L]]*a[L]);
		}
		ac[ask[i].id] = tmp;
		// 回滚 
		while(L <= bkr[belong[ask[i].l]]) cnt[c[L++]]--;
	}
	for(int i=1;i<=m;i++){
		cout << ac[i] << "\n";
	}
	
	
	return 0;
}
Prev
2021-05-10 14:19:00 # ACM
Next