分块+二分

雨点打透心脏的1/2处 2024-04-18 08:26 70阅读 0赞

这是令人难忘的一个晚上

一个区间加1  然后求中位数的题，二分T了  原因是每次只是加1  不用每次都二分答案。

[https://vjudge.net/contest/324061\#problem/F][https_vjudge.net_contest_324061_problem_F]

代码：

#include<bits/stdc++.h>
    using namespace std;
    int n,m,blo;
    int a[60065],l[600],r[600],d[60065],add[60065],pos[60065];
    int judge(int mid){
    	int res=0;
    	for(int k,i=1;i<=blo;i++){
    		k=(int)(upper_bound(d+l[i],d+r[i]+1,mid-add[i])-(d+l[i])); 
    		res+=r[i]-l[i]+1-k;
    	}
    	return res+1;
    }
    int ll=0,rr=1e9+60065,res=0,flag=0;
    void change(){
    	int s,t,pl,pr;
    	scanf("%d%d",&s,&t);
    	if(s>t) swap(s,t);	
    	pl=pos[s],pr=pos[t];
    	if(pl==pr){
    		for(register int i=s;i<=t;i++)++a[i];
    		for(register int i=l[pl];i<=r[pl];i++)d[i]=a[i];
    		sort(d+l[pl],d+r[pl]+1);
    	}else{
    		for(int i=s;i<=r[pl];i++)a[i]++;
    		for(int i=l[pl];i<=r[pl];i++)d[i]=a[i];
    		sort(d+l[pl],d+r[pl]+1);
    		
    		for(int i=l[pr];i<=t;i++)a[i]++;
    		for(int i=l[pr];i<=r[pr];i++)d[i]=a[i];
    		sort(d+l[pr],d+r[pr]+1);
    
    		for(int k=pl+1;k<pr;k++)add[k]++;
    	}
    	if(!flag)
    	while(ll<=rr){
        	int mid = (ll+rr)/2;
        	if(judge(mid)<=n/2+1){
    	        res = mid;
        	    rr = mid-1;
        	}else ll = mid+1;
    		flag++;
    	}
    	else {
    		if(!(judge(res)<=n/2+1))res++;
    	}
    	printf("%d\n",res);
    }
    int main(){
    	while(scanf("%d%d",&n,&m)!=EOF){
    		ll=0,rr=1e9+60065,res=0,flag=0;
    		if(!n&&!m)return 0;
    		memset(add,0,sizeof(add));
    		for(int i=1;i<=n;i++)scanf("%d",&a[i]),d[i]=a[i];
    		
    		blo=sqrt(n);
    		for(int i=1;i<=blo;i++){
    			l[i]=(i-1)*sqrt(n)+1;
    			r[i]=i*sqrt(n);	
    		}
    		if(r[blo]<n){blo++;l[blo]=r[blo-1]+1;r[blo]=n;}	
    		 
    		for(int i=1;i<=blo;i++){
    			for(int j=l[i];j<=r[i];j++)pos[j]=i;	
    			sort(d+l[i],d+r[i]+1);
    		}
    		
    		while(m--)change();
    	}
    	return 0;	
    }

AC码

#include <unordered_map>
    #include <functional>
    #include <algorithm>
    #include <iostream>
    #include <cstring>
    #include <cassert>
    #include <complex>
    #include <vector>
    #include <cstdio>
    #include <queue>
    #include <cmath>
    #include <set>
    using namespace std;
    typedef pair<int, int> pii;
    typedef pair<int, pii> pip;
    typedef pair<long long, int> pli;
    
    const int N = 60005;
    const int M = 200010;
    const int inf = 1000 * 1000 * 1000;
    const int mod = int(1e9);
    
    int n , k;
    int a[N];
    
    int ina[N] , inb[N] , xumb[N];
    int d[N];
    vector <int> g[N];
    
    void upd(int z,int l,int r){
      g[z].clear();
      for(int i=ina[z];i<=inb[z];i++){
        if(i >= l && i <= r){
          ++a[i];
        }
        g[z].push_back(a[i]);
      }
      sort(g[z].begin() , g[z].end());
    }
    
    int get(int z,int x){
      return (int)g[z].size() - (lower_bound(g[z].begin() , g[z].end() , x) - g[z].begin());
    }
    
    void update(int l,int r){
      int x1 = xumb[l] , x2 = xumb[r];
      if(x1 == x2){
        upd(x1 , l , r);
        return ;
      }
      upd(x1 , l , inb[x1]);
      ++x1;
      while(x1 != x2){
        d[x1]++;
        ++x1;
      }
      upd(x2 , ina[x2] , r);
    }
    
    bool check(int x,int z){
      int sum = 0;
      for(int i=1;i<=z;i++){
        sum += get(i , x - d[i]);
      }
      return (sum * 2 > n);
    }
    
    void clean(int z){
      for(int i=1;i<=z;i++){
        g[i].clear();
        d[i] = 0;
      }
    }
    
    void solve() {
      while(cin >> n >> k){
        if(n == k && n == 0)break;
        ///
        for(int i=1;i<=n;i++){
          scanf("%d",&a[i]);
        }
        ///
        int arm = sqrt(n);
        int z = 0;
        ///
        for(int i=1;i<=n;i+=arm){
          ++z;
          ina[z] = i;
          for(int j=i;j<=min(n , i + arm - 1);j++){
            xumb[j] = z;
            g[z].push_back(a[j]);
          }
          inb[z] = min(n , i + arm - 1);
          sort(g[z].begin() , g[z].end());
        }
        ///
        int ina = 1 , inb = inf , answ;
        while(ina <= inb){
          int mid = (ina + inb) / 2;
          if(check(mid , z)){
            answ = mid;
            ina = mid + 1;
          }
          else
            inb = mid - 1;
        }
        ///
        while(k--){
          int l , r;
          scanf("%d%d",&l,&r);
          update(l , r);
          if(check(answ + 1 , z))
            ++answ;
          printf("%d\n",answ);
        }
        clean(z);
      }
    }
    
    
    int main() {
    #ifdef HAMLET
      freopen("input.txt", "r", stdin);
      freopen("output.txt", "w", stdout);
    #else
      freopen("f.in", "r", stdin);
    #endif
      solve();
      return 0;
    }

[https_vjudge.net_contest_324061_problem_F]: https://vjudge.net/contest/324061#problem/F