题目:
给个序列,问[l,r]区间内是否存在x>(r-l+1)>>1
题解:
好像大家都觉得这个题比较简单,没人写题解啊
先说BZOJ样例的格式应该是,第二个数是序列中数的范围(就是不用离散化)
10 3
1 2 1 2 1 2 3 2 3 3
8
1 2
1 3
1 4
1 5
2 5
2 6
6 9
7 10
这是经典的主席树问题,
按序列顺序依次让a[i]位置++,维护区间数的数目
我们二分答案然后从root[l-1]和root[r]开走
显然答案x满足sum[代表点x的节点]>(sum[r]-sum[l-1])/2
如果右子树-右子树满足要求,那就走到右子树,然后答案应该变大
同理左子树,如果都不行就没答案了
#include<cstdio>
#define N 300000*20
using namespace std;
int root[N],lc[N],rc[N],sum[N],n,m,x,pcnt,Lim;
void insert(int x,int &y,int l,int r,int k)
{
lc[y=++pcnt]=lc[x],rc[y]=rc[x],sum[y]=sum[x]+;
if (l==r) return ;
int mid=l+r>>;
if (k<=mid) insert(lc[x],lc[y],l,mid,k);
else insert(rc[x],rc[y],mid+,r,k);
}
int query(int L,int R)
{
int l=,r=Lim,mid,lim=(R-L+)>>,x=root[L-],y=root[R];
while (l<r)
{
if (sum[y]-sum[x]<=lim) return ;
mid=l+r>>;
if (sum[lc[y]]-sum[lc[x]]>lim)
r=mid,x=lc[x],y=lc[y];
else if (sum[rc[y]]-sum[rc[x]]>lim)
l=mid+,x=rc[x],y=rc[y];
else return ;
}
return l;
}
int main()
{
scanf("%d%d",&n,&Lim);
for (int i=;i<=n;i++)
scanf("%d",&x),insert(root[i-],root[i],,Lim,x);
scanf("%d",&m);
for (int i=,l,r;i<=m;i++)
scanf("%d%d",&l,&r),(x=query(l,r))?printf("yes %d\n",x):puts("no");
return ;
}