LOJ #6285. 数列分块入门 9-分块(查询区间的最小众数)
#6285. 数列分块入门 9内存限制：256 MiB时间限制：1500 ms标准输入输出
题目类型：传统评测方式：文本比较
上传者： hzwer
提交提交记录统计测试数据讨论
2
题目描述
给出一个长为 nn 的数列，以及 nn 个操作，操作涉及询问区间的最小众数。
输入格式
第一行输入一个数字 nn。
第二行输入 nn 个数字，第 ii 个数字为 a_iai，以空格隔开。
接下来输入 nn 行询问，每行输入两个数字 ll、rr，以空格隔开。
表示查询位于 的数字的众数。
输出格式
对于每次询问，输出一行一个数字表示答案。
样例
样例输入
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,pos,val;
10 int c,f;
11 vector<int> vec;
12 map<int,int> b;
13 bool vis;
14
15 #define reads(n) FastIO::read(n)
16 namespace FastIO
17 {
18 const int SIZE = 1 << 16;
19 char buf, obuf, str;
20 int bi = SIZE, bn = SIZE, opt;
21 int read(char *s)
22 {
23 while (bn)
24 {
25 for (; bi < bn && buf <= ' '; 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++)
35 s = buf;
36 if (bi < bn)
37 break;
38 bn = fread(buf, 1, SIZE, stdin);
39 bi = 0;
40 }
41 s = 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 == '-')
51 bf = -1, i++;
52 else
53 bf = 1;
54 for (x = 0; i < n; i++)
55 x = x * 10 + str - '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=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]++;
70 if(c]>nummax||(c]==nummax&&val]<val)){
71 nummax=c];
72 maxx=a;
73 }
74 f]=maxx;
75 }
76 }
77
78 int length(int l,int r,int val)
79 {
80 return upper_bound(vec.begin(),vec.end(),r)-lower_bound(vec.begin(),vec.end(),l);
81 }
82
83 int query(int l,int r)
84 {
85 int maxx=f+1]-1],nummax=0;
86 memset(vis,0,sizeof(vis));
87 nummax=length(l,r,maxx);
88 vis=1;
89 for(int i=l;i<=min(pos*m,r);i++){
90 if(vis]==0){
91 vis]=1;
92 int ret=length(l,r,a);
93 if(ret>nummax||(ret==nummax&&val]<val)){
94 nummax=ret;
95 maxx=a;
96 }
97 }
98 }
99 if(pos!=pos){
100 for(int i=(pos-1)*m+1;i<=r;i++){
101 if(vis]==0){
102 vis]=1;
103 int ret=length(l,r,a);
104 if(ret>nummax||(ret==nummax&&val]<val)){
105 nummax=ret;
106 maxx=a;
107 }
108 }
109 }
110 }
111 return val;
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);
122 scanf("%d",&a);
123 pos=(i-1)/m+1;
124 if(b]==0){
125 b]=++id;
126 val=a;
127 }
128 a=b];
129 vec].push_back(i);
130 }
131 // for(int i=1;i<=pos;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 }完结，再见分块！
文档来源：51CTO技术博客https://blog.51cto.com/u_15310764/3167988
页:
[1]