基础算法
三分
模板题 P3382 【模板】三分法
double lmid, rmid;
double const eps = 1e-6;
while (r - l > eps) {
lmid = (l * 2 + r) / 3;
rmid = (r * 2 + l) / 3;
if (F(lmid) > F(rmid)) r = rmid;
else l = lmid;
}
cout << l << '\n';
整体二分
例题 P3527 [POI2011] MET-Meteors
BIU (Byteotian Interstellar Union) 有 \(n\) 个成员国。
现在发现了一颗新的星球，这颗星球的轨道被分为 \(m\) 份（第 \(m\) 份和第 \(1\) 份相邻），第 \(i\) 份上有第 \(a_i\) 个国家的太空站。
这个星球经常会下陨石雨。BIU 已经预测了接下来 \(k\) 场陨石雨的情况，即第 \(i\) 场陨石雨发生在 \(l_i\) 顺时针到 \(r_i\) 的区间内，并为区间内的太空站提供 \(a_i\) 单位的陨石样本。
BIU 的第 \(i\) 个成员国希望能够收集 \(p_i\) 单位的陨石样本。你的任务是判断对于每个国家，它需要在第几次陨石雨之后，才能收集足够的陨石。
\(1\le n,m,k\le3\times10^5\)，\(1\le p_i,a_i\le10^9\)。
整体二分的思想是，当有许多个询问需要二分时，我们将所有询问一起进行二分，每次二分把询问划分为两部分，直到不能再划分为止。
视 \(n,m,k\) 同阶。二分层数共 \(O(\log n)\) 层，每层 \(O(n)\) 扫描所有询问，每个询问用树状数组查询单点前缀和，复杂度 \(O(\log n)\)。总复杂度 \(O(n\log^2n)\)。
注意差分的操作实现细节。
#include <vector>
#include <iostream>
#define f(x, y, z) for (int x = (y); x <= (z); ++x)
#define int ll
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int constexpr N = 3e5 + 10;
int n, m, k, p[N], ans[N];
vector<int> pos[N];
struct Meteor {
int l, r, w;
} a[N];
struct BIT {
int c[N];
inline int lowbit(int x) { return x & -x; }
void add(int x, int v) { while (x <= m) c[x] += v, x += lowbit(x); }
int sum(int x) { int r = 0; while (x) r += c[x], x -= lowbit(x); return r; }
} bit;
void solve(int l, int r, vector<pii> &q) {
if (q.empty()) return;
if (l > r) return;
if (l == r) {
for (pii i: q) { //验证是否合法, 不合法则无解
int idx = i.first, rmn = i.second, sum = 0;
for (int x: pos[idx]) {
if (a[l].l <= a[l].r) { if (x >= a[l].l && x <= a[l].r) sum += a[l].w; }
else { if (x <= a[l].r || x >= a[l].l) sum += a[l].w; }
if (sum >= rmn) break;
}
if (sum >= rmn) ans[idx] = l;
}
return;
}
int mid = l + r >> 1;
f(i, l, mid) { //差分
bit.add(a[i].l, a[i].w), bit.add(a[i].r + 1, -a[i].w);
if (a[i].l > a[i].r) bit.add(1, a[i].w);
}
vector<pii> lq, rq;
for (pii i: q) {
int idx = i.first, rmn = i.second, sum = 0;
for (int x: pos[idx]) {
sum += bit.sum(x);
if (sum >= rmn) break;
}
if (sum >= rmn) lq.push_back(i);
else rq.push_back(make_pair(idx, rmn - sum)); //减去左半部分的贡献
}
f(i, l, mid) { //将树状数组复原
bit.add(a[i].l, -a[i].w), bit.add(a[i].r + 1, a[i].w);
if (a[i].l > a[i].r) bit.add(1, -a[i].w);
}
solve(l, mid, lq);
solve(mid + 1, r, rq);
return;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
int x;
f(i, 1, m) {
cin >> x;
pos[x].push_back(i);
}
f(i, 1, n) cin >> p[i];
cin >> k;
f(i, 1, k) cin >> a[i].l >> a[i].r >> a[i].w;
vector<pii> q;
f(i, 1, n) q.emplace_back(i, p[i]);
solve(1, k, q);
f(i, 1, n)
if (ans[i]) cout << ans[i] << '\n';
else cout << "NIE\n";
return 0;
}
分治
- 把原先的大问题 分成几个小部分。
- 当问题 规模很小 时一般很好处理。
- 处理完子问题后，通过某些办法 合并 问题。
- 时间复杂度 \(O(n\log n)\)。
归并排序
P1177 【模板】排序
void merge_sort(int l, int r) {
if (l == r) return;
int mid = l + r >> 1;
merge_sort(l, mid);
merge_sort(mid + 1, r);
int i, j, t;
for (i = l, j = mid + 1, t = 1; i <= mid && j <= r; ++t)
if (a[i] < a[j]) b[t] = a[i], ++i;
else b[t] = a[j], ++j;
for (; i <= mid; ++i, ++t) b[t] = a[i];
for (; j <= r; ++j, ++t) b[t] = a[j];
memcpy(a + l, b + 1, sizeof(int) * (--t));
return;
}
CDQ 分治
我们把 边修改边询问 的问题称为「动态问题」，把 先修改后询问（或者无修改）的问题称为「静态问题」。
对于一系列 \([l,r]\) 范围内的修改操作和询问操作，我们考虑下列分治策略：
- 计算 \([l,mid]\) 的修改和询问；
- 计算 \((mid,r]\) 的修改和询问；
- 计算 \([l,mid]\) 的所有修改对 \((mid,r]\) 的所有询问造成的影响。
于是在分治过程中，对于每个询问，它前面的所有修改对它的影响都被计算了，也就保证了答案正确。
并且，在上述过程的第三步中，所有修改在所有询问之前，也就是说，这是一个「静态问题」。只要我们能在只与 \(r-l\) 相关（与操作总数 \(M\) 等无关）的时间内解决这个问题，那么解决整个「动态问题」的复杂度就仅仅比解决同类静态问题的复杂度多了一个 \(O(\log M)\)，即分治的复杂度。
由于这种算法基于时间顺序对操作序列进行分治，我们称之为「基于时间的分治算法」，又称为 CDQ 分治算法。
例题一 P4169 [Violet] 天使玩偶 / SJY 摆棋子
开始时平面上有 \(n\) 个点。\(m\) 次操作 \((t,x,y)\) 表示：
- 如果 \(t=1\) 则在平面上新添加一个点 \((x,y)\)；
- 如果 \(t=2\) 则询问与 \((x,y)\) 距离最近的点与它的距离，距离为曼哈顿距离。
对于 \(100\%\) 的数据，保证 \(1\le n,m\le3\times10^5\)，\(0\le x,y\le10^6\)。
假设没有 \(t=1\) 即添加点的操作，询问 \((x,y)\)，答案为 \(\min\limits_{1\le i\le n}\{|x-x_i|+|y-y_i|\}\)。
我们进行分类讨论，分别计算 \((x,y)\) 左下、左上、右下、右上的答案，取最小值即为答案。
对于左下，答案为 \(\min\{(x-x_i)+(y-y_i)\}=x+y-\max\{x_i+y_i\}\)，其中 \(x_i\le x,y_i\le y\)。
对于左上，答案为 \(\min\{(x-x_i)+(y_i-y)\}=x-y-\max\{x_i-y_i\}\)，其中 \(x_i\le x,y_i\ge y\)。
对于右下，答案为 \(\min\{(x_i-x)+(y-y_i)\}=-x+y-\max\{-x_i+y_i\}\)，其中 \(x_i\ge x,y_i\le y\)。
对于右上，答案为 \(\min\{(x_i-x)+(y_i-y)\}=-x-y-\max\{-x_i-y_i\}\)，其中 \(x_i\ge x,y_i\ge y\)。
将所有点以及询问按 \(x,y\) 排序后依次扫描，并用树状数组维护前缀最大值即可。
时间复杂度 \(O(N\log N)\)，其中 \(N=n+m\)。
现在考虑添加点的操作。首先我们可以把初始的 \(n\) 个点看作是向空平面加入 \(n\) 个点。于是问题变成了只有加入新的点和询问最近点。
对操作序列应用 CDQ 分治，重点需要解决的是分治策略的第三部分，即计算 \([l,mid]\) 的所有修改对 \((mid,r]\) 的所有询问造成的影响。在此问题中，相当于是进行 \([l,mid]\) 中所有加点操作，并且更新 \((mid,r]\) 中的所有询问的答案。我们发现这与刚才讨论的 没有加点操作 的问题完全相同，应用刚才的解法即可。
注意：每次计算分治的第三部分后，需要清空树状数组。为了保证复杂度仅与 \(r-l\) 相关，不能每次把树状数组全部初始化为 \(-\infty\)，或者新建一个树状数组。我们应该重新遍历刚才对树状数组造成影响的所有操作，并且撤销它们。
整个算法的时间复杂度为 \(O(N\log^2N)\)，其中 \(N=n+m\)。
#include <cstring>
#include <iostream>
#include <algorithm>
#define f(x, y, z) for (int x = (y); x <= (z); ++x)
#define g(x, y, z) for (int x = (y); x >= (z); --x)
using namespace std;
int constexpr N = 6e5 + 10, W = 1e6 + 10;
int constexpr INF = 0x3f3f3f3f;
int n, m, ans[N], Y = -INF;
inline int &gmx(int &a, int const &b) { return a = a > b ? a : b; }
inline int &gmn(int &a, int const &b) { return a = a < b ? a : b; }
struct BIT {
int c[W];
inline int lb(int const &x) { return x & -x; }
void insert(int x, int const &v) { while (x < Y) gmx(c[x], v), x += lb(x); }
int mx(int x) { int r = -INF; while (x) gmx(r, c[x]), x -= lb(x); return r; }
void clr(int x) { while (x <= Y) c[x] = -INF, x += lb(x); }
} T;
struct Operation {
int x, y, id;
int fl; //0: 加点; 1: 询问
inline bool operator<(Operation const &o) const {
return x == o.x ? y < o.y : x < o.x;
}
} a[N], b[N];
int cnt;
void calc() {
f(i, 1, cnt)
if (b[i].fl) gmn(ans[b[i].id], b[i].x + b[i].y - T.mx(b[i].y));
else T.insert(b[i].y, b[i].x + b[i].y);
f(i, 1, cnt) if (!b[i].fl) T.clr(b[i].y);
f(i, 1, cnt)
if (b[i].fl) gmn(ans[b[i].id], b[i].x - b[i].y - T.mx(Y - b[i].y));
else T.insert(Y - b[i].y, b[i].x - b[i].y);
f(i, 1, cnt) if (!b[i].fl) T.clr(Y - b[i].y);
g(i, cnt, 1)
if (b[i].fl) gmn(ans[b[i].id], -b[i].x + b[i].y - T.mx(b[i].y));
else T.insert(b[i].y, -b[i].x + b[i].y);
f(i, 1, cnt) if (!b[i].fl) T.clr(b[i].y);
g(i, cnt, 1)
if (b[i].fl) gmn(ans[b[i].id], -b[i].x - b[i].y - T.mx(Y - b[i].y));
else T.insert(Y - b[i].y, -b[i].x - b[i].y);
f(i, 1, cnt) if (!b[i].fl) T.clr(Y - b[i].y);
return;
}
void solve(int l, int r) {
int mid = l + r >> 1;
if (l < mid) solve(l, mid);
if (mid + 1 < r) solve(mid + 1, r);
cnt = 0;
f(i, l, r)
if ((i <= mid && !a[i].fl) || (i > mid && a[i].fl))
b[++cnt] = a[i], b[cnt].id = i;
sort(b + 1, b + cnt + 1);
calc();
return;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
memset(T.c, 0xc0, sizeof T.c);
memset(ans, 0x3f, sizeof ans);
cin >> n >> m; m += n;
f(i, 1, n) cin >> a[i].x >> a[i].y, ++a[i].y, gmx(Y, a[i].y);
f(i, n + 1, m) {
cin >> a[i].fl >> a[i].x >> a[i].y;
--a[i].fl, ++a[i].y, a[i].id = i;
gmx(Y, a[i].y);
}
++Y;
solve(1, m);
f(i, n + 1, m) if (a[i].fl) cout << ans[i] << '\n';
return 0;
}
例题二 P3810 【模板】三维偏序（陌上花开）
给定 \(n\) 组 \((a_i,b_i,c_i)\)（\(1\le i\le n\)），设 \(f(i)\) 表示 \(j\) 的个数，满足 \(j\ne i,a_j\le a_i,b_j\le b_i,c_j\le c_i\)。
对于每一个 \(d\in[0,n)\)，求 \(f(i)=d\) 的 \(i\) 的数量。
\(1\le n\le10^5\)，\(1\le a_i,b_i,c_i\le k\le2\times10^5\)，其中 \(k\) 是所给出的最大值。
本质上，上面所说的例题一其实是有 三个维度，即 \(x\)、\(y\) 和时间维，并且时间维是 有顺序的。而 CDQ 分治的作用就是在时间维上分治，过程中处理左半部分对右半部分的贡献，然后向上递归，从而做到将三维问题变为在平面上的二维问题。
将其推广到这道题中，则可以按 \(a\) 从小到大排序后分治，过程中计算对右区间的每个点 \(i\)，求左区间的所有点 \(j\) 中，满足 \(b_j\le b_i,c_j\le c_i\) 的 \(j\) 有多少个。
具体地，我们 分别保证 左半部分和右半部分的 \(b\) 从小到大 有序，然后遍历右半部分，同时用一个指针维护左半部分的 \(b\) 始终小于 右半部分当前的 \(b\)。\(c\) 用树状数组维护即可。最后在树状数组上撤销刚才的修改。
注意：在统计答案时，要直接记在结构体中，而不是开一个全局数组统计。原因是分治过程中有一步是按 \(b\) 排序，这样就打乱了原有的下标。
注意：CDQ 分治一般解决不了有重复元素的问题，除非重复元素之间不算贡献。题目中为小于等于，因此需要先去重。
时间复杂度 \(O(n\log n\log k)\)。
#include <cstring>
#include <iostream>
#include <algorithm>
#define f(x, y, z) for (int x = (y); x <= (z); ++x)
using namespace std;
int constexpr N = 1e5 + 10, K = 2e5 + 10;
int n, k;
int res[N];
struct Node {
int a, b, c, w, ans;
inline bool operator!=(Node const &o) const {
return a != o.a || b != o.b || c != o.c;
}
} a[N], tmp[N];
int cnt;
struct BIT {
int c[K];
inline int lb(int const &x) { return x & -x; }
void add(int x, int const &v) { while (x <= k) c[x] += v, x += lb(x); }
int sum(int x) { int r = 0; while (x) r += c[x], x -= lb(x); return r; }
void clr(int x) { while (x <= k) c[x] = 0, x += lb(x); }
} T;
void solve(int l, int r) {
if (l == r) return;
int mid = l + r >> 1;
solve(l, mid);
solve(mid + 1, r);
auto cmp = [](Node const &p, Node const &q) { return p.b == q.b ? p.c < q.c : p.b < q.b; };
sort(a + l, a + mid + 1, cmp);
sort(a + mid + 1, a + r + 1, cmp);
int t = l;
f(i, mid + 1, r) {
while (t <= mid && a[i].b >= a[t].b)
T.add(a[t].c, a[t].w), ++t;
a[i].ans += T.sum(a[i].c);
}
--t; f(i, l, t) T.clr(a[i].c);
return;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> k;
f(i, 1, n) cin >> a[i].a >> a[i].b >> a[i].c;
sort(a + 1, a + n + 1, [](Node const &p, Node const &q) {
return p.a == q.a ? (p.b == q.b ? p.c < q.c : p.b < q.b) : p.a < q.a;
});
f(i, 1, n) { //去重
if (a[i] != a[i - 1])
tmp[++cnt] = a[i];
++tmp[cnt].w;
}
memcpy(a + 1, tmp + 1, sizeof(Node) * cnt);
solve(1, cnt);
f(i, 1, cnt) res[a[i].ans + a[i].w - 1] += a[i].w;
f(i, 0, n - 1) cout << res[i] << '\n';
return 0;
}
正常分治
（别问我为什么要叫正常分治，因为它就是纯纯的分治））））
「JOISC 2017 Day 4」绑架 2
不会。
标签：le,return,int,分治,mid,笔记,cin,学习,算法 From： https://www.cnblogs.com/f2021ljh/p/17381372.html