题目描述
给出一个长为 nn 的数列，以及 nn 个操作，操作涉及询问区间的最小众数。
输入格式
第一行输入一个数字 nn。
第二行输入 nn 个数字，第 ii 个数字为 a_iai，以空格隔开。
接下来输入 nn 行询问，每行输入两个数字 ll、rr，以空格隔开。
表示查询位于 [l,r][l,r] 的数字的众数。
输出格式
对于每次询问，输出一行一个数字表示答案。
样例
样例输入
4
1 2 2 4
1 2
1 4
2 4
3 4样例输出
1
2
2
2数据范围与提示
对于 100\%100% 的数据，1 \leq n \leq 100000, -2^{31} \leq \mathrm{others}1≤n≤100000,−231≤others、\mathrm{ans} \leq 2^{31}-1ans≤231−1。
这道题，我交了82发，微笑:)
分块根号n是过不去的，是的，开80长度可以过，然后要打标记，查询的时候前一部分找过的，就打标记后一部分就不用再找了。
然后就是标记要用bool型，开int过不了，重新编号要用map，int过不了，还有就是主函数预处理的时候，块数是n/m+1,不再是m+1。
以上都是踩过的坑，灰常开心，写到自闭，最后看了别人的，发现长度开大了，改了就过了。
代码:
//#6285. 数列分块入门 9-查询区间的最小众数
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+;
const int maxm=2e3+; int n,m,id=;
int a[maxn],pos[maxn],val[maxn];
int c[maxn],f[maxm][maxm];
vector<int> vec[maxn];
map<int,int> b;
bool vis[maxn]; #define reads(n) FastIO::read(n)
namespace FastIO
{
const int SIZE = << ;
char buf[SIZE], obuf[SIZE], str[];
int bi = SIZE, bn = SIZE, opt;
int read(char *s)
{
while (bn)
{
for (; bi < bn && buf[bi] <= ' '; bi++);
if (bi < bn)
break;
bn = fread(buf, , SIZE, stdin);
bi = ;
}
int sn = ;
while (bn)
{
for (; bi < bn && buf[bi] > ' '; bi++)
s[sn++] = buf[bi];
if (bi < bn)
break;
bn = fread(buf, , SIZE, stdin);
bi = ;
}
s[sn] = ;
return sn;
}
bool read(int& x)
{
int n = read(str), bf;
if (!n)
return ;
int i = ;
if (str[i] == '-')
bf = -, i++;
else
bf = ;
for (x = ; i < n; i++)
x = x * + str[i] - '';
if (bf < )
x = -x;
return ;
}
}; void init(int x)
{
// for(int i=0;i<=1e5+10;i++)
// c[i]=0;
int nummax=,maxx=;
memset(c,,sizeof(c));
for(int i=(x-)*m+;i<=n;i++){
c[a[i]]++;
if(c[a[i]]>nummax||(c[a[i]]==nummax&&val[a[i]]<val[maxx])){
nummax=c[a[i]];
maxx=a[i];
}
f[x][pos[i]]=maxx;
}
} int length(int l,int r,int val)
{
return upper_bound(vec[val].begin(),vec[val].end(),r)-lower_bound(vec[val].begin(),vec[val].end(),l);
} int query(int l,int r)
{
int maxx=f[pos[l]+][pos[r]-],nummax=;
memset(vis,,sizeof(vis));
nummax=length(l,r,maxx);
vis[maxx]=;
for(int i=l;i<=min(pos[l]*m,r);i++){
if(vis[a[i]]==){
vis[a[i]]=;
int ret=length(l,r,a[i]);
if(ret>nummax||(ret==nummax&&val[a[i]]<val[maxx])){
nummax=ret;
maxx=a[i];
}
}
}
if(pos[l]!=pos[r]){
for(int i=(pos[r]-)*m+;i<=r;i++){
if(vis[a[i]]==){
vis[a[i]]=;
int ret=length(l,r,a[i]);
if(ret>nummax||(ret==nummax&&val[a[i]]<val[maxx])){
nummax=ret;
maxx=a[i];
}
}
}
}
return val[maxx];
} int main()
{
// reads(n);
scanf("%d",&n);
// m=sqrt(n);
m=;
for(int i=;i<=n;i++){
// reads(a[i]);
scanf("%d",&a[i]);
pos[i]=(i-)/m+;
if(b[a[i]]==){
b[a[i]]=++id;
val[id]=a[i];
}
a[i]=b[a[i]];
vec[a[i]].push_back(i);
}
// for(int i=1;i<=pos[n];i++){
for(int i=;i<=n/m+;i++){//块长为m，那么最多为n/m+1个块
init(i);
}
for(int i=;i<=n;i++){
int l,r;
// reads(l);
// reads(r);
scanf("%d%d",&l,&r);
printf("%d\n",query(l,r));
}
}
完结，再见分块！