首页 > 其他分享 >整体二分

整体二分

时间：2023-04-26 15:23:58浏览次数：38  
标签：二分 int 整体 long kmaxM pc kmax include

二分的进阶版。

先看一个经典问题。

区间第K大

给定一个长度为 \(n\) 的序列 \(a\) 和 \(m\) 个询问.
每次询问给定一个区间 \([l,r]\)，输出该区间第 \(k\) 大的数。

\(n,m \le 30000，a_i \in [0, 2^{31})\)

对于单次询问，二分答案即可。

如何处理多组询问呢？

不难发现在处理每次询问时，我们都要重新进行一次二分，这个时间花费是比较大的。

于是，我们有一个大胆的想法：

将所有的询问离线，并将所有的询问同时进行二分。

整体二分

如上所述，所有询问同时处理。

具体来说，我们用 \((l, r, l', r')\) 来表示当前状态。
其中 \([l,r]\) 表示当前正在考虑的操作的编号区间（不一定是初始编号），\([l',r']\) 表示当前的答案区间。

考虑分治，将当前答案区间分成两部分 \([l',mid]\) 和 \([mid+1, r']\)，然后对每一个询问单独考虑。
判断每一个询问的答案属于左半区间右半区间，最后向下传递，直到 \(l' =r'\) 再将答案存起来。

原序列中的元素就被当作是修改加入操作序列。

代码结构大致长这样：

void Solve(int l, int r, int _l, int _r) { // 询问区间，答案区间
  if (l > r || _l > _r) return;
  if (_l == _r) { // 边界
    for (int i = l; i <= r; i++) {
      if (!q[i].op) continue; // 如果是修改则跳过
      res[q[i].id] = _l; // 存答案
    }
    return;
  }
  int mid = (_l + _r) >> 1; 
  int pc[2] = {0};
  for (int i = l; i <= r; i++) {
    if (!q[i].op) { // 是修改
      if (q[i].r <= mid) { // 左半部分, 直接修改，存储
      } else { // 右半部分，存储
      }
    } else { // 是询问
      int tot = Getres(q[i].r) - Getres(q[i].l - 1);
      if (tot >= q[i].k) { // 个数超过询问， 左半部分
      } else { // 修改询问的k，右半部分
      }
    }
  }
  // 撤除修改，避免产生后效
  for (int i = 1; i <= pc[0]; i++) {
    if (p[0][i].op) continue; // 是询问，跳过
  }
  // 将原区间按照答案区间分成连续的两个部分
  int pl = l;
  for (int i = 1; i <= pc[0]; i++) {
    q[pl++] = p[0][i];
  }
  for (int i = 1; i <= pc[1]; i++) {
    q[pl++] = p[1][i];
  }
  // 分治
  Solve(l, l + pc[0] - 1, _l, mid);
  Solve(l + pc[0], r, mid + 1, _r);
}

