wujingfey @ 2023-10-17 17:01:06
神奇程序,目前调出来的问题是:手写的对拍都能过,但只有
#include<bits/stdc++.h>
using namespace std;
const int N=4e4+5,M=2e2+2,INF=1e9+10;
int n,m,a[N],b[N],c[N],ctop,maxn;
int tong[M][N],x;//tong[i][j]表示j元素到i块的前缀和
int st[M],ed[M],block,t,pos[N];
int maxx[M][M],maxxx[M][M];//记录块i-j间的出现次数最多的数出现了多少次,以及哪个数出现次数最多
int query(int l,int r){
int p=pos[l],q=pos[r];
int ans1=0,ans2=INF;//ans1最大出现次数,ans2记录是哪个数
int t[N]={0};//记录ai出现次数
if(p==q){//暴力查询区间内
for(int i=l;i<=r;i++)
t[a[i]]++;
for(int i=l;i<=r;i++){
if(t[a[i]]>ans1){
ans1=t[a[i]];
ans2=a[i];
}else if(t[a[i]]==ans1){//相等的时候更新更小的ai
ans2=min(ans2,a[i]);
}
}
return ans2;
}else{
ans1=maxx[p+1][q-1],ans2=maxxx[p+1][q-1];
(ans2==0)?ans2=INF:ans2;
for(int i=l;i<=ed[p];i++){
int times=tong[q-1][a[i]]-tong[p][a[i]];
if(t[a[i]]==0) t[a[i]]=times+1;
else t[a[i]]++;
}
for(int i=st[q];i<=r;i++){
int times=tong[q-1][a[i]]-tong[p][a[i]];
if(t[a[i]]==0) t[a[i]]=times+1;
else t[a[i]]++;
}
for(int i=l;i<=ed[p];i++){
if(t[a[i]]>ans1){
ans1=t[a[i]];
ans2=a[i];
}else if(t[a[i]]==ans1){//相等的时候更新更小的ai
ans2=min(ans2,a[i]);
}
}
for(int i=st[q];i<=r;i++){
if(t[a[i]]>ans1){
ans1=t[a[i]];
ans2=a[i];
}else if(t[a[i]]==ans1){//相等的时候更新更小的ai
ans2=min(ans2,a[i]);
}
}
return ans2;
}
}
signed main(){
// freopen("P4168_1.in","r",stdin);
// freopen("t1.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=a[i];
}
/*------------离散化--------------*/
sort(b+1,b+1+n);
for(int i=1;i<=n;i++)
if(b[i-1]!=b[i]||i==1)
c[++ctop]=b[i];
for(int i=1;i<=n;i++){
int www=lower_bound(c+1,c+ctop+1,a[i])-c;
a[i]=www;
}
/*-------------分块---------------*/
block=sqrt(n);
t=n/block;
if(n%block) t++;
for(int i=1;i<=t;i++){
st[i]=(i-1)*block+1;
ed[i]=i*block;
}
ed[t]=n;
for(int i=1;i<=t;i++)
for(int j=st[i];j<=ed[i];j++)
pos[j]=i;
/*--------------预处理前缀和、桶----------------*/
for(int i=1;i<=n;i++){
int p=pos[i];
tong[p][a[i]]++;
}
for(int i=1;i<=N-4;i++)
for(int j=1;j<=t;j++)
tong[j][i]=tong[j-1][i]+tong[j][i];
for(int i=1;i<=t;i++){//起点块
for(int j=i;j<=t;j++){//终点块
int res=0,num=INF;
for(int k=st[j];k<=ed[j];k++){//终点块每个元素
if(tong[j][a[k]]-tong[i-1][a[k]]>res){
res=tong[j][a[k]]-tong[i-1][a[k]];
num=a[k];
}else if(tong[j][a[k]]-tong[i-1][a[k]]==res){
num=min(num,a[k]);
}
}
maxx[i][j]=res,maxxx[i][j]=num;
}
}
/*-------------处理查询----------------*/
while(m--){
int l=0,r=0;
cin>>l>>r;
l=(l+x-1)%n+1,r=(r+x-1)%n+1;//解压密码
if(l>r) swap(l,r);
x=c[query(l,r)];
cout<<x<<"\n";
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
by wujingfey @ 2023-10-17 17:03:38
写了个暴力上去,正确性有保正。因为暴力直接复制的读入、离散化、输出,所以这些没毛病。并且 query 的 p==q 验证过无误
by lovely_hyzhuo @ 2023-10-17 17:08:28
我之前也是10pts,咋改的忘了。
你稍等
by wujingfey @ 2023-10-17 17:13:53
又拍了半天,发现不是初始化的问题,因为出现了第一行就错的情况