BZOJ-3524: [Poi2014]Couriers（可持久化线段树）-白红宇

BZOJ-3524: [Poi2014]Couriers（可持久化线段树）

阅读量：4468 次

发布时间：2019-06-08

本文共 1525 字，大约阅读时间需要 5 分钟。

3524: [Poi2014]Couriers

Time Limit: 20 Sec Memory Limit: 256 MB

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

HINT

【数据范围】

n,m≤500000

可持久化线段树，裸。。。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #include
                      
                       #include
                       
                        #include
                        
                         using namespace std;int n,m,x,y,size;int root[5000005],lef[10000010],rig[10000010],sum[10000010];void build(int l,int r,int pre,int &now,int v){ now=++size; sum[now]=sum[pre]+1; if(l==r)return ; lef[now]=lef[pre]; rig[now]=rig[pre]; int mid=(l+r)/2; if(v<=mid)build(l,mid,lef[pre],lef[now],v); else build(mid+1,r,rig[pre],rig[now],v);}int query(int l,int r){ int xx=root[l-1],yy=root[r],num=(r-l+1)/2; int L=1,R=n,mid; while(L!=R) { mid=(L+R)/2; if(sum[lef[yy]]-sum[lef[xx]]>num) { R=mid; xx=lef[xx]; yy=lef[yy]; } else if(sum[rig[yy]]-sum[rig[xx]]>num) { L=mid+1; xx=rig[xx]; yy=rig[yy]; } else return 0; } return L;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&x); build(1,n,root[i-1],root[i],x); } for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); printf("%d\n",query(x,y)); } return 0;}