回到原题，要求区间第 \(k\) 大。为了便于使用树状数组修改和统计答案，我们将其转化为区间第 \(k'\) 小，直接整体二分即可。

代码：

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int kmax = 3e4 + 3;
const int kmaxM = 1e5 + 3;

struct Q {
  int l, r, k;
  int id, op, res;
} q[kmaxM], p[2][kmaxM];

int n, m, a[kmax];
int qc;
int num, b[kmax];
int c[kmax];

int Lowbit(int x) {
  return x & -x;
}

void Modify(int x, int v) {
  for (; x <= n; x += Lowbit(x)) {
    c[x] += v;
  }
}

int Getres(int x) {
  int tot = 0;
  for (; x; x -= Lowbit(x)) {
    tot += c[x];
  }
  return tot;
}

void Solve(int l, int r, int _l, int _r) {
  if (l > r || _l > _r) return;
  if (_l == _r) {
    for (int i = l; i <= r; i++) {
      if (!q[i].op)
        continue;
      q[i].res = _l;
    }
    return;
  }
  int mid = (_l + _r) >> 1;
  int pc[2] = {0};
  for (int i = l; i <= r; i++) {
    if (!q[i].op) {
      if (q[i].k <= mid) {
        p[0][++pc[0]] = q[i];
        Modify(q[i].id, 1);
      } else {
        p[1][++pc[1]] = q[i];
      }
    } else {
      int tot = Getres(q[i].r) - Getres(q[i].l - 1);
      if (tot >= q[i].k) {
        p[0][++pc[0]] = q[i];
      } else {
        q[i].k -= tot;
        p[1][++pc[1]] = q[i];
      }
    }
  }
  // 撤除修改
  for (int i = 1; i <= pc[0]; i++) {
    if (p[0][i].op) continue;
    Modify(p[0][i].id, -1);
  }
  // 分成两部分
  int pl = l;
  for (int i = 1; i <= pc[0]; i++) {
    q[pl++] = p[0][i];
  }
  for (int i = 1; i <= pc[1]; i++) {
    q[pl++] = p[1][i];
  }
  Solve(l, l + pc[0] - 1, _l, mid);
  Solve(l + pc[0], r, mid + 1, _r);
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    b[i] = a[i];
  }
  // 离散化，便于树状数组修改
  sort(b + 1, b + n + 1);
  num = unique(b + 1, b + n + 1) - b - 1;
  for (int i = 1; i <= n; i++) {
    a[i] = lower_bound(b + 1, b + num + 1, a[i]) - b;
  }
  // 将原序列转化成修改放入操作序列中
  for (int i = 1; i <= n; i++) {
    q[++qc].k = a[i], q[qc].id = i;
  }
  for (int i = 1, l, r, k; i <= m; i++) {
    scanf("%d%d%d", &l, &r, &k);
    // 转成区间第k小
    q[++qc] = {l, r, r - l + 1 - k + 1, i, 1};
  }
  Solve(1, qc, 1, num);  // 整体二分
  sort(q + 1, q + qc + 1, [](Q p, Q q) { return p.op > q.op || p.op == q.op && p.id < q.id; });
  for (int i = 1; i <= m; i++) {
    printf("%d\n", b[q[i].res]);
  }
  return 0;
}

我们将原问题进行拓展

带修改区间第K小

如题，有两种操作。

  1. 1, x, v 表示将 \(a_x\) 修改为 \(v\)。
  2. 2, l, r, k 表示询问 \([l, r]\) 的第 \(k\) 小的元素。

显然，我们只需像将序列转为修改操作那样增加修改操作即可。

代码：

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int kmax = 1e5 + 3;
const int kmaxM = 5e5 + 3;

struct Q {
  int l, r, k;
  int id, op;
} q[kmaxM], p[2][kmaxM];

int n, m, a[kmax];
int qc;
int num, b[kmax];
int c[kmax];
int res[kmax];

int Lowbit(int x) {
  return x & -x;
}

void Modify(int x, int v) {
  for (; x <= n; x += Lowbit(x)) {
    c[x] += v;
  }
}

int Getres(int x) {
  int tot = 0;
  for (; x; x -= Lowbit(x)) {
    tot += c[x];
  }
  return tot;
}

void Solve(int l, int r, int _l, int _r) {
  if (l > r || _l > _r) return;
  if (_l == _r) {
    for (int i = l; i <= r; i++) {
      if (!q[i].op) continue;
      res[q[i].id] = _l;
    }
    return;
  }
  int mid = (_l + _r) >> 1;
  int pc[2] = {0};
  for (int i = l; i <= r; i++) {
    if (!q[i].op) {
      if (q[i].r <= mid) {
        p[0][++pc[0]] = q[i];
        Modify(q[i].l, q[i].k);
      } else {
        p[1][++pc[1]] = q[i];
      }
    } else {
      int tot = Getres(q[i].r) - Getres(q[i].l - 1);
      if (tot >= q[i].k) {
        p[0][++pc[0]] = q[i];
      } else {
        q[i].k -= tot;
        p[1][++pc[1]] = q[i];
      }
    }
  }
  for (int i = 1; i <= pc[0]; i++) {
    if (p[0][i].op) continue;
    Modify(p[0][i].l, -p[0][i].k);
  }
  int pl = l;
  for (int i = 1; i <= pc[0]; i++) {
    q[pl++] = p[0][i];
  }
  for (int i = 1; i <= pc[1]; i++) {
    q[pl++] = p[1][i];
  }
  Solve(l, l + pc[0] - 1, _l, mid);
  Solve(l + pc[0], r, mid + 1, _r);
}

