题解 P3567 【[POI2014]KUR-Couriers】

顾z

2018-10-26 15:11:02

Solution

# [顾](https://www.luogu.org/blog/RPdreamer/#)[z](https://www.cnblogs.com/-guz/) ~~你没有发现两个字里的blog都不一样嘛~~ qwq 主席树板子题 ~~话说为啥是个板子题,我也没看出来~~ 查询时需要找出出现次数为$(r-l+1)/2$的. 主席树基本操作,**离散化**是必须的. 然后建树操作与之前操作相同. 难点在于查询时候如何做. 最基本的查询,是判断当前根的左节点的$sum$与查询的大小的关系. 如果左边的$sum$大于等于$(r-l+1)/2$则,此数在左侧. 然后如何**判断在右侧**? 用当前根总共的$sum$减去左边的$sum$,即为右边的$sum$,判断是否大于$(r-l+1)/2$即可. 否则$return 0$ ``代码`` ```c++ #include<cstdio> #include<cctype> #include<algorithm> #define N 500008 #define R register using namespace std; inline void in(int &x) { int f=1;x=0;char s=getchar(); while(!isdigit(s)){if(s=='-')f=-1;s=getchar();} while(isdigit(s)){x=x*10+s-'0';s=getchar();} x*=f; } int n,m,new_n=1; int a[N],b[N],cnt; int root[N*20],sum[N*20],lson[N*20],rson[N*20]; void build(int lastroot,int &nowroot,int l,int r,int pos) { nowroot=++cnt; sum[nowroot]=sum[lastroot]+1; lson[nowroot]=lson[lastroot]; rson[nowroot]=rson[lastroot]; if(l==r)return; int mid=(l+r)>>1; if(pos<=mid)build(lson[lastroot],lson[nowroot],l,mid,pos); else build(rson[lastroot],rson[nowroot],mid+1,r,pos); } int query(int lastroot,int nowroot,int l,int r,int pos) { if(l==r)return l; int tmp=sum[lson[nowroot]]-sum[lson[lastroot]]; int mid=(l+r)>>1; if(pos<tmp)return query(lson[lastroot],lson[nowroot],l,mid,pos); if(sum[nowroot]-sum[lastroot]-tmp>pos)return query(rson[lastroot],rson[nowroot],mid+1,r,pos); return 0; } int main() { in(n),in(m); for(R int i=1;i<=n;i++)in(a[i]),b[i]=a[i]; sort(b+1,b+n+1); for(R int i=2;i<=n;i++)if(b[i]!=b[new_n])b[++new_n]=b[i]; for(R int i=1;i<=n;i++) build(root[i-1],root[i],1,new_n,lower_bound(b+1,b+new_n+1,a[i])-b); for(R int i=1,l,r;i<=m;i++) { in(l),in(r); int pos=query(root[l-1],root[r],1,new_n,(r-l+1)>>1); printf("%d\n",b[pos]); } } ```