给一个数列，每次询问一个区间内有没有一个数出现次数超过一半
主席树水题
// luogu-judger-enable-o2 #include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define ll long long #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) #define pb push_back #define inf 0x3f3f3f3f #define CLR(A,v) memset(A,v,sizeof A) typedef pair<int,int>pii; ////////////////////////////////// const int N=2e6+10; int t[N<<5],T[N<<5],lson[N<<5],rson[N<<5],ncnt; void up(int x,int l,int r,int pre,int &pos) { pos=++ncnt; t[pos]=t[pre]+1; lson[pos]=lson[pre]; rson[pos]=rson[pre]; if(l==r)return ;int m=l+r>>1; if(x<=m)up(x,l,m,lson[pre],lson[pos]); else up(x,m+1,r,rson[pre],rson[pos]); Max=max(t[lson[pos]],t[rson[pos]]); } int qsum(int x,int l,int r,int pre,int pos) { if(l==r)return l; int m=l+r>>1; if(2*(t[lson[pos]]-t[lson[pre]])>x)return qsum(x,l,m,lson[pre],lson[pos]); if(2*(t[rson[pos]]-t[rson[pre]])>x)return qsum(x,m+1,r,rson[pre],rson[pos]); return 0; } int maxx,a[N]; int main() { int n,m;scanf("%d%d",&n,&m); rep(i,1,n)scanf("%d",&a[i]),maxx=max(maxx,a[i]); rep(i,1,n) up(a[i],1,maxx,T[i-1],T[i]); while(m--) { int x,y;scanf("%d%d",&x,&y); printf("%d ",qsum(y-x+1,1,maxx,T[x-1],T[y])); } return 0; }
顺便想了一下求区间出现次数最多的数 也可以用主席树很简单的维护（在底部修改 up上去）