題目鏈接: QwQ

Solution:

以權(quán)值為下標(biāo)，對每個點(diǎn)建樹

對于x點(diǎn)，以它為根的樹涵蓋的是1到x區(qū)間內(nèi)每個數(shù)出現(xiàn)的次數(shù)

Code:

#include<bits/stdc++.h> #define N 500001 using namespace std; int n,m,tot,rt[N]; struct chair_tree{int sum,l,r;}tree[N*21]; void ins(int &x,int v,int l,int r){tree[++tot]=tree[x];x=tot;tree[x].sum++;if(l==r) return ;int mid=(l+r)>>1;if(v<=mid) ins(tree[x].l,v,l,mid);else ins(tree[x].r,v,mid+1,r); } int query(int p1,int p2,int u,int l,int r){if(l==r) return l;int mid=(l+r)>>1;if(2*(tree[tree[p2].l].sum-tree[tree[p1].l].sum)>u)return query(tree[p1].l,tree[p2].l,u,l,mid);if(2*(tree[tree[p2].r].sum-tree[tree[p1].r].sum)>u)return query(tree[p1].r,tree[p2].r,u,mid+1,r);return 0; } int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}return x*f; } int main(){n=read(),m=read();for(int i=1;i<=n;i++){int x=read();rt[i]=rt[i-1];ins(rt[i],x,1,n);}for(int i=1;i<=m;i++){int l=read(),r=read();printf("%d\n",query(rt[l-1],rt[r],r-l+1,1,n));}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/NLDQY/p/10541933.html

總結(jié)

以上是生活随笔為你收集整理的KUR-Couriers的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。