https://www.luogu.com.cn/record/132628141
by jqsh @ 2023-10-31 18:41:12
离谱，把注释删掉 40 分
by CEFqwq @ 2023-10-31 18:53:14
等我把 DEV-C++ 装好，我看看
by CEFqwq @ 2023-10-31 18:55:57
https://www.luogu.com.cn/record/132632421
加上
```cpp
#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 rabbitohh @ 2023-10-31 18:59:23
调下块长，用pbds。
by _lgh_ @ 2023-10-31 18:59:46
你这是怎么测出 600ms 的。。。
我本地测试 #6 开 O2 跑了 4.08s，不开能跑 18.04s
by CEFqwq @ 2023-10-31 19:00:18
@[_lgh_](/user/598275) pbds 是什么黑科技，能不能科普一下/yiw
by CEFqwq @ 2023-10-31 19:03:20
@[jqsh](/user/320652)
```cpp
#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:06:12
@[rabbitohh](/user/327512) 我加了一些优化还是要卡一卡，而且不开 C++14(GCC 9) 貌似根本过不了
by CEFqwq @ 2023-10-31 19:20:58
@[jqsh](/user/320652)
```cpp
#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;
}
```
这个代码多交几遍就能卡过去了
by CEFqwq @ 2023-10-31 19:21:58