题解:分块+离散化
解题报告:
一个分块典型题呢qwq还是挺妙的毕竟是道黑题
然,然后发现忘记放链接了先放链接QAQ
有两三种解法,都港下qwq
第一个是O(n5/3)的复杂度,谢总说不够优秀没有港,等下看了再写qwq
umm看了下大概明白了似乎qwq
虽然不知道我看的是不是这个解法×
就是法二不是有个f[][]表示区间内众数是谁嘛
然后法一中除了开这个以外还开了color[][][]表示区间内每个数的出现次数
这样就不用二分了!
但是这样的话就很容易T?是要吸氧的qwq
代码就懒得放了(主要懒得打了,,,这个题目的细节太多了,,,QAQ
第二个是O(n√nlogn)的,这个港下
就先分块,处理每个块里面的众数
然后对于每个询问,答案有两种可能
第一种,是中间被完全包含的块的众数
第二种,是两边出现过的数
然后再开个vector相当于桶排一样存下每个值所有出现的位置,每次lowerbound暴力查找第二种(两边的直接强行暴力枚举就好
第一种的话可以先暴力预处理出f[i][j]表示第i块到第j块的众数,这样每次就可以直接查了qwq)
然后就可以了,正确性我感觉还挺显然的就不证明辣?
其实我都懒得打这个代码了,,,本来感觉想通了思路之后大概不太复杂?但总有人问我做了没有,,,就很烦,,,于是就做了下
然后发现细节挺多挺麻烦:D
于是就耗了一天总算打出来了
布星啊现在状态越来越差了随便丢我个题都要调好久好久好久的,效率极低QAQ
对了这题给了我个小惊喜欸,,,就是,我才知道我的离散化一直有一点儿问题...就是我unique的那个tot,应该还要-=1我一直没有这么做,但玄学的是一直好像也没问题,,,ummm,,,很迷,,,幸好NOIp中我没有用离散化啥的不然怕是直接GG了?QAQ
然后放个代码就走了,就是记得把第三个方法学下趴qwq
#include<bits/stdc++.h> using namespace std; #define rp(i,x,y) for(register int i=x;i<=y;++i) #define my(i,x,y) for(register int i=y;i>=x;--i) +,sqtN=+; int n,m,cjk,len,a[N],b[N],st[N],num[N],mx[sqtN][sqtN]; vector<int>gg[N]; inline int read() { ;; '))ch=getchar(); ; )+(x<<)+(ch^'),ch=getchar(); return y?x:-x; } int cal(int x,int l,int r) { ); int L,R,ret1,ret2; L=,R=gg[x].size()-,ret1=R; while(L<=R) { ; ; ; } L=,R=gg[x].size()-,ret2=L; while(L<=R) { ; ; ; } ,); } int main() { // freopen("cjk.in","r",stdin); // freopen("cjk.out","w",stdout); n=read();m=read();len=;cjk=(n-)/len+; rp(i,,n)st[i]=a[i]=read(); sort(st+,st++n);,st++n)-st-; rp(i,,n)a[i]=lower_bound(st+,st++tot,a[i])-st; rp(i,,n)gg[a[i]].push_back(i); rp(i,,n)b[i]=(i-)/len+; rp(i,,cjk) { memset(num,,sizeof(num)); ; rp(j,i,cjk) { rp(k,(j-)*len+,min(n,j*len)) { num[a[k]]++; if(num[a[k]]>num[x] || (num[a[k]]==num[x] && x>a[k]))x=a[k]; } mx[i][j]=x; } } ; while(m--) { )%n+,r=(read()+ans-)%n+,mxans=,x=;if(l>r)swap(l,r); ) rp(i,l,r) { int d=cal(a[i],l,r); if(d>mxans || (d==mxans && x>a[i]))mxans=d,x=a[i]; } else { x=mx[b[l]+][b[r]-];mxans=cal(x,l,r);//二分和max都打挂了?哭了QAQ );++i) { int d=cal(a[i],l,r); if(d>mxans || (d==mxans && x>a[i]))mxans=d,x=a[i]; } && (i==r || i%len!=);--i) { int d=cal(a[i],l,r); if(d>mxans|| (d==mxans && x>a[i]))mxans=d,x=a[i]; } } printf("%d\n",ans=st[x]); } ; }
第三个是听说有个O(n√n)的?然后我不会:D先把解法二写了再来学这个qwq