BlankAo @ 2020-08-31 08:44:32
loj上ac过此题(黄学长的数列分块入门),那里我用的块长度是80,才能勉强卡过。
但是我把代码复制到这里,却发现只有45pts。然后我把块长改为了sqrt(n)
,有60pts。最后我把块长改成了180,然后就100pts了?有人能说一下这是为什么吗,感觉没有ub
全程没有任何TLE,都是WA
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define wei(z) ( (z-1)/kie+1 )
#define ll(z) ( (z-1)*kie+1 )
#define rr(z) ( z*kie )
using namespace std;
int n,m,i,j,k,kie,ansx,ansn,a[101234],box[101234],f[1324][1324];
vector <int> lin[101234];
map <int,int> mop;
inline int read(){
int Xx=0,Ff=1;
char ch=getchar();
while(ch<'0' || ch>'9'){ if(ch=='-') Ff=-1; ch=getchar(); }
while(ch>='0' && ch<='9'){ Xx=(Xx<<1)+(Xx<<3)+ch-48; ch=getchar(); }
return Xx*Ff;
}
void prit(int x) {
if (x/10)prit(x/10);
putchar(x%10+'0');
}
void TieTie(){
int tmp[101234]={0},d[101234]={0};
for(i=1;i<=n;i++)tmp[i]=a[i];
sort(tmp+1,tmp+n+1);
int siz=unique(tmp+1,tmp+n+1)-tmp-1;
for(i=1;i<=n;i++)d[i]=lower_bound(tmp+1,tmp+siz+1,a[i])-tmp;
for(i=1;i<=n;i++)mop[d[i]]=a[i],a[i]=d[i];
}
int calc(int l,int r,int z){
return (upper_bound(lin[z].begin(),lin[z].end(),r)-lower_bound(lin[z].begin(),lin[z].end(),l));
}
void do_it(int l,int r,int z){
int got=calc(l,r,z);
if(got>ansx)ansx=got,ansn=z;
else if(got==ansx)ansn=min(ansn,z);
}
int main(){
n=read(),m=read();
kie=180;
for(i=1;i<=n;i++)a[i]=read();
TieTie();
for(i=1;i<=n;i++)lin[a[i]].push_back(i);
for(i=1;i<=wei(n);i++){
ansx=0,ansn=0;
memset(box,0,sizeof box);
for(j=i;j<=wei(n);j++){
for(k=ll(j);k<=rr(j);k++){
box[a[k]]++;
if(box[a[k]]>ansx)ansx=box[a[k]],ansn=a[k];
else if(box[a[k]]==ansx)ansn=min(ansn,a[k]);
}
f[i][j]=ansn;
}
}
while(m--){
int l,r;
l=read(),r=read();
l=(l+mop[ansn]-1)%n+1,r=(r+mop[ansn]-1)%n+1;
if(l>r)swap(l,r);
ansx=0,ansn=0;
if( wei(l)==wei(r) )for(int i=l;i<=r;i++)do_it(l,r,a[i]);
else{
for(i=l;i<=rr(wei(l));i++)do_it(l,r,a[i]);
for(i=ll(wei(r));i<=r;i++)do_it(l,r,a[i]);
if(wei(r)-wei(l)>=2)do_it(l,r,f[wei(l)+1][wei(r)-1]);
}
prit(mop[ansn]);putchar('\n');
}
}
by cmll02 @ 2020-08-31 09:09:35
也许是炸int?
by konjacq @ 2020-08-31 09:13:06
不清楚...说不定是块长乘块数暴数组了 没去算
by ___balalida___ @ 2020-08-31 09:24:30
你开个ll试试