bzoj 2653 middle (主席树+二分)-白红宇

bzoj 2653 middle (主席树+二分)

阅读量：6285 次

发布时间：2019-06-22

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

题意：

　　一个长度为n的序列a，设其排过序之后为b，其中位数定义为b[n/2]，其中a,b从0开始标号,除法取下整。

　　给你一个长度为n的序列s。

　　回答Q个这样的询问：s的左端点在[a,b]之间,右端点在[c,d]之间的子序列中，最大的中位数。

　　其中a<b<c<d。

　　位置也从0开始标号。

　　强制在线。

解法：

　　首先可以想到的是二分答案，再判断是否满足条件。

　　对于答案x，我们将原数组中大于等于x的数记1，小于的记为-1，那么一个区间是否满足中位数大于等于x的条件就是区间和大于等于0 。

　　求解子段用线段树就可以快速做到，跟网上的主流做法不同，我线段树节点记录的是区间最大最小前缀和，查询的话只需询问区间[c,d]的最大前缀和和 [a-1,b-1]的最小前缀和，两者一减就是最大的区间和，再判断它是否大于等于0 。这样子好写，而且效率更高。（虽然不知道为什么，估计是优化到常数上了，当时是跑了940MS，排到了十三名，之前都没一题排这么前过。。。）

　　当然不可能对每一个答案x都建立一颗线段树，这时就要用到主席树，按不同的答案x建树。之后随意搞搞就可以了 _(:з」∠)_

code

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
               10 #define LL long long 11 12 using namespace std; 13 14 const int N=20000+7; 15 16 int Ls[N*30],Rs[N*30],dc[N*30],mm[N*30][2]; // 0 最小值 1 最大值 17 int root[N],tot=0; 18 19 struct node{ 20 int id,key; 21 bool operator < (const node &t) const { 22 return key
               
                '9')) in=getchar(); 33 if(in=='-'){ IsN=true;num=0;} 34 else num=in-'0'; 35 while(in=getchar(),in>='0'&&in<='9'){ 36 num*=10,num+=in-'0'; 37 } 38 if(IsN) num=-num; 39 return true; 40 } 41 42 inline void pushup(int k){ 43 mm[k][0]=min(mm[Ls[k]][0],mm[Rs[k]][0])-dc[k]; 44 mm[k][1]=max(mm[Ls[k]][1],mm[Rs[k]][1])-dc[k]; 45 } 46 47 inline int bulidtree(int L,int R){ 48 int k=tot++; 49 dc[k]=0; 50 51 if (L==R){ 52 mm[k][0]=mm[k][1]=L; 53 return k; 54 } 55 56 int mid=(L+R)>>1; 57 Ls[k]=bulidtree(L,mid); 58 Rs[k]=bulidtree(mid+1,R); 59 pushup(k); 60 61 return k; 62 } 63 64 inline void COPY(int x,int y){ 65 dc[x]=dc[y]; 66 mm[x][0]=mm[y][0]; 67 mm[x][1]=mm[y][1]; 68 Ls[x]=Ls[y]; 69 Rs[x]=Rs[y]; 70 } 71 72 inline int update(int o,int x,int y,int L,int R){ 73 int k=tot++; 74 COPY(k,o); 75 if (x==L && y==R){ 76 dc[k]+=2; 77 mm[k][0]-=2; 78 mm[k][1]-=2; 79 return k; 80 } 81 82 int mid=(L+R)>>1; 83 if (y<=mid) Ls[k]=update(Ls[k],x,y,L,mid); 84 else if (x>mid) Rs[k]=update(Rs[k],x,y,mid+1,R); 85 else { 86 Ls[k]=update(Ls[k],x,mid,L,mid); 87 Rs[k]=update(Rs[k],mid+1,y,mid+1,R); 88 } 89 pushup(k); 90 91 return k; 92 } 93 94 inline int query(int o,int x,int y,int L,int R,int op){ 95 if (L==x && R==y) return mm[o][op]; 96 97 int mid=(L+R)>>1; 98 if (y<=mid) return query(Ls[o],x,y,L,mid,op)-dc[o]; 99 else if (x>mid) return query(Rs[o],x,y,mid+1,R,op)-dc[o];100 else {101 if (op==1) return max(query(Ls[o],x,mid,L,mid,op),query(Rs[o],mid+1,y,mid+1,R,op))-dc[o];102 else return min(query(Ls[o],x,mid,L,mid,op),query(Rs[o],mid+1,y,mid+1,R,op))-dc[o];103 }104 }105 106 inline bool ok(int x,int a,int b,int c,int d){107 return query(root[x],c,d,0,n,1)-query(root[x],a-1,b-1,0,n,0)>=0;108 }109 110 inline int search(int a,int b,int c,int d){111 int L=1,R=n;112 int mid;113 while (L<=R){114 mid=(L+R)>>1;115 if (ok(mid,a,b,c,d)) L=mid+1;116 else R=mid-1;117 }118 return sorted[R];119 }120 121 int main(){122 scan_d(n);123 for (int i=1;i<=n;i++){124 scan_d(a[i].key);125 sorted[i]=a[i].key;126 a[i].id=i;127 }128 sort(sorted+1,sorted+n+1);129 sort(a+1,a+n+1);130 131 root[0]=bulidtree(0,n);132 int j=1;133 for (int i=1;i<=n;i++){134 root[i]=root[i-1];135 while (j<=n && a[j].key

转载于:https://www.cnblogs.com/without-ACM/p/5988963.html

你可能感兴趣的文章