吸氧暴力轻松水过。

Sky_valley @ 2018-09-27 22:05:26

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define rg register
using namespace std;
const int MAXN=5e5+5;

int a[MAXN],b[MAXN],n,m,las,t[40001],Max,w;

inline int read()
{
    rg int x=0,w=1; rg char c=getchar();
    while((c<'0'||c>'9')&&c!='-') c=getchar();
    if(c=='-') w=-1,c=getchar();
    while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-'0',c=getchar();
    return x*w;
}

int main()
{
    n=read(),m=read();
    for(rg int i=1;i<=n;++i) a[i]=b[i]=read();
    sort(b+1,b+n+1);
    int len=unique(b+1,b+n+1)-b-1;
    for(rg int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+len+1,a[i])-b;
    for(rg int i=1;i<=m;++i){
    memset(t,0,sizeof(t));
    rg int l=read(),r=read();
    l=(l+las-1)%n+1,r=(r+las-1)%n+1;
    if(l>r) swap(l,r);
    for(rg int j=l;j<=r;++j) t[a[j]]++;
    Max=0;
    for(rg int j=1;j<=len;++j) if(t[j]>Max) Max=t[j],w=j;
    printf("%d\n",b[w]);
    las=b[w];
    }
    return 0;
}

by ___I_AK_IOI @ 2018-09-27 22:08:04

NOIP不让用O2还是老老实实的打正解吧

by Sky_valley @ 2018-09-27 22:08:24

当时看数据范围也没那么大，就试了试裸的暴力，一口清新的氧气就过了。

by Sky_valley @ 2018-09-27 22:08:54

嗯，去学了分块

by 空の軌跡 @ 2018-09-27 22:16:02

TQL

by wuzhaoxin @ 2018-09-27 22:19:43

原题数据 m<=500000 到了洛谷瞬间少了一个0

by Aehnuwx @ 2018-10-10 13:02:16

@白哥小葱 然鹅省选可以吸氧

by Apricot @ 2018-10-12 16:32:23

现在您的算法会T了，（评测机变慢了

by 冒泡ioa @ 2018-10-13 09:18:45

@Split 加上这个还是能过

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")