[POI2014]KUR-Couriers

Posted on | In

主席树都不会写迟早药丸

递归查询是否存在有严格众数的区间即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
const int maxn=500005;
int cnt,a[maxn],ls[maxn<<5],rs[maxn<<5],sum[maxn<<5],root[maxn];
inline void Modify (int &now,int last,int l,int r,int pos) {
	now=++cnt; sum[now]=sum[last]+1;
	if(l==r) return ; register int mid=(l+r)>>1;
	if(pos<=mid) rs[now]=rs[last],Modify(ls[now],ls[last],l,mid,pos);
	else ls[now]=ls[last],Modify(rs[now],rs[last],mid+1,r,pos);
}
inline int Query (int u,int v,int l,int r,int num) {
	if(l==r) return (l+r)>>1; register int mid=(l+r)>>1;
	register int xl=sum[ls[v]]-sum[ls[u]],xr=sum[rs[v]]-sum[rs[u]];
	if(xl<=num/2&&xr<=num/2) return 0;
	else if(xl>num/2) return Query(ls[u],ls[v],l,mid,num);
	else if(xr>num/2) return Query(rs[u],rs[v],mid+1,r,num);
}
inline int read () {
	char ch=getchar(); register int num=0;
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) num=(num<<3)+(num<<1)+(ch^'0'),ch=getchar();
	return num;
}
int main () {
	register int n=read(),Q=read();
	for(register int i=1;i<=n;++i) a[i]=read();
	for(register int i=1;i<=n;++i) Modify(root[i],root[i-1],1,n,a[i]);
	while(Q--) {
		register int l=read(),r=read();
		printf("%d\n",Query(root[l-1],root[r],1,n,r-l+1));
	}
	return 0;
}