[ZJOI2013]K大数查询——整体二分

新科技：整体二分

它能解决的典型问题：带修改区间第\(k\)大

大概的做法是这样的：我们一次二分一个值\(mid\)，然后依据操作的答案与\(mid\)的大小关系把操作分别划到两边，然后递归下去。也就是相当于二分的是所有询问的答案

感觉其实这个跟在权值线段树上二分一个效果，只是用离线的方式替代掉了那一层权值线段树而已

计算可得复杂度为\(O(nlog^2n)\)（由主定理，\(T(n)=2T(n/2)+O(nlogn)=O(nlog^2n)\)）

拿线段树或者树状数组维护都行

板子题是这一道K大数查询

直接上代码了，很好写，跟\(cdq\)分治写起来很像

#include 
#include  
#include   
#include   
#include    
#include    
#include    
#include     
#include     
#include     
#include       
#include       

using namespace std;

#define ull unsigned long long
#define pii pair
#define uint unsigned int
#define mii map
#define lbd lower_bound
#define ubd upper_bound
#define INF 0x3f3f3f3f
#define IINF 0x3f3f3f3f3f3f3f3fLL
#define vi vector
#define ll long long
#define mp make_pair
#define pb push_back
#define re register
#define il inline

#define N 100000
#define M 100000

int n, m, qtot, ans[M+5];

struct Query {
  int type;
  int a, b, id;
  ll c;
}q[M+5], tl[M+5], tr[M+5];

struct SegmentTree {
  ll sumv[4*N+5], addv[4*N+5];
  int lson(int o) { return (o<<1); }
  int rson(int o) { return (o<<1|1); }
  void init() {
    memset(sumv, 0, sizeof sumv);
    memset(addv, 0, sizeof addv);
  }
  void pushup(int o) {
    sumv[o] = sumv[lson(o)]+sumv[rson(o)];
  }
  void pushdown(int o, int l, int r) {
    if(addv[o]) {
      int mid = (l+r)>>1;
      sumv[lson(o)] += (mid-l+1)*addv[o], addv[lson(o)] += addv[o];
      sumv[rson(o)] += (r-mid)*addv[o], addv[rson(o)] += addv[o];
      addv[o] = 0;
    }
  }
  void add(int o, int l, int r, int L, int R, ll k) {
    if(L <= l && r <= R) {
      sumv[o] += (r-l+1)*k, addv[o] += k;
      return ;
    }
    pushdown(o, l, r);
    int mid = (l+r)>>1;
    if(L <= mid) add(lson(o), l, mid, L, R, k);
    if(R > mid) add(rson(o), mid+1, r, L, R, k);
    pushup(o);
  }
  ll query(int o, int l, int r, int L, int R) {
    if(L <= l && r <= R) return sumv[o];
    pushdown(o, l, r);
    int mid = (l+r)>>1;
    ll ret = 0;
    if(L <= mid) ret += query(lson(o), l, mid, L, R);
    if(R > mid) ret += query(rson(o), mid+1, r, L, R);
    return ret;
  }
}ST;

void solve(int l, int r, int L, int R) {
  if(l > r) return ;
  if(L == R) {
    for(int i = l; i <= r; ++i) if(q[i].type == 2) ans[q[i].id] = L;
    return ;
  }
  int mid = L+(R-L)/2;
  int tot1 = 0, tot2 = 0;
  for(int i = l; i <= r; ++i) {
    if(q[i].type == 1) {
      if(q[i].c > mid) ST.add(1, 1, n, q[i].a, q[i].b, 1), tr[++tot2] = q[i];
      else tl[++tot1] = q[i];
    }
    else {
      ll v = ST.query(1, 1, n, q[i].a, q[i].b);
      if(v >= q[i].c) tr[++tot2] = q[i];
      else q[i].c -= v, tl[++tot1] = q[i];
    }
  }
  for(int i = 1; i <= tot1; ++i) q[l+i-1] = tl[i];
  for(int i = 1; i <= tot2; ++i) {
    q[l+tot1+i-1] = tr[i];
    if(tr[i].type == 1) ST.add(1, 1, n, tr[i].a, tr[i].b, -1);
  }
  solve(l, l+tot1-1, L, mid), solve(l+tot1, r, mid+1, R);
}

int main() {
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; ++i) {
    scanf("%d%d%d%lld", &q[i].type, &q[i].a, &q[i].b, &q[i].c);
    if(q[i].type == 2) q[i].id = ++qtot;
  }
  solve(1, m, -n, n);
  for(int i = 1; i <= qtot; ++i) printf("%d\n", ans[i]);
  return 0;
}

