大爷的字符串题

题目背景

在那遥远的西南有一所学校，

/*被和谐部分*/

然后去参加该省省选虐场，

然后某蒟蒻不会做，所以也出了一个字符串题：

题目描述

给你一个字符串 $a$，每次询问一段区间的贡献。

贡献定义：

每次从这个区间中拿出一个字符 $x$ ，然后把 $x$ 从这个区间中删除，直到区间为空。你要维护一个集合 $S$。

• 如果 $S$ 为空，你 rp 减 $1$。
• 如果 $S$ 中有一个元素不小于 $x$，则你 rp 减 $1$，清空 $S$。
• 之后将 $x$ 插入 $S$。

由于你是大爷，平时做过的题考试都会考到，所以每次询问你搞完这段区间的字符之后最多还有多少 rp？rp 初始为 $0$。

询问之间不互相影响~

输入格式

第一行两个整数 $n$，$m$，表示字符串长度与询问次数。

之后一行 $n$ 个数，第 $i$ 个整数表示给出的字符串的第 $i$ 个字符 $x_i$。

接下来 $m$ 行，每行两个整数 $l,r$，表示一次询问的区间。

输出格式

对于每次询问，输出一行一个整数表示答案。

样例 #1

样例输入 #1

3 3
3 3 3
3 3
3 3
3 3
1
2
3
4
5

样例输出 #1

-1
-1
-1
1
2
3

提示

数据规模与约定

• 对于 $10\%$ 的数据，是样例。
• 对于另外 $10\%$ 的数据，保证 $n,m\le 100$；
• 对于另外 $10\%$ 的数据，保证 $n,m\le 10^3$；
• 对于另外 $10\%$ 的数据，保证 $n,m\le 10^4$；
• 对于另外 $10\%$ 的数据，保证 $n,m\le 10^5$；
• 对于 $100\%$ 的数据，$1\le n,m\le 2\times 10^5$，$1\le a_i\le 10^9$，$1\le l,r\le n$。

保证数据像某省省选 day1T2 一样 sb，大家尽情用暴力水过题吧！

没事，你只要在一个好学校，就算这题只能拿到 10 分，也可以进队了

#include
using namespace std;
const int N=1e6+10;
typedef long long ll;
int n,m,a[N];
unordered_map<int,int> mp;
int pos[N],Id=0;
int c[N],sum=0,num[N],ans[N],L=1,R=0;
//题意：求区间众数出现的次数的相反数
struct modui{
	int l,r,id;
}s[N];
bool cmp(modui x,modui y){//按左端点分块，然后在同一个块当中区间右端点要递增
	if (pos[x.l]!=pos[y.l]) return x.l<y.l;
    if(pos[x.l]&1) return x.r<y.r;//奇偶性优化
	return x.r>y.r;//都是为了加速
}
//c[i]代表i出现的次数
//num[i]代表出现次数为i的数的个数
void add(int x){
    //增加一个数，计数器删除原来次数的出现次数，更新现在的次数，更新答案
	--num[c[x]];
	++c[x];
	++num[c[x]];
	sum=max(sum,c[x]);//如果比当前众数出现的次数多，那么更新答案
}
void del(int x){
    //删除一个数，计数器更新原来的出现次数，更新现在的次数，再更新答案
	--num[c[x]];
	if(c[x]==sum){
        //如果只有一个众数，删除这个数后，答案必定减1
		if(num[c[x]]==0) sum--;
	}
	--c[x];
	++num[c[x]];
	sum=max(sum,c[x]);//如果比当前众数出现的次数多，那么更新答案
}
void query(int l,int r,int id){
	while (L<l) del(a[L++]);//左指针往右移删除
	while (L>l) add(a[--L]);//左指针往左移加入
	while (R<r) add(a[++R]);//右指针往右移加入
	while (R>r) del(a[R--]);//右指针往左移删除
	ans[id]=sum;//记录答案
	return;
}
int main(){
	scanf("%d%d",&n,&m);
	int dis=sqrt(n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(mp[a[i]]) a[i]=mp[a[i]];//离散化
		else mp[a[i]]=++Id,a[i]=Id;
		pos[i]=(i-1)/dis+1;//分块
	}
	for(int i=1;i<=m;i++){
		scanf("%d %d",&s[i].l,&s[i].r);
		s[i].id=i;
	}
	sort(s+1,s+1+m,cmp);
	for(int i=1;i<=m;i++) query(s[i].l,s[i].r,s[i].id);
	for(int i=1;i<=m;i++) printf("%d\n",-ans[i]);
	return 0;
}
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