LOJ #6285. 数列分块入门 9-分块(查询区间的最小众数)

绝代码农

#6285. 数列分块入门 9
内存限制：256 MiB时间限制：1500 ms标准输入输出
题目类型：传统评测方式：文本比较
上传者： hzwer
提交提交记录统计测试数据讨论
2
题目描述

给出一个长为 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。
以上都是踩过的坑，灰常开心，写到自闭，最后看了别人的，发现长度开大了，改了就过了。
代码:

1 //#6285. 数列分块入门 9-查询区间的最小众数
  2 #include<bits/stdc++.h>
  3 using namespace std;
  4 typedef long long ll;
  5 const int maxn=1e5+10;
  6 const int maxm=2e3+20;
  7 
  8 int n,m,id=0;
  9 int a[maxn],pos[maxn],val[maxn];
 10 int c[maxn],f[maxm][maxm];
 11 vector<int> vec[maxn];
 12 map<int,int> b;
 13 bool vis[maxn];
 14 
 15 #define reads(n) FastIO::read(n)
 16 namespace FastIO
 17 {
 18 const int SIZE = 1 << 16;
 19 char buf[SIZE], obuf[SIZE], str[60];
 20 int bi = SIZE, bn = SIZE, opt;
 21 int read(char *s)
 22 {
 23   while (bn)
 24   {
 25     for (; bi < bn && buf[bi] <= ' '; bi++);
 26     if (bi < bn)
 27       break;
 28     bn = fread(buf, 1, SIZE, stdin);
 29     bi = 0;
 30   }
 31   int sn = 0;
 32   while (bn)
 33   {
 34     for (; bi < bn && buf[bi] > ' '; bi++)
 35       s[sn++] = buf[bi];
 36     if (bi < bn)
 37       break;
 38     bn = fread(buf, 1, SIZE, stdin);
 39     bi = 0;
 40   }
 41   s[sn] = 0;
 42   return sn;
 43 }
 44 bool read(int& x)
 45 {
 46   int n = read(str), bf;
 47   if (!n)
 48     return 0;
 49   int i = 0;
 50   if (str[i] == '-')
 51     bf = -1, i++;
 52   else
 53     bf = 1;
 54   for (x = 0; i < n; i++)
 55     x = x * 10 + str[i] - '0';
 56   if (bf < 0)
 57     x = -x;
 58   return 1;
 59 }
 60 };
 61 
 62 void init(int x)
 63 {
 64 //  for(int i=0;i<=1e5+10;i++)
 65 //    c[i]=0;
 66   int nummax=0,maxx=0;
 67   memset(c,0,sizeof(c));
 68   for(int i=(x-1)*m+1;i<=n;i++){
 69     c[a[i]]++;
 70     if(c[a[i]]>nummax||(c[a[i]]==nummax&&val[a[i]]<val[maxx])){
 71       nummax=c[a[i]];
 72       maxx=a[i];
 73     }
 74     f[x][pos[i]]=maxx;
 75   }
 76 }
 77 
 78 int length(int l,int r,int val)
 79 {
 80   return upper_bound(vec[val].begin(),vec[val].end(),r)-lower_bound(vec[val].begin(),vec[val].end(),l);
 81 }
 82 
 83 int query(int l,int r)
 84 {
 85   int maxx=f[pos[l]+1][pos[r]-1],nummax=0;
 86   memset(vis,0,sizeof(vis));
 87   nummax=length(l,r,maxx);
 88   vis[maxx]=1;
 89   for(int i=l;i<=min(pos[l]*m,r);i++){
 90     if(vis[a[i]]==0){
 91       vis[a[i]]=1;
 92       int ret=length(l,r,a[i]);
 93       if(ret>nummax||(ret==nummax&&val[a[i]]<val[maxx])){
 94         nummax=ret;
 95         maxx=a[i];
 96       }
 97     }
 98   }
 99   if(pos[l]!=pos[r]){
100     for(int i=(pos[r]-1)*m+1;i<=r;i++){
101       if(vis[a[i]]==0){
102         vis[a[i]]=1;
103         int ret=length(l,r,a[i]);
104         if(ret>nummax||(ret==nummax&&val[a[i]]<val[maxx])){
105           nummax=ret;
106           maxx=a[i];
107         }
108       }
109     }
110   }
111   return val[maxx];
112 }
113 
114 int main()
115 {
116 //  reads(n);
117   scanf("%d",&n);
118 //  m=sqrt(n);
119   m=80;
120   for(int i=1;i<=n;i++){
121 //    reads(a[i]);
122     scanf("%d",&a[i]);
123     pos[i]=(i-1)/m+1;
124     if(b[a[i]]==0){
125       b[a[i]]=++id;
126       val[id]=a[i];
127     }
128     a[i]=b[a[i]];
129     vec[a[i]].push_back(i);
130   }
131 //  for(int i=1;i<=pos[n];i++){
132   for(int i=1;i<=n/m+1;i++){//块长为m，那么最多为n/m+1个块
133     init(i);
134   }
135   for(int i=1;i<=n;i++){
136     int l,r;
137 //    reads(l);
138 //    reads(r);
139     scanf("%d%d",&l,&r);
140     printf("%d\n",query(l,r));
141   }
142 }

完结，再见分块！