我 1272ms / 117.29MB
by Fading @ 2018-09-30 06:51:44
@[我是一个菜鸡](/space/show?uid=20309) orz
by ddwqwq @ 2018-09-30 17:47:19
@[我是一个菜鸡](/space/show?uid=20309) 怎么做到的？我主席树、普通线段树、随机化都敲了一遍，然而全都被卡了。。
by ddwqwq @ 2018-09-30 17:50:32
@[杜岱玮](/space/show?uid=64366) 我的主席树开20倍就过了
```
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
int n,m,cnt;
struct node{
int l,r,sum;
}tree[maxn*20];
struct value{
int x,id;
}x[maxn];
bool cmp(value v1,value v2){
return v1.x<v2.x;
}
int root[maxn],ra[maxn];
void update(int num,int &rt,int l,int r){
tree[++cnt]=tree[rt]; rt=cnt; tree[rt].sum++;
int mid=(l+r)/2;
if (l==r) return;
if (num<=mid) update(num,tree[rt].l,l,mid);
else update(num,tree[rt].r,mid+1,r);
}
int query(int i,int j,int k,int l,int r){
int mid=(l+r)/2;
if (l==r) return l;
if (2*(tree[tree[j].l].sum-tree[tree[i].l].sum)>k) return query(tree[i].l,tree[j].l,k,l,mid);
if (2*(tree[tree[j].r].sum-tree[tree[i].r].sum)>k) return query(tree[i].r,tree[j].r,k,mid+1,r);
else return 0;
}
int main(){
cnt=1;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&ra[i]);
}
for(int i=1;i<=n;i++){
root[i]=root[i-1];
update(ra[i],root[i],1,n);
}
int left,right;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&left,&right);
printf("%d\n",query(root[left-1],root[right],right-left+1,1,n));
}
return 0;
}
```
by Fading @ 2018-09-30 19:33:31