链接：戳这里
3524: [Poi2014]Couriers Time Limit: 20 Sec Memory Limit: 256 MB [Submit][Status][Discuss] Description 给一个长度为n的序列a。1≤a[i]≤n。 m组询问，每次询问一个区间[l,r]，是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在，输出这个数，否则输出0。 Input 第一行两个数n，m。 第二行n个数，a[i]。 接下来m行，每行两个数l,r，表示询问[l,r]这个区间。 Output m行，每行对应一个答案。 Sample Input 7 5 1 1 3 2 3 4 3 1 3 1 4 3 7 1 7 6 6 Sample Output 1 0 3 0 4 HINT 【数据范围】 n,m≤500000
思路：
对于询问区间出现次数>=(r-l+1)/2次的值，我们考虑可持久化线段树。
线段树是以权值为下标建树
当前ai插进去，则线段树在走过的区间上都+1，当前区间sum表示该区间内存在多少个数
然后你每次询问的时候一直跑下去，如果跑到l==r的时候则为答案。
也就是还满足当前线段树版本为y里数l出现的个数-线段树版本为x-1里l出现的个数>=(y-x+1)/2
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<string> #include<vector> #include <ctime> #include<queue> #include<set> #include<map> #include<list> #include<stack> #include<iomanip> #include<cmath> #include<bitset> #define mst(ss,b) memset((ss),(b),sizeof(ss)) ///#pragma comment(linker, "/STACK:102400000,102400000") typedef long long ll; typedef long double ld; #define INF (1ll<<60)-1 #define Max 30*500000 using namespace std; int a[500100]; struct node{ int l,r,sum; }tr[Max]; int tot=0; void update(int &root,int l,int r,int last,int x){ root=++tot; tr[root].sum=tr[last].sum+1; tr[root].l=tr[last].l; tr[root].r=tr[last].r; if(l==r) { tr[root].l=root; tr[root].r=root; return ; } int mid=(l+r)/2; if(x<=mid) update(tr[root].l,l,mid,tr[last].l,x); else update(tr[root].r,mid+1,r,tr[last].r,x); } int query(int root,int l,int r,int last,int k){ if(l==r) return l; int mid=(l+r)/2; if(tr[tr[root].l].sum-tr[tr[last].l].sum>k) return query(tr[root].l,l,mid,tr[last].l,k); if(tr[tr[root].r].sum-tr[tr[last].r].sum>k) return query(tr[root].r,mid+1,r,tr[last].r,k); return 0; } int root[500100]; int n,m; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) update(root[i],1,n,root[i-1],a[i]); for(int i=1;i<=m;i++){ int x,y; scanf("%d%d",&x,&y); printf("%d\n",query(root[y],1,n,root[x-1],(y-x+1)/2)); } return 0; }