Description
Input
Output
10 3 1 2 1 2 1 2 3 2 3 3 8 1 2 1 3 1 4 1 5 2 5 2 6 6 9 7 10
Sample Input
no
yes 1
no
yes 1
no
yes 2
no
yes 3
yes 1
no
yes 1
no
yes 2
no
yes 3
Sample Output
HINT
Notice:输入第二个整数是序列中权值的范围Lim，即1<=ai(1<=i<=n)<=Lim。
依旧主席树模板，无需离散化。
1<=Lim<=10000
Source
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #define N 10000010 5 using namespace std; 6 int sum[N],root[500010],ls[N],rs[N]; 7 int n,m,lim,sz; 8 void updata(int l,int r,int x,int &y,int v) 9 { 10 y=++sz; 11 sum[y]=sum[x]+1; 12 ls[y]=ls[x]; rs[y]=rs[x]; 13 if (l==r) return; 14 int mid=(l+r)>>1; 15 if (v<=mid) updata(l,mid,ls[x],ls[y],v); 16 else updata(mid+1,r,rs[x],rs[y],v); 17 } 18 19 int query(int L,int R) 20 { 21 int l=1,r=n,temp=(R-L+1)>>1,x=root[L-1],y=root[R],mid; 22 while (l<r) 23 { 24 if (sum[y]-sum[x]<=temp) return 0; 25 mid=(l+r)>>1; 26 if (sum[ls[y]]-sum[ls[x]]>temp) 27 { 28 r=mid; x=ls[x]; y=ls[y]; 29 } 30 else if (sum[rs[y]]-sum[rs[x]]>temp) 31 { 32 l=mid+1, x=rs[x]; y=rs[y]; 33 } 34 else return 0; 35 } 36 return l; 37 } 38 39 int main() 40 { 41 scanf("%d%d",&n,&m); 42 for (int i=1;i<=n;i++) 43 { 44 int a; 45 scanf("%d",&a); 46 updata(1,n,root[i-1],root[i],a); 47 } 48 // scanf("%d",&m); 49 for (int i=1;i<=m;i++) 50 { 51 int aa,bb; 52 scanf("%d%d",&aa,&bb); 53 int pos=query(aa,bb); 54 printf("%d ",pos); 55 // if (pos==0) printf("no "); 56 //else printf("yes %d ",pos); 57 } 58 return 0; 59 }