CF 840 D
clf大佬告诉我,直接主席树是\(n\times \log(n)\)哒
这是为什么呢.
首先最多有5个叶子节点是出现次数大于等于\(n\over 5\)哒,然后上述叶子也可能不是叶子啊.
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
const int MAXN=300000;
const int INF=0x3f3f3f3f;
struct Node{int w,lc,rc;};
int n,q;
int root[MAXN+10];
Node t[20*MAXN+10];int tot;
void insert(int& o,int l,int r,int q)
{
t[++tot]=t[o];o=tot;
if(l==r){++t[o].w;return;}
int mid=(l+r)>>1;
if(q<=mid)insert(t[o].lc,l,mid,q);
else insert(t[o].rc,mid+1,r,q);
t[o].w=t[t[o].lc].w+t[t[o].rc].w;
}
int query(int o1,int o2,int l,int r,int q)
{
if(l==r)return l;
int mid=(l+r)>>1,res=INF;
if(t[t[o2].lc].w-t[t[o1].lc].w>=q)res=min(res,query(t[o1].lc,t[o2].lc,l,mid,q));
if(t[t[o2].rc].w-t[t[o1].rc].w>=q)res=min(res,query(t[o1].rc,t[o2].rc,mid+1,r,q));
return res;
}
int main()
{
scanf("%d%d",&n,&q);
for(int i=1,a;i<=n;++i)
{
scanf("%d",&a);
root[i]=root[i-1];
insert(root[i],1,n,a);
}
while(q--)
{
int l,r,k,res;
scanf("%d%d%d",&l,&r,&k);
res=query(root[l-1],root[r],1,n,(r-l+1)/k+1);
printf("%d\n",res>=INF?-1:res);
}
return 0;
}