[BZOJ 3524][Poi2014]Couriers：可持久化线段树

本文主要是介绍[BZOJ 3524][Poi2014]Couriers：可持久化线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

点击这里查看原题

主席树，建立权值线段树进行查询

/*
User:Small
Language:C++
Problem No.:3524
*/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=5e5+5;
int n,q,cnt,rt[M];
struct no{int ls,rs,sum;
}a[M*20];
void insert(int &rt,int pre,int l,int r,int pos){rt=++cnt;a[rt]=a[pre];a[rt].sum++;if(l==r) return;int mid=l+r>>1;if(pos<=mid) insert(a[rt].ls,a[pre].ls,l,mid,pos);else insert(a[rt].rs,a[pre].rs,mid+1,r,pos);
}
int query(int s,int t){int l=1,r=n,cnt=(t-s+1)/2;int x=rt[s-1],y=rt[t];while(l!=r){int mid=l+r>>1;if(a[y].sum-a[x].sum<=cnt) return 0;if(a[a[y].ls].sum-a[a[x].ls].sum>cnt){y=a[y].ls;x=a[x].ls;r=mid;}else if(a[a[y].rs].sum-a[a[x].rs].sum>cnt){y=a[y].rs;x=a[x].rs;l=mid+1;}else return 0;}return l;
}
int main(){freopen("data.in","r",stdin);//scanf("%d%d",&n,&q);for(int i=1;i<=n;i++){int x;scanf("%d",&x);insert(rt[i],rt[i-1],1,n,x);}while(q--){int l,r;scanf("%d%d",&l,&r);printf("%d\n",query(l,r));}return 0;
}

这篇关于[BZOJ 3524][Poi2014]Couriers：可持久化线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---