int main() {
  while (scanf("%d", &n) != EOF) {
    for (int i = 1; i <= n; i++) {
      scanf("%d", &a[i]);
    }
    qc = 0;
    for (int i = 1; i <= n; i++) {
      q[++qc] = {i, a[i], 1, 1, 0};
    }
    scanf("%d", &m);
    for (int i = 1, op, l, r, k; i <= m; i++) {
      scanf("%d%d%d", &op, &l, &r);
      res[i] = -1;
      if (op == 1) {
        q[++qc] = {l, a[l], -1, 1, 0};
        q[++qc] = {l, r, 1, 1, 0};
        a[l] = r;
      } else {
        scanf("%d", &k);
        q[++qc] = {l, r, k, i, 1};
      }
    }
    Solve(1, qc, 0, 1e9);
    for (int i = 1; i <= m; i++) {
      if (res[i] == -1) continue;
      printf("%d\n", res[i]);
    }
  }
  return 0;
}

[国家集训队]矩阵乘法

在矩阵上求第 \(k\) 大，做法同上，使用二维树状数组即可。

代码中没有将原问题转化为第 \(k\) 小，而是将树状数组反着做，也是可以的。

代码：

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int kmax = 503;
const int kmaxM = 1e5 + 3;

// 位置，权值
struct V {
  int x, y, c;
} v[kmax * kmax];

struct Q {
  int lx, ly, rx, ry;
  int k;
  int id;
} q[kmaxM], p[2][kmaxM];

int n, m;
int vc;
int c[kmax][kmax];
int res[kmaxM];

int Lowbit(int x) {
  return x & -x;
}

// 二维树状数组反着做
void Modify(int x, int y, int v) {
  for (int i = x; i <= n; i += Lowbit(i)) {
    for (int j = y; j <= n; j += Lowbit(j)) {
      c[i][j] += v;
    }
  }
}

int Getres(int x, int y) {
  int tot = 0;
  for (int i = x; i; i -= Lowbit(i)) {
    for (int j = y; j; j -= Lowbit(j)) {
      tot += c[i][j];
    }
  }
  return tot;
}

void Solve(int l, int r, int _l, int _r) {
  if (l > r || _l > _r) return;
  if (_l == _r) {
    for (int i = l; i <= r; i++) {
      res[q[i].id] = v[_l].c;
    }
    return;
  }
  int mid = (_l + _r) >> 1;
  int pc[2] = {0};
  // 直接把答案区间的矩阵元素的坐标取出并修改
  for (int i = _l; i <= mid; i++) {
    Modify(v[i].x, v[i].y, 1);
  }
  for (int i = l; i <= r; i++) {
    int tot = Getres(q[i].rx, q[i].ry) - Getres(q[i].lx - 1, q[i].ry) - Getres(q[i].rx, q[i].ly - 1) + Getres(q[i].lx - 1, q[i].ly - 1);
    if (tot >= q[i].k) {
      p[0][++pc[0]] = q[i];
    } else {
      q[i].k -= tot;
      p[1][++pc[1]] = q[i];
    }
  }
  // 撤除修改
  for (int i = _l; i <= mid; i++) {
    Modify(v[i].x, v[i].y, -1);
  }
  int pl = l;
  for (int i = 1; i <= pc[0]; i++) {
    q[pl++] = p[0][i];
  }
  for (int i = 1; i <= pc[1]; i++) {
    q[pl++] = p[1][i];
  }
  Solve(l, l + pc[0] -1, _l, mid);
  Solve(l + pc[0], r, mid + 1, _r);
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    for (int j = 1, w; j <= n; j++) {
      scanf("%d", &w);
      v[++vc] = {i, j, w};
    }
  }
  // 按照权值排序
  // 把矩阵的权值作为答案区间
  sort(v + 1, v + vc + 1, [](V p, V q) { return p.c < q.c; });
  for (int i = 1; i <= m; i++) {
    scanf("%d%d%d%d%d", &q[i].lx, &q[i].ly, &q[i].rx, &q[i].ry, &q[i].k);
    q[i].id = i;
  }
  // 答案区间变为答案所在的矩阵元素区间
  Solve(1, m, 1, vc); 
  for (int i = 1; i <= m; i++) {
    printf("%d\n", res[i]);
  }
  return 0;
}

