jqsh @ 2023-10-31 18:40:49
本地运行用 clock 看只有 600多ms 但交上去就会T，求巨佬救救
#include<bits/stdc++.h>
//#define int long long
//#define lld d
using namespace std;
int n,m,a[1000001];
int cnt,len,bel[1000001];
unordered_map<int,int>H,ans;
struct Node{
int l,r;
unordered_map<int,int>s;
vector<int>num;
}fk[10001];
int pre[351][40001],s[351][351];
int lastans;
int read(){
int k=0;
char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)){
k=(k<<1)+(k<<3)+(ch^48);
ch=getchar();
}
return k;
}
signed main(){
// freopen("4168.in","r",stdin);
// freopen("4168.out","w",stdout);
// scanf("%d %d",&n,&m);
n=read();m=read();
len=sqrt(n);
for(int i=1;i<=n;i++){
//scanf("%d",&a[i]);
a[i]=read();
bel[i]=(i/len)+1;
if(!H[a[i]]) H[a[i]]=++cnt;
ans[H[a[i]]]=a[i];
if(!fk[bel[i]].s[a[i]])
fk[bel[i]].num.push_back(a[i]);
fk[bel[i]].s[a[i]]++;
}
fk[bel[n]].r=n;
for(int i=1;i<=bel[n];i++){
for(int j=1;j<=cnt;j++)
pre[i][j]=pre[i-1][j]+fk[i].s[ans[j]];
}
for(int i=1;i<=bel[n];i++){
int now=0;
unordered_map<int,int>nows;
for(int j=i;j<=bel[n];j++){
for(auto k:fk[j].num){
nows[k]+=fk[j].s[k];
now=nows[k]==nows[now]?(k>now?now:k):(nows[k]>nows[now]?k:now);
}
s[i][j]=now;
}
}
while(m--){
int l=read(),r=read();
l=(l+lastans-1)%n+1;
r=(r+lastans-1)%n+1;
if(l>r) swap(l,r);
int now=0;
// cout<<"A"<<endl;
unordered_map<int,int>nows;
if(bel[r]-bel[l]<=1){
// cout<<"C"<<endl;
for(int i=l;i<=r;i++){
nows[a[i]]++;
now=nows[a[i]]==nows[now]?(a[i]>now?now:a[i]):(nows[a[i]]>nows[now]?a[i]:now);
}
printf("%d\n",now);
lastans=now;
continue;
}
else{
// cout<<"B"<<endl;
for(int i=l;bel[i]==bel[l];i++){
if(!nows[a[i]])
nows[a[i]]+=pre[bel[r]-1][H[a[i]]]-pre[bel[l]][H[a[i]]];
nows[a[i]]++;
now=nows[a[i]]==nows[now]?(a[i]>now?now:a[i]):(nows[a[i]]>nows[now]?a[i]:now);
}
for(int i=r;bel[i]==bel[r];i--){
if(!nows[a[i]])
nows[a[i]]+=pre[bel[r]-1][H[a[i]]]-pre[bel[l]][H[a[i]]];
nows[a[i]]++;
now=nows[a[i]]==nows[now]?(a[i]>now?now:a[i]):(nows[a[i]]>nows[now]?a[i]:now);
}
int nowk=s[bel[l]+1][bel[r]-1];
if(!nows[nowk]){
nows[nowk]+=(pre[bel[r]-1][H[nowk]]-pre[bel[l]][H[nowk]]);
now=nows[nowk]==nows[now]?(nowk>now?now:nowk):(nows[nowk]>nows[now]?nowk:now);
}
printf("%d\n",now);
lastans=now;
}
}
// cout<<clock()<<endl;
return 0;
}by jqsh @ 2023-10-31 18:41:12
https://www.luogu.com.cn/record/132628141
by CEFqwq @ 2023-10-31 18:53:14
离谱，把注释删掉 40 分
by CEFqwq @ 2023-10-31 18:55:57
等我把 DEV-C++ 装好，我看看
by rabbitohh @ 2023-10-31 18:59:23
https://www.luogu.com.cn/record/132632421 加上
#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使用pbds中的哈希表就可以过了
by _lgh_ @ 2023-10-31 18:59:46
调下块长，用pbds。
by CEFqwq @ 2023-10-31 19:00:18
你这是怎么测出 600ms 的。。。
我本地测试 #6 开 O2 跑了 4.08s，不开能跑 18.04s
by CEFqwq @ 2023-10-31 19:03:20
@lgh pbds 是什么黑科技，能不能科普一下/yiw
by CEFqwq @ 2023-10-31 19:06:12
@jqsh
#include<bits/stdc++.h>
#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
int n,m,a[1000001];
int cnt,len,bel[1000001];
unordered_map<int,int>H,ans;
struct Node{
int l,r;
unordered_map<int,int>s;
vector<int>num;
}fk[10001];
int pre[351][40001],s[351][351];
int lastans;
#define BF_SIZE 100000
bool IOerr=0;
inline char nc(){
static char buf[BF_SIZE],*p1=buf+BF_SIZE,*pend=buf+BF_SIZE;
if(p1==pend){
p1=buf;
pend=buf+fread(buf,1,BF_SIZE,stdin);
if(pend==p1){IOerr=1;return -1;}
}
return *p1++;
}
inline bool bla(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
inline void read(int &x){
register char ch;
while(bla(ch=nc()));
if(IOerr){return;}
for(x=ch-'0';(ch=nc())>='0'&&ch<='9';x=x*10+ch-'0');
}
#undef BF_SIZE
signed main(){
read(n);read(m);
len=sqrt(n);
for(int i=1;i<=n;i++){
read(a[i]);
bel[i]=(i/len)+1;
if(!H[a[i]]) H[a[i]]=++cnt;
ans[H[a[i]]]=a[i];
if(!fk[bel[i]].s[a[i]])
fk[bel[i]].num.push_back(a[i]);
fk[bel[i]].s[a[i]]++;
}
fk[bel[n]].r=n;
for(int i=1;i<=bel[n];i++){
for(int j=1;j<=cnt;j++)
pre[i][j]=pre[i-1][j]+fk[i].s[ans[j]];
}
for(int i=1;i<=bel[n];i++){
int now=0;
unordered_map<int,int>nows;
for(int j=i;j<=bel[n];j++){
for(auto k:fk[j].num){
nows[k]+=fk[j].s[k];
now=nows[k]==nows[now]?(k>now?now:k):(nows[k]>nows[now]?k:now);
}
s[i][j]=now;
}
}
while(m--){
int l,r;
read(l);read(r);
l=(l+lastans-1)%n+1;
r=(r+lastans-1)%n+1;
if(l>r) swap(l,r);
int now=0;
unordered_map<int,int>nows;
if(bel[r]-bel[l]<=1){
for(int i=l;i<=r;i++){
nows[a[i]]++;
now=nows[a[i]]==nows[now]?(a[i]>now?now:a[i]):(nows[a[i]]>nows[now]?a[i]:now);
}
printf("%d\n",now);
lastans=now;
continue;
}
else{
for(int i=l;bel[i]==bel[l];i++){
if(!nows[a[i]])
nows[a[i]]+=pre[bel[r]-1][H[a[i]]]-pre[bel[l]][H[a[i]]];
nows[a[i]]++;
now=nows[a[i]]==nows[now]?(a[i]>now?now:a[i]):(nows[a[i]]>nows[now]?a[i]:now);
}
for(int i=r;bel[i]==bel[r];i--){
if(!nows[a[i]])
nows[a[i]]+=pre[bel[r]-1][H[a[i]]]-pre[bel[l]][H[a[i]]];
nows[a[i]]++;
now=nows[a[i]]==nows[now]?(a[i]>now?now:a[i]):(nows[a[i]]>nows[now]?a[i]:now);
}
int nowk=s[bel[l]+1][bel[r]-1];
if(!nows[nowk]){
nows[nowk]+=(pre[bel[r]-1][H[nowk]]-pre[bel[l]][H[nowk]]);
now=nows[nowk]==nows[now]?(nowk>now?now:nowk):(nows[nowk]>nows[now]?nowk:now);
}
printf("%d\n",now);
lastans=now;
}
}
return 0;
}改了下超快读，快一点了，多卡几次不知道能不能过（）
by CEFqwq @ 2023-10-31 19:20:58
@rabbitohh 我加了一些优化还是要卡一卡，而且不开 C++14(GCC 9) 貌似根本过不了
by CEFqwq @ 2023-10-31 19:21:58
@jqsh
#include<bits/stdc++.h>
#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
int n,m,a[50001];
int cnt,len,bel[50001];
unordered_map<int,int>H,ans;
struct Node{
int l,r;
unordered_map<int,int>s;
vector<int>num;
}fk[10001];
int pre[221][40001],s[221][221];
int lastans;
#define BF_SIZE 1000
bool IOerr=0;
inline char nc(){
static char buf[BF_SIZE],*p1=buf+BF_SIZE,*pend=buf+BF_SIZE;
if(p1==pend){
p1=buf;
pend=buf+fread(buf,1,BF_SIZE,stdin);
if(pend==p1){IOerr=1;return -1;}
}
return *p1++;
}
inline bool bla(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
inline void read(int &x){
register char ch;
while(bla(ch=nc()));
if(IOerr){return;}
for(x=ch-'0';(ch=nc())>='0'&&ch<='9';x=x*10+ch-'0');
}
#undef BF_SIZE
inline void write(int x){
register char F[200];
register int tmp=x>0?x:-x;
if(x<0)putchar('-');
register int cnt=0;
while(tmp>0)
{
F[cnt++]=tmp%10+'0';
tmp/=10;
}
while(cnt>0)putchar(F[--cnt]);
}
signed main(){
read(n);read(m);
len=sqrt(n);
for(register int i=1;i<=n;i++){
read(a[i]);
bel[i]=(i/len)+1;
if(!H[a[i]]) H[a[i]]=++cnt;
ans[H[a[i]]]=a[i];
if(!fk[bel[i]].s[a[i]])
fk[bel[i]].num.push_back(a[i]);
fk[bel[i]].s[a[i]]++;
}
fk[bel[n]].r=n;
for(register int i=1;i<=bel[n];i++){
for(int j=1;j<=cnt;j++)
pre[i][j]=pre[i-1][j]+fk[i].s[ans[j]];
}
for(register int i=1;i<=bel[n];i++){
int now=0;
unordered_map<int,int>nows;
for(int j=i;j<=bel[n];j++){
for(auto k:fk[j].num){
nows[k]+=fk[j].s[k];
now=nows[k]==nows[now]?(k>now?now:k):(nows[k]>nows[now]?k:now);
}
s[i][j]=now;
}
}
while(m--){
int l,r;
read(l);read(r);
l=(l+lastans-1)%n+1;
r=(r+lastans-1)%n+1;
if(l>r) swap(l,r);
int now=0;
unordered_map<int,int>nows;
if(bel[r]-bel[l]<=1){
for(register int i=l;i<=r;i++){
nows[a[i]]++;
now=nows[a[i]]==nows[now]?(a[i]>now?now:a[i]):(nows[a[i]]>nows[now]?a[i]:now);
}
write(now);
putchar('\n');
lastans=now;
continue;
}
else{
for(register int i=l;bel[i]==bel[l];i++){
if(!nows[a[i]])
nows[a[i]]+=pre[bel[r]-1][H[a[i]]]-pre[bel[l]][H[a[i]]];
nows[a[i]]++;
now=nows[a[i]]==nows[now]?(a[i]>now?now:a[i]):(nows[a[i]]>nows[now]?a[i]:now);
}
for(register int i=r;bel[i]==bel[r];i--){
if(!nows[a[i]])
nows[a[i]]+=pre[bel[r]-1][H[a[i]]]-pre[bel[l]][H[a[i]]];
nows[a[i]]++;
now=nows[a[i]]==nows[now]?(a[i]>now?now:a[i]):(nows[a[i]]>nows[now]?a[i]:now);
}
int nowk=s[bel[l]+1][bel[r]-1];
if(!nows[nowk]){
nows[nowk]+=(pre[bel[r]-1][H[nowk]]-pre[bel[l]][H[nowk]]);
now=nows[nowk]==nows[now]?(nowk>now?now:nowk):(nows[nowk]>nows[now]?nowk:now);
}
write(now);
putchar('\n');
lastans=now;
}
}
return 0;
}这个代码多交几遍就能卡过去了