昨天对着代码看了一晚上
然后今天终于在loj上过了
数列分块入门9题撒花★,°:.☆(￣▽￣)/$:.°★ 。
然后相当玄学
块的大小调成(sqrt{n})会TLE,改成150就过了
啧
然后就是用map离散化之后的值不能直接比较大小
锅锅锅
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <cmath>
using namespace std;
int belong[100100],f[1000][1000],sz,blocknum,n,val[100100],id=0,cnt[100100],a[100100];
vector<int> Vec[100100];
map<int,int> To;
void calbe(int n){
for(int i=1;i<=n;i++)
belong[i]=(i-1)/sz+1;
}
void pre(int x){
memset(cnt,0,sizeof(cnt));
int ans=0,ansto=0;
for(int i=(x-1)*sz+1;i<=n;i++){
cnt[a[i]]++;
if(cnt[a[i]]>ansto||(val[a[i]]<=val[ans]&&cnt[a[i]]>=ansto))
ans=a[i],ansto=cnt[a[i]];
f[x][belong[i]]=ans;
}
}
int query(int l,int r,int c){
return upper_bound(Vec[c].begin(),Vec[c].end(),r)-lower_bound(Vec[c].begin(),Vec[c].end(),l);
}
int query(int l,int r){
int lsx=belong[l];
int rex=belong[r];
int ans=0,ansto=0,mid;
for(int i=l;i<=min(lsx*sz,r);i++)
if((mid=query(l,r,a[i]))>ansto||(val[a[i]]<=val[ans]&&mid>=ansto))
ans=a[i],ansto=mid;
if(lsx!=rex){
for(int i=(rex-1)*sz+1;i<=r;i++)
if((mid=query(l,r,a[i]))>ansto||(val[a[i]]<=val[ans]&&mid>=ansto))
ans=a[i],ansto=mid;
if(lsx+1<=rex-1)
if((mid=query(l,r,f[lsx+1][rex-1]))>ansto||(val[f[lsx+1][rex-1]]<=val[ans]&&mid>=ansto))
ans=f[lsx+1][rex-1],ansto=mid;
}
return ans;
}
int main(){
// freopen("1.in","r",stdin);
// freopen("test.out","w",stdout);
scanf("%d",&n);
sz=150;
blocknum=n/sz;
if(n%sz)
blocknum++;
calbe(n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(!To[a[i]]){
To[a[i]]=++id;
val[id]=a[i];
}
a[i]=To[a[i]];
Vec[a[i]].push_back(i);
}
for(int i=1;i<=blocknum;i++)
pre(i);
for(int i=1;i<=n;i++){
int l,r;
scanf("%d %d",&l,&r);
printf("%d
",val[query(l,r)]);
}
return 0;
}