Another One?

还有一道比较板的题 MET-Meteors，这题可能需要稍微卡卡常数才能过，直接把代码扔过来了

#include 
#include  
#include   
#include   
#include    
#include    
#include    
#include     
#include     
#include     
#include       
#include       

using namespace std;

#define ull unsigned long long
#define pii pair
#define uint unsigned int
#define mii map
#define lbd lower_bound
#define ubd upper_bound
#define INF 0x3f3f3f3f
#define IINF 0x3f3f3f3f3f3f3f3fLL
#define vi vector
#define ll long long
#define mp make_pair
#define pb push_back
#define re register
#define il inline

#define N 300000
#define M 300000
#define K 300000

inline char Getchar(){
  static char buf[512], *p1=buf, *p2=buf;
  return p1==p2&&(p2=(p1=buf)+fread(buf,1,512,stdin),p1==p2)?EOF:*p1++;
}

inline int read() {
  int s = 0; char c = Getchar();
  while(c < '0' || c > '9') c = Getchar();
  while(c >= '0' && c <= '9') s = s*10+c-'0', c = Getchar();
  return s;
}

int n, m, k, tot;
int cnt[N+5], head[N+5], want[N+5], belong[M+5], ans[N+5];

struct Opt {
  bool type;
  int l, r, a;
  int time;
  int *pos;
}q[M+N+5], swp[M+N+5];

struct BIT {
  ll b[M+5];
  int lowbit(int x) {
    return x&-x;
  }
  void update(int x, ll k) {
    if(!x) return ;
    while(x <= m) {
      b[x] += k;
      x += lowbit(x);
    }
  }
  void add(int l, int r, ll k) {
    if(l <= r) update(l, k), update(r+1, -k);
    else update(l, k), update(m+1, -k), update(1, k), update(r+1, -k);
  }
  ll query(int x) {
    ll ret = 0;
    while(x) {
      ret += b[x];
      x -= lowbit(x);
    }
    return ret;
  }
}bit;

ll getsum(Opt &q) {
  ll ret = 0;
  for(int i = 0; i < cnt[q.l]; ++i) {
    ll v = bit.query(q.pos[i]);
    if(v >= IINF-ret) ret = INF;
    ret += v;
  }
  return ret;
}

void solve(int l, int r, int L, int R) {
  if(l > r) return ;
  if(L == R) {
    for(int i = l; i <= r; ++i) if(q[i].type == 1) ans[q[i].l] = L;
    return ;
  }
  int i, mid = L+(R-L)/2, tot1 = 0, tot2 = r-l+2;
  for(i = l; i <= r; ++i) {
    if(q[i].type == 0) {
      if(q[i].time <= mid) bit.add(q[i].l, q[i].r, q[i].a), swp[++tot1] = q[i];
      else swp[--tot2] = q[i];
    }
    else {
      ll v = getsum(q[i]);
      if(v >= q[i].a) swp[++tot1] = q[i];
      else q[i].a -= v, swp[--tot2] = q[i];
    }
  }
  for(i = 1; i <= tot1; ++i) {
    if(swp[i].type == 0) bit.add(swp[i].l, swp[i].r, -swp[i].a);
    q[i+l-1] = swp[i];
  }
  for(i = r-l+1; i >= tot2; --i) q[r+1-i+tot1] = swp[i];
  solve(l, l+tot1-1, L, mid), solve(l+tot1, r, mid+1, R);
}

int main() {
  n = read(), m = read(); 
  for(int i = 1; i <= m; ++i) belong[i] = read(), cnt[belong[i]]++;
  for(int i = 1; i <= n; ++i) want[i] = read();
  k = read();
  for(int i = 1, l, r, a; i <= k; ++i) {
    l = read(), r = read(), a = read();
    q[++tot] = {0, l, r, a, i};
  }
  for(int i = 1; i <= n; ++i) {
    q[tot+i] = {1, i, i, want[i]};
    q[tot+i].pos = new int[cnt[i]];
  }
  for(int i = 1; i <= m; ++i) q[tot+belong[i]].pos[head[belong[i]]++] = i;
  tot += n;
  solve(1, tot, 1, k+1);
  for(int i = 1; i <= n; ++i) {
    if(ans[i] == k+1) printf("NIE\n");
    else printf("%d\n", ans[i]);
  }
  return 0;
}
分治——整体二分整体二分

相关

bzoj4009 [HNOI2015]接水果 整体二分+扫描线+树状数组+dfs序

标签