[ZJOI2013]K大数查询

单点修改改为区间修改即可，使用线段树。
（我的树状数组不知道为什么寄了）

代码：

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#define int long long

using namespace std;

const int kmax = 2e5 + 3;

struct Q {
  int l, r;
  long long k;
  int id, op;
} q[kmax], p[2][kmax];

int n, m;
int res[kmax];
long long c[kmax];
long long tr[kmax << 2], laz[kmax << 2];

void Pushup(int x) {
  tr[x] = tr[x << 1] + tr[x << 1 | 1];
}

void Pushdown(int x, int l, int r) {
  if (!laz[x]) return;
  int mid = (l + r) >> 1;
  laz[x << 1] += laz[x];
  laz[x << 1 | 1] += laz[x];
  tr[x << 1] += (mid - l + 1) * laz[x];
  tr[x << 1 | 1] += (r - mid) * laz[x];
  laz[x] = 0;
}

void Update(int x, int l, int r, int _l, int _r, int v) {
  if (_l <= l && r <= _r) {
    laz[x] += v;
    tr[x] += (r - l + 1) * v;
    return;
  }
  int mid = (l + r) >> 1;
  Pushdown(x, l, r);
  if (_l <= mid) {
    Update(x << 1, l, mid, _l, _r, v);
  }
  if (_r > mid) {
    Update(x << 1 | 1, mid + 1, r, _l, _r, v);
  }
  Pushup(x);
}

long long Query(int x, int l, int r, int _l, int _r) {
  if (_l <= l && r <= _r) return tr[x];
  int mid = (l + r) >> 1;
  long long res = 0;
  Pushdown(x, l, r);
  if (_l <= mid) res += Query(x << 1, l, mid, _l, _r);
  if (_r > mid) res += Query(x << 1 | 1, mid + 1, r, _l, _r);
  return res;
}

void Solve(int l, int r, int _l, int _r) {
  if (l > r || _l > _r) return;
  if (_l == _r) {
    for (int i = l; i <= r; i++) {
      if (!q[i].op) continue;
      res[q[i].id] = _l;
    }
    return;
  }
  int mid = (_l + _r) >> 1;
  int pc[2] = {0};
  for (int i = l; i <= r; i++) {
    if (!q[i].op) {
      if (q[i].k <= mid) {
        p[0][++pc[0]] = q[i];
      } else {
        p[1][++pc[1]] = q[i];
        Update(1, 1, n, q[i].l, q[i].r, 1); // 线段树区间修改
      }
    } else {
      int tot = Query(1, 1, n, q[i].l, q[i].r); // 线段树区间查询
      if (tot >= q[i].k) {
        p[1][++pc[1]] = q[i];
      } else {
        q[i].k -= tot;
        p[0][++pc[0]] = q[i];
      }
    }
  }
  // 撤除修改
  for (int i = l; i <= r; i++) {
    if (!q[i].op && q[i].k > mid) {
      Update(1, 1, n, q[i].l, q[i].r, -1);
    }
  }
  int pl = l;
  for (int i = 1; i <= pc[0]; i++) {
    q[pl++] = p[0][i];
  }
  for (int i = 1; i <= pc[1]; i++) {
    q[pl++] = p[1][i];
  }
  Solve(l, l + pc[0] - 1, _l, mid);
  Solve(l + pc[0], r, mid + 1, _r);
}

signed main() {
  scanf("%lld%lld", &n, &m);
  int qc = 0;
  for (int i = 1; i <= m; i++) {
    scanf("%lld%lld%lld%lld", &q[i].op, &q[i].l, &q[i].r, &q[i].k);
    q[i].op--;
    if (q[i].op) q[i].id = ++qc;
  }
  Solve(1, m, 0, n);
  for (int i = 1; i <= qc; i++) {
    printf("%lld\n", res[i]);
  }
  return 0;
}

