首先上题目
题目描述
给出一个长为n的数列，以及n个操作，操作涉及询问区间的最小众数。
第一行输入一个数字n。
第二行输入n个数字，第i个数字为a[i]，以空格隔开。
接下来输入n行询问，每行输入两个数字l,r以空格隔开。
表示查询位于[l,r]的数字的众数。这道题遇到了之前没有遇到过的众数问题，那么我们怎么解决呢？
众所周知，直接暴力可以骗分
暴力显然是不行的，因此我们要考虑其他方法。
根据陈立杰的区间众数解题报告可知，a和b集合的众数，一定属于a集合的众数与b集合的交集，即一定在这两个集合的某一个集合中出现（似乎是废话）
解题思路：
如果边界是[l,r]，l在第a块，r在第b块，可以分成三个部分：
1.l到a最后一块
2.a+1~b-1块
3.第b块到r
根据上面的性质，如果我们预先处理a+1~b-1块的众数，再去遍历判断第一部分和第三部分是否有更合适的众数，这道题就能做出来了。
具体细节在下面代码中说：
1.建立分块：
#include<bits/stdc++.h>
using namespace std;
/*
1.将数组v[i]离散化，不记录其值，只记录其位数
2.分块查询
*/
const int N=100005;
int n,blo,id,bl[N],v[N],val[N],cnt[N];
int f[1005][1005];
vector<int> ve[N];//储存编号相同，就是数相同时原来的第几个值，用来二分求众数
map<int,int> mp;其中，bl存储每个块的边界，val存储原来的v数组，cnt用来计算每个数出现的个数。
进入主函数
在主函数中，由于输入进去的v数组太大，我们并不需要那么大的数
因此可以进行离散化，相同的数具有相同的标号，再用val来存储原来的v数组
当需要查询其值大小的时候，只需要用 val[v[i]] 就行了
ve函数其实是查编号为v[i]的数在第几位出现过，为后来的二分找下标做处理
int main()
{
cin>>n;
blo=200;//每一块分成200，在后期寻找中好计算
for(int i=1;i<=n;i++)
{
cin>>v[i];
if(!mp[v[i]])//之前没有出现过
{
mp[v[i]]=++id;//第几个出现的数
val[id]=v[i];//记录编号为i的原值
}
v[i]=mp[v[i]];//记录其是第几个出现的数(离散化）
ve[v[i]].push_back(i);//第v[i]个出现的数在哪里出现，此句话为记录个数所用，
}
for(int i=1;i<=n;i++) bl[i]=(i-1)/blo+1;
for(int i=1;i<=bl[n];i++) pre(i);//将每一段进行众数排序
for(int i=1;i<=n;i++)
{
int a,b;
cin>>a>>b;
if(a>b) swap(a,b);
cout<<val[query(a,b)]<<endl;//输出众数
}
return 0;
}在
for(int i=1;i<=bl[n];i++) pre(i);这个语句是为了预处理在[i,n]中每个区间的众数，接下来上代码：
预处理众数
我们将整个处理众数的过程看成是一个表
那么我们需要算出来每一块到每一块区间的众数，包括其本身
假如说有四个区间a,b,c,d;
那么我们就需要算a-b，a-c，a-d，b-c，b-d，c-d，a,b,c,d这一共10个区间的众数。
我们可以将这个看成是一个表格
那么就可以开一个二维数组f[1000][1000]用来记录每一块的众数是什么
void pre(int x)//预处理每一段的众数
{
memset(cnt,0,sizeof(cnt));//一开始进行初始化
int mx=0,ans=0;
for(int i=(x-1)*blo+1;i<=n;i++)//第x个块左边界到n中的众数
{
cnt[v[i]]++;//记录每一段每个数出现的个数
int t=bl[i];//记录这是第几段
if(cnt[v[i]]>mx||(cnt[v[i]]==mx&&val[v[i]]<val[ans]))//找最小众数
ans=v[i],mx=cnt[v[i]];
//x是初始段，t是末尾段
f[x][t]=ans;//这一段众数是ans
}
}至此，我们所需要的就已经准备好了。
查询，解题
因为我们已经预先处理好每一块的众数，因此只需要判断左右两边多出来的那一小部分中，有没有数字可以当成是新的众数。
其中第一个query函数是照应了在建函数中ve[v[i]].push_back(i) 这一步，搜索从l到r中标号为v[i]的数出现了多少次
int query(int l,int r,int x)//二分查找这一块内编号为x的数量(ve[v[i]].push_back(i);)
{
int t=upper_bound(ve[x].begin(),ve[x].end(),r)-lower_bound(ve[x].begin(),ve[x].end(),l);//大下标减去小下标
//注意前面是upper_bound，后面是lower_bound
return t;
}
int query(int a,int b)
{
int ans,mx;
ans=f[bl[a]+1][bl[b]-1];//意思是在(bl[a]+1~bl[b]-1)这一序列中的众数
mx=query(a,b,ans);//查找这个众数在此区间里出现的个数
for(int i=a;i<=min(bl[a]*blo,b);i++)
{
int t=query(a,b,v[i]);//暴力查找左边多余部分每个数的数量
if(t>mx||(t==mx&&val[v[i]]<val[ans]))
ans=v[i],mx=t;
}
if(bl[a]!=bl[b])
for(int i=(bl[b]-1)*blo+1;i<=b;i++)//暴力查找右边多余部分每个数的数量
{
int t=query(a,b,v[i]);
if(t>mx||(t==mx&&val[v[i]]<val[ans]))
ans=v[i],mx=t;
}
return ans;
}