【回滚莫队】洛谷 P3709 大爷的字符串题
2021-05-10 15:25:00 # ACM

——-

题链

$1.$普通莫队：维护两个数组$v[i]$与$cnt[i]$，$v[i]$表示$i$出现次数，$cnt[i]$表示出现$i$次的数有多少个；

对于新加入的数很好更新，$ans = max(ans,v[x])$，对于删除的数x，若这个的数被删之前$v[x] = 1$了，删完后就没了，并且出现$ans$次的数的个数$cnt[ans] = 1$，那么$x$就是此时的众数，删了它，那么$ans–$；

$2.$回滚莫队：发现新增一个数字可以很好的维护$ans$，但是删除一个数字不好维护，所以使用回滚莫队；

方式一

1.普通莫队：维护两个数组$v[i]$与$cnt[i]$，$v[i]$表示$i$出现次数，$cnt[i]$表示出现i次的数有多少个；

对于新加入的数很好更新，$ans = max(ans,v[x])$，对于删除的数$x$，若这个的数被删之前$v[x] = 1$了，删完后就没了，并且出现$ans$次的数的个数$cnt[ans] = 1$，那么$x$就是此时的众数，删了它，那么$ans–$；

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
#include <bits/stdc++.h>
using namespace std;
#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;
int a[MS];
int b[MS],tb;
struct node{
	int l,r,id;
}ask[MS];
int unit;

int v[MS];
int cnt[MS];
int ac[MS];

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

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		cin >> a[i];
		b[i] = a[i];
	}
	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++){
		a[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};
	}
	unit = sqrt(n);
	sort(ask+1,ask+m+1,cmp);
	int ans = 0;
	int L = 1 ,R = 0;
	for(int i=1;i<=m;i++){
		int l = ask[i].l;
		int r = ask[i].r;
		int id = ask[i].id;
		while(L < l){
			if(ans == v[a[L]] && cnt[v[a[L]]] == 1) ans--;
			cnt[v[a[L]]]--;
			v[a[L]]--;
			cnt[v[a[L]]]++;
			L++;
		}
		while(L > l){
			L--;
			cnt[v[a[L]]]--;
			v[a[L]]++;
			cnt[v[a[L]]]++;
			ans = max(ans,v[a[L]]);
		}
		while(R < r){
			R++;
			cnt[v[a[R]]]--;
			v[a[ R]]++;
			cnt[v[a[R]]]++;
			ans = max(ans,v[a[R]]);
		}
		while(R > r){
			if(ans == v[a[R]] && cnt[v[a[R]]] == 1) ans--;
			cnt[v[a[R]]]--;
			v[a[R]]--;
			cnt[v[a[R]]]++;
			R--;
		}
		ac[id] = ans;
	}
	for(int i=1;i<=m;i++){
		cout << -ac[i] << "\n";
	}
	

	return 0;
}

方式二

$2.$回滚莫队：发现新增一个数字可以很好的维护$ans$，但是删除一个数字不好维护，所以使用回滚莫队；

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
#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 f1 first
#define f2 second
#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 1000009

LL n,m;
LL a[MS];
LL b[MS],tb;

struct node{
	int l,r,id;
}ask[MS];
LL size,bknum;
LL bkl[MS],bkr[MS];
LL belong[MS];

LL cnt[MS];
LL cnp[MS];
LL ac[MS];

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;
		}
	}
}

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

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		cin >> a[i];
		b[i] = a[i];
	}
	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++){
		a[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_bk();
	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[a[j]]++;
				tmp = max(tmp,cnp[a[j]]);
			}
			ac[ask[i].id] = tmp;
			for(int j=ask[i].l;j<=ask[i].r;j++){
				cnp[a[j]]--;
			}
			continue;
		}
		if(belong[ask[i].l] != lastbk){
			for(;L<=bkr[belong[ask[i].l]];L++) cnt[a[L]]--;
			for(;R> bkr[belong[ask[i].l]];R--) cnt[a[R]]--;
			lastbk = belong[ask[i].l];
			ans = 0;
		}
		while(R < ask[i].r){
			cnt[a[++R]]++;
			ans = max(ans,cnt[a[R]]);
		}
		LL tmp = ans;
		while(L > ask[i].l){
			cnt[a[--L]]++;
			tmp = max(tmp,cnt[a[L]]);
		}
		ac[ask[i].id] = tmp;
		for(;L<=bkr[belong[ask[i].l]];L++) cnt[a[L]]--;
	}
	for(int i=1;i<=m;i++){
		cout << -ac[i] << "\n";
	}
	
	
	return 0;
}
Prev
2021-05-10 15:25:00 # ACM
Next