完结撒花 \ / \ / \ /

标签：二分,int,整体,long,kmaxM,pc,kmax,include
From： https://www.cnblogs.com/ereoth/p/17356189.html

相关文章

  • 折半查找（二分查找法）
    问题描述：N个有序整数数列已放在一维数组中，利用二分查找法查找整数m在数组中的位置。若找到，则输出其下标值;反之，则输出“Notbefound!”。代码：#include<iostream>#defineN10intmain(){ intk,i0=-1,a[N]={3,12,30,34,45,57,66,78,89,100}; intmid=(N-1)/......
  • 实例解释BCELoss与BCEWithLogitsLoss的关联（二分类问题）
      BCEWithLogitsLoss=Sigmoid+BCELoss，      nn接口                       Function接口nn.BCELoss()                 F.binary_cross_entropy()nn.BCEWithLogitsLos......
  • ZOJ Monthly, August 2014 ZOJ - 3806 计算几何+二分
    Atriangleisonethebasicshapesingeometry.It’sapolygonwiththreeverticesandthreesideswhicharelinesegments.AtrianglewithverticesA,B,CisdenotedΔABC.Anditsthreesides,BC,CA,ABareoftendenoteda,bandc.Theincircleofat......
  • XI Samara Regional Intercollegiate Programming Contest Problem K. Video Reviews
    Thestudio«LodkaGaming»isengagedinadvertisingoftheirnewgame«.C.O.N.T.E.S.T:UnexpectedBehaviour».Thestudio’smarketerisplanningtocommunicatewithnvideobloggersonebyone(inthepredeterminedorder,startingfromthe1-standend......
  • HDU - 5649 线段树+区间二分答案 （好题）
    DZYhasasequencea[1…n].Itisapermutationofintegers1∼n.Nowhewantstoperformtwotypesofoperations:0lr:Sorta[l…r]inincreasingorder.1lr:Sorta[l…r]indecreasingorder.Afterdoingalltheoperations,hewilltellyouapositionk,andask......
  • 51 Nod 2497 数三角形 二分
    小b有一个仅包含非负整数的数组a，她想知道有多少个三元组(i,j,k)，满足i<j<k且a[i],a[j],a[k]可能作为某个三角形的三条边的边长。 收起 输入第一行输入一个正整数n，表示数组a中元素个数；第二行n个非负整数，表示a中元素，以空格隔开；其中0＜n≤1000，a中任意元素a[i]满......
  • 二分模板 不会乱的
    (29条消息)不需要考虑mid+1、mid-1的二分查找模板，希望大家都能学会_二分查找如果lightmid不加1_一支彩色铅笔的博客-CSDN博客非常好的博客，爱来自中国二分查找为什么总是写错？_哔哩哔哩_bilibili非常好的视频，爱来自中国......
  • 数组的复制、反转、线性查找、二分查找
    publicclassArrayTest2{ publicstaticvoidmain(String[]args){ String[]arr=newString[]{"JJ","DD","MM","BB","GG","AA"}; //数组的复制(区别于数组变量的赋值：arr1=arr) String[]arr1=new......
  • codeforces 545C C. Woodcutters(dp+二分)
    题目链接：codeforces545C题目大意：给出一些树的位置和高度，每棵树可以砍倒，覆盖[xi−hi,xi]或者覆盖[xi,xi+hi],或者不砍倒，问最多砍倒多少棵树？题目分析：我们记录dp[i]表示选取到i棵树的时候用的最短的区间长度。每次枚举每棵树，二分到最大的不超过当前树位置的个数，然后利用当前树的信息......
  • codeforces 225B B. Well-known Numbers(数论+二分+贪心+构造)
    题目链接：codeforces225B题目大意：定义f(k,n)为类似菲波那契数推导，只不过变为前k项的和，然后给出一个数s，利用k-菲波那契数构造出一个不重复的集合的元素和为s，集合的规模大于1题目分析：首先因为菲波那契数的增长速度快的吓人，所以给的数据范围109很快就能达到，我们得到O(n)的构造出所有的......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99