这道题目质量还是很不错的 从中我发现我的一些漏洞。
前言：并不是你认为一定对的代码就是一定对的 能让你近乎崩溃的代码有的时候只不过是你的一点粗心罢了。
看完题目后一定要审题这是一道强制在线的题目 所以注意输入的问题 。
然后问的是蒲公英在某个区间的众数 线段树 树状数组都败下阵了
这时分块显得比较优秀。考虑将整个区间分块 然后 每次询问分为三个区间 左边 右边 块内 自然答案也在其中产生。
朴素做法维护块内每个数字出现的次数暴力的去询问两边然后更新答案 复杂度是可以过的。
这种方法也极大的体现了分块的特点。 只需要暴力对两边进行询问即可。
自然我第一次wa的原因 是 没看见在线输入 。。。
第二次RE 发现数组可能在越界的边缘 。。。
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cstring>
#include<string>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<utility>
#include<set>
#include<bitset>
#include<queue>
#include<stack>
#include<deque>
#include<map>
#include<vector>
#include<ctime>
#define INF 2147483646
#define ll long long
#define db double
using namespace std;
char buf[1<<15],*fs,*ft;
inline char getc()
{
return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void put(int x)
{
x<0?putchar('-'),x=-x:0;
int num=0;char ch[50];
while(x)ch[++num]=x%10+'0',x/=10;
num==0?putchar('0'):0;
while(num)putchar(ch[num--]);
putchar('\n');return;
}
//整个算法的复杂度 为 (nT^2+nm/T)
//将 m约为n 那么就是 nT^2+n^2/T 根据基本不等式 a+b>=2sqrt(ab)
//可得 nT^2==n^2/T时整个算法的复杂度最小 T=n的立方根
//T最大也不过<35
//总复杂度 n^5/3+n^4/3=67860440+1842015=1e7
const int MAXN=50002;
int n,m,T,num,len,p;
int a[MAXN],tmp[MAXN],pos[MAXN];
int l[MAXN],r[MAXN],vis[MAXN];
int b[50][50][MAXN];//b[i][j][k]表示i~j这个块中k出现的次数
int c[50][50];//表示i到j中的众数
inline void swap(int &x,int &y){int t=x;x=y;y=t;}
inline int min(int x,int y){return x>y?y:x;}
void discrete()
{
sort(tmp+1,tmp+1+n);
for(int i=1;i<=n;++i)if(i==1||tmp[i]!=tmp[i-1])tmp[++num]=tmp[i];
for(int i=1;i<=n;++i)a[i]=lower_bound(tmp+1,tmp+1+num,a[i])-tmp;
}
int ask(int L,int R)
{
int maxx=0,cnt=INF;
int p=pos[L],q=pos[R];
if(p==q||p+1==q)
{
for(int i=L;i<=R;++i)
{
++vis[a[i]];
if(vis[a[i]]==maxx)cnt=min(cnt,a[i]);
if(vis[a[i]]>maxx)cnt=a[i],maxx=vis[a[i]];
}
for(int i=L;i<=R;++i)--vis[a[i]];
}
else
{
cnt=c[p+1][q-1];
maxx=b[p+1][q-1][cnt];
for(int i=L;i<=r[p];++i)
{
++b[p+1][q-1][a[i]];
if(b[p+1][q-1][a[i]]==maxx)cnt=min(cnt,a[i]);
if(b[p+1][q-1][a[i]]>maxx)cnt=a[i],maxx=b[p+1][q-1][a[i]];
}
for(int i=l[q];i<=R;++i)
{
++b[p+1][q-1][a[i]];
if(b[p+1][q-1][a[i]]==maxx)cnt=min(cnt,a[i]);
if(b[p+1][q-1][a[i]]>maxx)cnt=a[i],maxx=b[p+1][q-1][a[i]];
}
for(int i=L;i<=r[p];++i)--b[p+1][q-1][a[i]];
for(int i=l[q];i<=R;++i)--b[p+1][q-1][a[i]];
}
return cnt;
}
int main()
{
//freopen("1.in","r",stdin);
n=read();m=read();
for(int i=1;i<=n;++i)tmp[i]=a[i]=read();
T=(int)pow(n*1.0,1.0/3*1.0);//分成T块
len=(int)(n*1.0/T*1.0);//每块长度为n/T
//cout<<T<<endl;
discrete();
//for(int i=1;i<=n;i++)cout<<a[i]<<endl;
for(int i=1;i<=T;++i)
{
l[i]=(i-1)*len+1;
r[i]=i*len;
}
if(r[T]<n)++T,l[T]=r[T-1]+1,r[T]=n;
for(int i=1;i<=T;++i)
{
for(int j=l[i];j<=r[i];j++)pos[j]=i;
for(int j=i;j<=T;++j)
{
int maxx=0,s=INF;
for(int k=l[i];k<=r[j];++k)
{
++b[i][j][a[k]];
if(b[i][j][a[k]]==maxx)s=min(s,a[k]);
if(b[i][j][a[k]]>maxx)s=a[k],maxx=b[i][j][a[k]];
}
c[i][j]=s;
}
}
/*for(int i=1;i<=T;++i)
for(int j=i;j<=T;++j)cout<<c[i][j]<<endl;*/
for(int i=1;i<=m;i++)
{
int x,y;
x=read();y=read();
x=(x+p-1)%n+1;
y=(y+p-1)%n+1;
if(x>y)swap(x,y);
int answer=ask(x,y);
put(tmp[answer]);
p=tmp[answer];
}
return 0;
}
View Code
数组开大一点总是好的。
第二种做法呢是一种比较巧妙的想法了，对于每个数字将其出现的下标存起来 。
对于每个询问 我们之间询问两边的数字的不超过当前最近最小的出现位置和最大的出现的位置。
此时比较即可。
第一次wa 真的比较绝望觉得一点错没问题 二分觉得不太妥。但是却是一个自主主张的标记被自己忽略了导致wa的很惨。
第二次wa 二分的中间有一个地方少打了东西导致wa 真的不亏 下次一定要注意不要这么手残。
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cstring>
#include<string>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<utility>
#include<set>
#include<bitset>
#include<queue>
#include<stack>
#include<deque>
#include<map>
#include<vector>
#include<ctime>
#define INF 2147483646
#define ll int
#define db double
using namespace std;
char buf[1<<15],*fs,*ft;
inline char getc()
{
return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void put(int x)
{
x<0?putchar('-'),x=-x:0;
int num=0;char ch[50];
while(x)ch[++num]=x%10+'0',x/=10;
num==0?putchar('0'):0;
while(num)putchar(ch[num--]);
putchar('\n');return;
}
//蒲公英 考虑二分来写
//复杂度 (nT+mn/T*log(n)) 由基本不等式可得 a+b>=2sqrt(ab)
//nT>=mn/T*log(n) T=sqrt(mlog(n))是取得最优 -> sqrt(nlogn)
const int MAXN=50002;
vector<int>q[MAXN];
int n,m,p,T,len,num,length;
int a[MAXN],pos[MAXN],tmp[MAXN];
int vis[MAXN];
int l[MAXN],r[MAXN];
int g[1000][1000];
inline int min(int x,int y){return x>y?y:x;}
inline void swap(int &x,int &y){int t=x;x=y;y=t;}
void discrete()
{
sort(tmp+1,tmp+1+n);
for(int i=1;i<=n;++i)if(i==1||tmp[i]!=tmp[i-1])tmp[++num]=tmp[i];
for(int i=1;i<=n;++i)a[i]=lower_bound(tmp+1,tmp+1+num,a[i])-tmp;
}
void carculate(int x)
{
memset(vis,0,sizeof(vis));
int maxx=0,s;
for(int i=x;i<=T;++i)
{
for(int j=l[i];j<=r[i];++j)
{
if(x==1)q[a[j]].push_back(j);
++vis[a[j]];
if(vis[a[j]]==maxx)s=min(s,a[j]);
if(vis[a[j]]>maxx)s=a[j],maxx=vis[a[j]];
}
g[x][i]=s;
}
}
int query1(int x,int k)
{
int l=0,r=q[x].size()-1;
while(l+1<r)
{
int mid=(l+r)>>1;
if(q[x][mid]==k)return mid;
if(q[x][mid]>k)r=mid;//求>k
else l=mid;
}
if(q[x][l]>=k)return l;
return r;
}
int query2(int x,int k)
{
int l=0,r=q[x].size()-1;
while(l+1<r)
{
int mid=(l+r)>>1;
if(q[x][mid]==k)return mid;
if(q[x][mid]>k)r=mid;//求<=k
else l=mid;
}
if(q[x][r]<=k)return r;
return l;
}
int ask(int L,int R)
{
int p=pos[L],q=pos[R];//注意此处变量重名局部变量屏蔽全局变量
int maxx=0,s;
if(p==q||p+1==q)
{
for(int i=L;i<=R;++i)
{
if(vis[a[i]]==1)continue;
vis[a[i]]=1;
int xx=query1(a[i],L);//寻找>=L的下标
int yy=query2(a[i],R);//寻找<=R的下标
if(yy-xx+1==maxx)s=min(s,a[i]);
if(yy-xx+1>maxx)s=a[i],maxx=yy-xx+1;
}
for(int i=L;i<=R;++i)vis[a[i]]=0;
}
else
{
int xx,yy;
xx=query1(g[p+1][q-1],L);
yy=query2(g[p+1][q-1],R);
maxx=yy-xx+1;s=g[p+1][q-1];
vis[s]=1;
for(int i=L;i<=r[p];++i)
{
if(vis[a[i]]==1)continue;
vis[a[i]]=1;
xx=query1(a[i],L);//寻找>=L的下标
yy=query2(a[i],R);//寻找<=R的下标
if(yy-xx+1==maxx)s=min(s,a[i]);
if(yy-xx+1>maxx)s=a[i],maxx=yy-xx+1;
}
for(int i=l[q];i<=R;++i)
{
if(vis[a[i]]==1)continue;
vis[a[i]]=1;
int xx=query1(a[i],L);//寻找>=L的下标
int yy=query2(a[i],R);//寻找<=R的下标
if(yy-xx+1==maxx)s=min(s,a[i]);
if(yy-xx+1>maxx)s=a[i],maxx=yy-xx+1;
}
vis[g[p+1][q-1]]=0;//注意 NC的错误也被我撞上了 我真是个NC
for(int i=L;i<=r[p];++i)vis[a[i]]=0;
for(int i=l[q];i<=R;++i)vis[a[i]]=0;
}
return s;
}
int main()
{
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
n=read();m=read();
for(int i=1;i<=n;++i)tmp[i]=a[i]=read();
discrete();
T=(int)sqrt(m*1.0*log(n*1.0));
len=n/T;
for(int i=1;i<=T;++i)
{
if(i*len>n)break;
l[i]=(i-1)*len+1;
r[i]=i*len;
}
if(r[T]<n)T++,l[T]=r[T-1]+1,r[T]=n;
for(int i=1;i<=T;++i)
{
carculate(i);
for(int j=l[i];j<=r[i];++j)pos[j]=i;
}
memset(vis,0,sizeof(vis));
for(int i=1;i<=m;++i)
{
int x,y;
x=read();y=read();
x=(x+p-1)%n+1;
y=(y+p-1)%n+1;
if(x>y)swap(x,y);
int k=ask(x,y);
put(tmp[k]);
p=tmp[k];
}
return 0;
}
View Code
写代码的时候 切记：
真正弄懂了思路再写不然只是白白的浪费时间罢了
写代码的时候一定要专注 把自己写的每一个函数的功能都弄懂。
静态眼查 不要急着去带样例 。