解题关键：观察发现答案可进行二分，二分答案，将大于等于答案的数记为1，小于的记为0，从而可以使用线段树的区间赋值和区间求和解决。

复杂度：$O(nlog^2n)$

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 using namespace std; 8 typedef long long ll; 9 const int maxn=200005; 10 int a[maxn],sum[maxn<<3],add[maxn<<3]; 11 int t1[maxn],t2[maxn],t3[maxn],v[maxn]; 12 int n,m,r; 13 14 void pushdown(int rt,int m){ 15 if(add[rt]!=-1){ 16 add[rt<<1]=add[rt]; 17 add[rt<<1|1]=add[rt]; 18 sum[rt<<1]=add[rt]*(m-(m>>1)); 19 sum[rt<<1|1]=add[rt]*(m>>1); 20 add[rt]=-1; 21 } 22 } 23 24 void pushup(int rt){ 25 sum[rt]=sum[rt<<1]+sum[rt<<1|1]; 26 } 27 28 void build(int rt,int l,int r){ 29 add[rt]=-1; 30 if(l==r){ 31 sum[rt]=v[l]; 32 return; 33 } 34 int mid=(l+r)>>1; 35 build(rt<<1,l,mid); 36 build(rt<<1|1, mid+1, r); 37 pushup(rt); 38 } 39 40 void update(int rt,int l,int r,int tl,int tr,int c){ 41 if(tl>tr) return;//落掉这句话导致在bzoj一直re 42 if(tl<=l&&tr>=r){ 43 sum[rt]=c*(r-l+1); 44 add[rt]=c; 45 return; 46 } 47 pushdown(rt, r-l+1); 48 int mid=(l+r)>>1; 49 if(tl<=mid) update(rt<<1,l,mid,tl,tr, c); 50 if(tr>mid) update(rt<<1|1, mid+1, r, tl, tr, c); 51 pushup(rt); 52 } 53 54 int query(int rt,int l,int r,int tl,int tr){ 55 if(tl<=l&&tr>=r){ 56 return sum[rt]; 57 } 58 pushdown(rt,r-l+1); 59 int mid=(l+r)>>1,res=0; 60 if(tl<=mid) res+=query(rt<<1,l,mid,tl,tr); 61 if(tr>mid) res+=query(rt<<1|1,mid+1,r,tl,tr); 62 return res; 63 } 64 65 bool check(int x){ 66 for(int i=1;i<=n;i++) v[i]= a[i]>=x?1:0; 67 build(1, 1, n); 68 for(int i=0;i
           
            >1; 87 if(check(mid)) l=mid; 88 else r=mid-1; 89 } 90 return r; 91 } 92 93 int main(){ 94 scanf("%d%d",&n,&m); 95 for(int i=1;i<=n;i++) scanf("%d",a+i); 96 for(int i=0;i