蓝桥杯2022年第十三届省赛真题-重复的数

解题思路:
离线处理(若一边读一边实时处理则为在线处理)，分块思想。
注意事项:
不要超时
参考代码:

#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <map>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstring>//strlen、strcmp 
#include <cmath>
#include <cstdlib>//malloc
#include <algorithm>
using namespace std;


#define maxn 100010
struct check{
	int L,R,ki,k;//k记录是第几个查询 
}ch[maxn];
int ans[maxn];//存储结果 
int a[maxn];//输入数据
int cnt[maxn];//区间L-R内统计数字i出现了多少次
int ci[maxn];//ci[i]:区间L-R内出现次数为i的元素个数 
int pos[maxn];//第i个元素所在的块
bool cmp(check a1,check a2){//按块将查询顺序排序，就是莫队算法 
	if(pos[a1.L] != pos[a2.L]){//按L所在的块排序，若其相等, 则再按R排序 
		return pos[a1.L] < pos[a2.L]; 
	}else if(pos[a1.L]&1){//奇偶性优化,奇数块的R降序排列,偶数块则升序 
		return a1.R > a2.R;
	}else{
		return a1.R < a2.R;
	} 
}
void add(int x){//扩大区间时(L左移或R右移)增加第x个数出现的次数 
	ci[cnt[a[x]]]--;//cnt[a[x]]加一个,对应其原来次数cnt[a[x]]要少一个元素 
	cnt[a[x]]++; 
	ci[cnt[a[x]]]++;//次数为cnt[a[x]]多了一个元素 
}
void del(int x){//缩小区间时(L右移或R左移)减小第x个数出现的次数
	ci[cnt[a[x]]]--;
	cnt[a[x]]--;
	ci[cnt[a[x]]]++;
} 

int main() {
	int n,m;
	scanf("%d",&n);
	int block = sqrt(n);//块的大小,为根号n时算法最快
	for(int i = 1;i <= n;i++){
		scanf("%d",&a[i]);
		pos[i] = (i - 1)/block + 1;//1~block个元素属于第1块，依次类推 
	}
	scanf("%d",&m);
	for(int i = 1;i <= m;i++){//读取所有查询，离线处理(若一边读一边实时处理则为在线处理) 
		scanf("%d%d%d",&ch[i].L,&ch[i].R,&ch[i].ki);
		ch[i].k = i;//记录是第几个查询
	}
	sort(ch+1,ch+1+m,cmp);//对所有查询排序
	int l=1,r=0; 
	for(int i = 1;i <= m;i++){
//每次l、r移动,可保证cnt、ci中的结果对应于当前的区间[l,r] 
		while(l<ch[i].L)
			del(l++);//先+1,然后删除上一个元素的次数
		while(r>ch[i].R)
			del(r--);//同上
		while(l>ch[i].L)
			add(--l);//先-1,然后这个元素的次数+1
		while(r<ch[i].R)
			add(++r);//同上
		ans[ch[i].k] = ci[ch[i].ki];//记录第i个结果 
	}
	for(int i = 1;i <= m;i++)
		printf("%d\n",ans[i]);//按询问顺序输出结果 
	
		
	return 0;
}