【LuoguP3709】大爷的字符串题
题目链接: https://www.luogu.org/problemnew/show/P3709
前言
最近一个月是各种忙啊。先是准备了半个多月的合格考，然后终于回归了OI。最近一周又生病请假等就没有更新过题解。上次更新题解也是很久之前，因为中间有段时间颓废过度做项目，现在那个项目基本已经咕咕，因为懒得再下Visual Studio了。
这几天一直在做莫队，然后做到这道题，打算水篇题解。
分析
这题可以说是语文阅读理解神题，丝毫看不懂出题人意图是什么。
根据出题人的解释，一句话概括如下:
给你 N 个数, M 次询问区间[l, r]中众数的出现次数
然后就非常容易，但是字符集数据范围1e9需要离散化，我直接边读入边使用map处理。
根据一些其他题解的提示，我们开一个cnt数组记录区间内某个数出现的次数，然后用cntt数组记录cnt数组中数出现的次数。
在区间扩大时ans和cnt数组取max，然后区间缩小时就判断cntt是否已经为0，如果是就让ans减一。当然不能忘了区间更改时cnt和cntt肯定都会有所改变。
代码
评测详情(未开O2): Accepted 100 用时: 1634ms / 内存: 9740KB
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
| #include <iostream>
#include <stdio.h>
#include <map>
#include <math.h>
#include <algorithm>
using namespace std;
int read() {
int x= 0, f= 1;
char ch= getchar();
while(ch < '0' || ch > '9') {
if(ch == '-') f= -1;
ch= getchar();
}
while(ch >= '0' && ch <= '9') x= x * 10 + ch - '0', ch= getchar();
return x * f;
}
inline void write(int x) {
if(x < 0) x= -x, putchar('-');
if(x > 9) write(x / 10);
putchar('0' + x % 10);
return;
}
int n, m, a[200001], mapptr, cnt[200001], cntt[200001], nowans, ans[200001], ns;
map< int, int > mapping;
struct QUERY {
int id, l, r, bl;
int operator<(const QUERY &q2) const {
return bl == q2.bl ? r < q2.r : l < q2.l;
}
} qs[200001];
inline void add(int x) {
--cntt[cnt[x]];
++cntt[++cnt[x]];
nowans= max(nowans, cnt[x]);
return;
}
inline void del(int x) {
--cntt[cnt[x]];
if(!cntt[cnt[x]] && nowans == cnt[x]) --nowans;
++cntt[--cnt[x]];
return;
}
int main() {
n= read(), m= read(), ns= sqrt(n);
for(int i= 1; i <= n; i++) {
a[i]= read();
if(!mapping[a[i]]) mapping[a[i]]= ++mapptr;
a[i]= mapping[a[i]];
}
for(int i= 1; i <= m; i++) qs[i].l= read(), qs[i].r= read(), qs[i].id= i, qs[i].bl= (qs[i].l - 1) / ns;
sort(qs + 1, qs + m + 1);
int l= 1, r= 0;
for(int i= 1; i <= m; i++) {
while(l < qs[i].l) del(a[l++]);
while(l > qs[i].l) add(a[--l]);
while(r > qs[i].r) del(a[r--]);
while(r < qs[i].r) add(a[++r]);
ans[qs[i].id]= nowans;
}
for(int i= 1; i <= m; i++) write(-ans[i]), putchar('\n');
return 0;
}
|
