Rye_Catcher @ 2018-06-23 22:38:26
rt,debug了好久,开O2上去3个点Too Many Or Too Few Lines,一片RE,求助
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <map>
#include <vector>
#include <queue>
#include <unordered_map>
#define ll long long
#define ri int
using namespace std;
const int inf=0x7fffffff;
const int maxn=40005;
const int maxx=505;
template <class T>inline void read(T &x){
x=0;int ne=0;char c;
while(!isdigit(c=getchar()))ne=c=='-';
x=c-48;
while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
x=ne?-x:x;
return ;
}
int n,m,size;
int pos[maxx],L[maxx],R[maxx],f[maxx][maxx],cnt[maxx],fun[maxn];
unordered_map <int,int>rec;//离散化
vector <int>loc[maxn];//记录各数出现位置
int a[maxn],tot=0;
inline void pre(int now){
int mx=-1,ans=0;
memset(cnt,0,sizeof(cnt));
for(ri i=L[now];i<=n;i++){
cnt[a[i]]++;
if(cnt[a[i]]>mx||(cnt[a[i]]==mx&&fun[a[i]]<fun[ans])){/*有若干种蒲公英出现次数相同,则输出种类编号最小的那个。*/
mx=cnt[a[i]];
ans=a[i];
}
f[now][pos[i]]=ans;
//cout<<pos[i]<<' '<<ans<<endl;
}
return ;
}
inline int get(int l,int r,int x){
return upper_bound(loc[x].begin(),loc[x].end(),r)-lower_bound(loc[x].begin(),loc[x].end(),l);
}
inline int query(int l,int r){
int ans=f[pos[l]+1][pos[r]-1],tmp;
int mx=get(l,r,ans),p=pos[l],q=pos[r];
if(p!=q){
for(ri i=l;i<=R[p];i++){
tmp=get(l,r,a[i]);
if(tmp>mx||(tmp==mx&&fun[a[i]]<fun[ans])){
mx=tmp,ans=a[i];
}
}
for(ri i=L[q];i<=r;i++){
tmp=get(l,r,a[i]);
if(tmp>mx||(tmp==mx&&fun[a[i]]<fun[ans])){
mx=tmp,ans=a[i];
}
}
}
else{
for(ri i=l;i<=r;i++){
tmp=get(l,r,a[i]);
if(tmp>mx||(tmp==mx&&fun[a[i]]<fun[ans])){
mx=tmp,ans=a[i];
}
}
}
return ans;
}
int main(){
read(n),read(m);
size=sqrt(n);
for(ri i=1;i<=n;i++){
read(a[i]);
if(rec[a[i]]==0){
rec[a[i]]=++tot;
fun[tot]=a[i];
}
a[i]=rec[a[i]];
loc[a[i]].push_back(i);
}
for(ri i=1;i<=size;i++){
L[i]=(i-1)*size+1;
R[i]=i*size;
}
if(R[size]<n){size++,L[size]=R[size-1]+1,R[size]=n;}
for(ri i=1;i<=size;i++){
for(ri j=L[i];j<=R[i];j++){
pos[j]=i;
}
}
for(ri i=1;i<=size;i++)pre(i);
int x=0,l,r,c;
while(m--){
read(l),read(r);
l=(l+x-1)%n+1,r=(r+x-1)%n+1;
if(l>r)swap(l,r);
x=fun[query(l,r)];
printf("%d\n",x);
}
return 0;
}
by 小粉兔 @ 2018-06-24 00:02:13
好强啊……我分块都没做这题
by Mudrobøt @ 2018-08-07 17:50:33
@Rye_Catcher 吸纯净臭氧!
by Delva @ 2018-08-07 17:50:33
@Rye_Catcher 吸纯净臭氧啊