coding_goat @ 2024-02-11 03:10:14
rt，感觉时间复杂度正确，但是莫名TLE后面的所有数据，求调，谢谢！
by coding_goat @ 2024-02-11 03:11:27
#include<bits/stdc++.h>
#define ll long long
using namespace std;
template <typename T>inline void read(T &xx){
xx=0;int f=1;
char c = getchar();
while(c<'0'||c>'9'){
if(c=='-') f = -1;
c = getchar();
}
while(c>='0'&&c<='9'){
xx = (xx<<1)+(xx<<3)+(c^48);
c = getchar();
}
xx*=f;
}
#define maxn 40040
#define maxb 220
#define debug puts("I AK IOI");
int n,m,a[maxn];
int p[maxb][maxb],s[maxb][maxn];
int x,len,top,L,R;
int bel[maxn],st[maxb],ed[maxb],sz[maxb];
map<int,int> disc,redisc;
int query(int l,int r){
if(bel[l]==bel[r]){
map<int,int>mp;
int cnta=0,cntpl;
for(int i=l;i<=r;i++){
mp[a[i]]++;
if(cnta<mp[a[i]]){
cnta=mp[a[i]];
cntpl=a[i];
}else if(cnta==mp[a[i]]&&cntpl>a[i]){
cntpl=a[i];
}
}
return cntpl;
}
map<int,int>mp;
for(int i=l;i<=ed[bel[l]];i++) mp[a[i]]++;
for(int i=st[bel[r]];i<=r;i++) mp[a[i]]++;
int cntpl=p[bel[l]+1][bel[r]-1];
int cnta =s[bel[r]-1][disc[cntpl]]-s[bel[l]][disc[cntpl]];
for(int i=l;i<=ed[bel[l]];i++){
if(cnta<s[bel[r]-1][disc[a[i]]]-s[bel[l]][disc[a[i]]]+mp[a[i]]){
cntpl=a[i];
cnta=s[bel[r]-1][disc[a[i]]]-s[bel[l]][disc[a[i]]]+mp[a[i]];
}else if(cnta==s[bel[r]-1][disc[a[i]]]-s[bel[l]][disc[a[i]]]+mp[a[i]]&&cntpl>a[i]){
cntpl=a[i];
}
}
for(int i=st[bel[r]];i<=r;i++){
if(cnta<s[bel[r]-1][disc[a[i]]]-s[bel[l]][disc[a[i]]]+mp[a[i]]){
cntpl=a[i];
cnta=s[bel[r]-1][disc[a[i]]]-s[bel[l]][disc[a[i]]]+mp[a[i]];
}else if(cnta==s[bel[r]-1][disc[a[i]]]-s[bel[l]][disc[a[i]]]+mp[a[i]]&&cntpl>a[i]){
cntpl=a[i];
}
}
return cntpl;
}
int main(){
//debug
//freopen("tmp.in","r",stdin);
//debug
scanf("%d%d",&n,&m);
//cout<<n<<'\n';
//debug
for(int i=1;i<=n;i++){
//debug
scanf("%d",&a[i]);
//printf("%d ",a[i]);
if(!disc[a[i]]){
disc[a[i]]=++top;
redisc[top]=a[i];
}
}
//debug
len=sqrt(n);
for(int i=1;i<=len;i++){
st[i]=ed[i-1]+1;
ed[i]=ed[i-1]+n/len;
sz[i]=ed[i]-st[i]+1;
}
ed[len]=n;
sz[len]=ed[len]-st[len]+1;
for(int i=1;i<=len;i++)
for(int j=st[i];j<=ed[i];j++)
bel[j]=i;
//debug
for(int i=1;i<=len;i++){
int cnta=0,cntpl;
map<int,int>mp;
for(int k=i;k<=len;k++){
for(int j=st[k];j<=ed[k];j++){
mp[a[j]]++;
if(cnta<mp[a[j]]){
cnta=mp[a[j]];
cntpl=a[j];
}else if(cnta==mp[a[j]]&&cntpl>a[j]){
cntpl=a[j];
}
}
p[i][k]=cntpl;
}
}
//debug
for(int i=1;i<=len;i++){
for(int k=st[i];k<=ed[i];k++)
s[i][disc[a[k]]]++;
}
for(int i=1;i<=len;i++)
for(int j=1;j<=top;j++)
s[i][j]+=s[i-1][j];
for(int i=1;i<=m;i++){
read(L);read(R);
L=((L+x-1)%n)+1;
R=((R+x-1)%n)+1;
if(L>R) swap(L,R);
x=query(L,R);
printf("%d\n",x);
}
return 0;
}
by coding_goat @ 2024-02-11 03:16:48
靠把 map 改成 unordered_map 多卡过了俩
by coding_goat @ 2024-02-11 03:22:12
会不会是 map 太慢了，我改成数组试试
by coding_goat @ 2024-02-11 03:43:30
由于离散化些挂了，但是我还是拿了10pts，而且几乎每个测试点都是 250ms。
by coding_goat @ 2024-02-11 04:05:42
现在长这样：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
template <typename T>inline void read(T &xx){
xx=0;int f=1;
char c = getchar();
while(c<'0'||c>'9'){
if(c=='-') f = -1;
c = getchar();
}
while(c>='0'&&c<='9'){
xx = (xx<<1)+(xx<<3)+(c^48);
c = getchar();
}
xx*=f;
}
#define maxn 40040
#define maxb 220
#define debug puts("I AK IOI");
int n,m,a[maxn];
int p[maxb][maxb],s[maxb][maxn];
int x,len,top,L,R;
int bel[maxn],st[maxb],ed[maxb],sz[maxb];
int disc[maxn];
int mp[maxn];
map<int,int>apper;
int query(int l,int r){
if(bel[l]==bel[r]){
memset(mp,0,sizeof(mp));
int cnta=0,cntpl;
for(int i=l;i<=r;i++){
mp[disc[i]]++;
if(cnta<mp[disc[i]]){
cnta=mp[disc[i]];
cntpl=a[i];
}else if(cnta==mp[disc[i]]&&cntpl>a[i]){
cntpl=a[i];
}
}
return cntpl;
}
memset(mp,0,sizeof(mp));
for(int i=l;i<=ed[bel[l]];i++) mp[disc[i]]++;
for(int i=st[bel[r]];i<=r;i++) mp[disc[i]]++;
int cntpl=p[bel[l]+1][bel[r]-1];
int cnta =s[bel[r]-1][disc[apper[cntpl]]]-s[bel[l]][disc[apper[cntpl]]];
for(int i=l;i<=ed[bel[l]];i++){
if(cnta<s[bel[r]-1][disc[i]]-s[bel[l]][disc[i]]+mp[disc[i]]){
cntpl=a[i];
cnta=s[bel[r]-1][disc[i]]-s[bel[l]][disc[i]]+mp[disc[i]];
}else if(cnta==s[bel[r]-1][disc[i]]-s[bel[l]][disc[i]]+mp[disc[i]]&&cntpl>a[i]){
cntpl=a[i];
}
}
for(int i=st[bel[r]];i<=r;i++){
if(cnta<s[bel[r]-1][disc[i]]-s[bel[l]][disc[i]]+mp[disc[i]]){
cntpl=a[i];
cnta=s[bel[r]-1][disc[i]]-s[bel[l]][disc[i]]+mp[disc[i]];
}else if(cnta==s[bel[r]-1][disc[i]]-s[bel[l]][disc[i]]+mp[disc[i]]&&cntpl>a[i]){
cntpl=a[i];
}
}
return cntpl;
}
int main(){
//debug
//freopen("tmp.in","r",stdin);
//debug
scanf("%d%d",&n,&m);
//cout<<n<<'\n';
//debug
for(int i=1;i<=n;i++){
//debug
scanf("%d",&a[i]);
//printf("%d ",a[i]);
if(!apper[a[i]])
disc[i]=++top,apper[a[i]]=i;
else
disc[i]=disc[apper[a[i]]];
}
//for(int i=1;i<=n;i++) cout<<disc[i]<<' ';
//debug
len=sqrt(n);
for(int i=1;i<=len;i++){
st[i]=ed[i-1]+1;
ed[i]=st[i]+n/len-1;
sz[i]=ed[i]-st[i]+1;
}
ed[len]=n;
sz[len]=ed[len]-st[len]+1;
for(int i=1;i<=len;i++)
for(int j=st[i];j<=ed[i];j++)
bel[j]=i;
//debug
for(int i=1;i<=len;i++){
int cnta=0,cntpl;
memset(mp,0,sizeof(mp));
for(int k=i;k<=len;k++){
for(int j=st[k];j<=ed[k];j++){
mp[disc[j]]++;
if(cnta<mp[disc[j]]){
cnta=mp[disc[j]];
cntpl=a[j];
}else if(cnta==mp[disc[j]]&&cntpl>a[j]){
cntpl=mp[disc[j]];
}
}
p[i][k]=cntpl;
}
}
//debug
for(int i=1;i<=len;i++){
for(int k=st[i];k<=ed[i];k++)
s[i][disc[k]]++;
}
for(int i=1;i<=len;i++)
for(int j=1;j<=top;j++)
s[i][j]+=s[i-1][j];
for(int i=1;i<=m;i++){
read(L);read(R);
L=((L+x-1)%n)+1;
R=((R+x-1)%n)+1;
if(L>R) swap(L,R);
x=query(L,R);
printf("%d\n",x);
}
return 0;
}
by coding_goat @ 2024-02-11 04:22:31
有人吗，救救求求嘤嘤
by coding_goat @ 2024-02-11 04:28:06
翻了以往的讨论区，在 unordered_map 那份代码里加了下面的就A了
#include<ext/pb_ds/hash_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define unordered_map gp_hash_table顺便撅警钟：多打数组少用map（雾
by coding_goat @ 2024-02-11 04:28:25
此帖结
by WZwangchongming @ 2024-02-12 10:48:23
@hzhHZH233 哈哈哈平板电视的哈希换umap，理论上是一个效果