An_Account @ 2018-08-15 21:19:37
第一次写分块,但是一直
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
#define N 40010
#define B 810
int len,f[B][B],at[N],cnt[N],n,m,v[N],val[N];
vector<int> id[N];
void pre(int x) {
memset(cnt,0,sizeof(cnt));
int mx=0,ans=0;
for (int i=(x-1)*len+1;i<=n;i++) {
cnt[v[i]]++;
if (cnt[v[i]]>mx||(cnt[v[i]]==mx&&val[v[i]]<val[ans]))
ans=v[i],mx=cnt[v[i]];
f[x][at[i]]=ans;
}
}
int query(int l,int r,int x) {
vector<int>::iterator start=lower_bound(id[x].begin(),id[x].end(),l);
vector<int>::iterator end=upper_bound(id[x].begin(),id[x].end(),r);
return end-start;
}
int query(int start,int end) {
int ans=f[at[start]+1][at[end]-1],mx=query(start,end,ans);
for (int i=start;i<=min(at[start]*len,end);i++) {
int t=query(start,end,v[i]);
if (t>mx||(t==mx&&val[v[i]]<val[ans])) ans=v[i],mx=t;
}
if (at[start]!=at[end])
for (int i=(at[end]-1)*len+1;i<=end;i++) {
int t=query(start,end,v[i]);
if (t>mx||(t==mx&&val[v[i]]<val[ans])) ans=v[i],mx=t;
}
return val[ans];
}
map<int,int> H;int hcnt;
int main() {
scanf("%d%d",&n,&m),len=sqrt(n*log2(n));
for (int i=1;i<=n;i++) {
scanf("%d",&v[i]),at[i]=(i-1)/len+1;
if (!H[v[i]]) H[v[i]]=++hcnt,val[hcnt]=v[i];
v[i]=H[v[i]],id[v[i]].push_back(i);
}
for (int i=1;i<=at[n];i++) pre(i);
int lastans=0;
for (int i=1;i<=m;i++) {
int start,end;scanf("%d%d",&start,&end);
start=(start+lastans-1)%n+1,end=(end+lastans-1)%n+1;
if (start>end) swap(start,end);
printf("%d\n",lastans=query(start,end));
}
return 0;
}
by Randyhoads @ 2018-08-15 21:54:07
其实本质上就是个暴力
by Randyhoads @ 2018-08-15 21:54:36
网上有人说主席树能过,但是我不知道怎么写,就写了一个类似暴力的东西
by An_Account @ 2018-08-15 21:55:39
@WLZS 这样一次查询最坏是
by Randyhoads @ 2018-08-15 21:56:18
@An_Account 然后ZJK实名了
by An_Account @ 2018-08-15 21:57:41
@WLZS 他没实名啊(他刚刚还想给您发私信然后发现发不起)
by An_Account @ 2018-08-15 22:04:24
其实ZJK也在写这道题结果RE+WA了
by Randyhoads @ 2018-08-15 22:16:22
@An_Account orz ZJK
by An_Account @ 2018-08-16 07:45:14
我终于过了这道题
把原来的
谢谢大家的帮助