题目:

给个序列,问[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
     
      #define N 300000*20using 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]+1;    if (l==r) return ;    int mid=l+r>>1;    if (k<=mid) insert(lc[x],lc[y],l,mid,k);    else insert(rc[x],rc[y],mid+1,r,k);}int query(int L,int R){    int l=1,r=Lim,mid,lim=(R-L+1)>>1,x=root[L-1],y=root[R];    while (l
      
       >1;        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+1,x=rc[x],y=rc[y];        else return 0;    }    return l;}int main(){    scanf("%d%d",&n,&Lim);    for (int i=1;i<=n;i++)        scanf("%d",&x),insert(root[i-1],root[i],1,Lim,x);    scanf("%d",&m);    for (int i=1,l,r;i<=m;i++)        scanf("%d%d",&l,&r),(x=query(l,r))?printf("yes %d\n",x):puts("no");    return 0;}