给一个长度为n的序列a。1≤a[i]≤n。
m组询问，每次询问一个区间[l,r]，是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在，输出这个数，否则输出0。
7 5
1 1 3 2 3 4 3
1 3
1 4
3 7
1 7
6 6
1
0
3
0
4
思路：主席树记录每个节点储存的个数，判断左右节点是否符合条件，递归到叶节点。
#include<bits/stdc++.h> #include<queue> #include<cstdio> #include<iostream> #define REP(i, a, b) for(int i = (a); i <= (b); ++ i) #define REP(j, a, b) for(int j = (a); j <= (b); ++ j) #define PER(i, a, b) for(int i = (a); i >= (b); -- i) using namespace std; const int maxn=5e5+10; int p[maxn],t[maxn],rt[maxn],lr[10000010],rr[10000010],cnt,tot,c[10000010],n,m; inline int read() { char ch=getchar(); while(!(ch>=‘0‘&&ch<=‘9‘))ch=getchar(); int x=0; while(ch>=‘0‘&&ch<=‘9‘){x=x*10+(ch-‘0‘);ch=getchar();} return x; } void update(int l,int r,int x,int &y,int val){ y=++tot,c[y]=c[x]+1; if(l==r)return; lr[y]=lr[x],rr[y]=rr[x]; int mid=(l+r)>>1; if(val<=mid)update(l,mid,lr[x],lr[y],val); else update(mid+1,r,rr[x],rr[y],val); } int query(int l,int r,int x,int &y,int val){ if(l==r)return l; int mid=l+r>>1; if(c[lr[y]]-c[lr[x]]>=val)return query(l,mid,lr[x],lr[y],val); else if(c[rr[y]]-c[rr[x]]>=val)return query(mid+1,r,rr[x],rr[y],val); return 0; } int main() { scanf("%d%d",&n,&m); REP(i, 1, n){ scanf("%d",&p[i]); t[i]=p[i]; } sort(t+1,t+1+n); cnt=unique(t+1,t+1+n)-t-1; REP(i, 1, n){ int cur=lower_bound(t+1,t+1+cnt,p[i])-t; update(1,cnt,rt[i-1],rt[i],cur); } REP(i, 1, m){ int l,r; scanf("%d%d",&l,&r); int ac=query(1,cnt,rt[l-1],rt[r],(r-l+1)/2+1); if(!ac)puts("0"); else printf("%d\n",t[ac]); } }
原文：https://www.cnblogs.com/czy-power/p/10370352.html