CONTENT: CDQ分治
DETAIL: 三维偏序、优化DP
BB
作业刚写完系列 tcl 还不知道会不会挂 tcl++
Introduction
CDQ分治用于解决三维偏序问题，在此基础上延申了优化DP、整体二分等
二维偏序就比如说求x1<x2,y1<y2的数目
三维偏序就比如说求x1<x2,y1<y2,z1<z2的数目
显然，二维偏序可以通过排序+树状数组的方式解决，而CDQ分治在此基础上套了一层分治
- OI-WIKI CDQ分治
https://oi-wiki.org/misc/cdq-divide/
[CQOI2011]动态逆序对 - Luogu P3157
Description
对于序列A，它的逆序对数定义为满足i<j，且Ai>Aj的数对(i,j)的个数。给1到n的一个排列，按照某种顺序依次删除m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。
输入第一行包含两个整数n和m，即初始元素的个数和删除的元素个数。以下n行每行包含一个1到n之间的正整数，即初始排列。以下m行每行一个正整数，依次为每次删除的元素。
输出包含m行，依次为删除每个元素之前，逆序对的个数。
Sample Input
5 4
1
5
3
4
2
5
1
4
2
Sample Output
5
2
2
1
Solution
逆序对本身为二维偏序问题，现在删除元素，如果为每个删除的元素打上被删除时的时间戳，就变成了三维偏序问题，用CDQ分治求解
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100000 + 15;
struct Node {
int tim, val;
bool operator < (const Node& b) const {
return val < b.val;
}
};
int tree[N];
Node a[N];
int ans[N];
int mp[N];
inline void init(int n) {
memset(tree, 0, n * sizeof(int));
}
inline int lowbit(int x) {
return x & -x;
}
inline void update(int x, int val) {
for(; x < N; x += lowbit(x)) {
tree[x] += val;
}
}
inline int getSum(int x) {
int sum = 0;
for(; x > 0; x -= lowbit(x)) {
sum += tree[x];
}
return sum;
}
void cdq(int l, int r, int m) {
if(l >= r) {
return;
}
int mid = (l + r) >> 1;
cdq(l, mid, m);
cdq(mid + 1, r, m);
sort(a + l, a + mid + 1);
sort(a + mid + 1, a + r + 1);
static stack<int> stk;
for(int j = l, i = mid + 1; j <= mid; j++) {
while(i <= r && a[j].val > a[i].val) {
update(a[i].tim, 1);
stk.emplace(a[i].tim);
i++;
}
ans[a[j].tim] += (getSum(m + 1) - getSum(a[j].tim));
}
while(!stk.empty()) {
update(stk.top(), -1);
stk.pop();
}
for(int i = r, j = mid; i >= mid + 1; i--) {
while(j >= l && a[j].val > a[i].val) {
update(a[j].tim, 1);
stk.emplace(a[j].tim);
j--;
}
ans[a[i].tim] += (getSum(m + 1) - getSum(a[i].tim));
}
while(!stk.empty()) {
update(stk.top(), -1);
stk.pop();
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
while(cin >> n >> m) {
for(int i = 1; i <= n; i++) {
cin >> a[i].val;
mp[a[i].val] = i;
a[i].tim = m + 1;
}
for(int i = 1, ele; i <= m; i++) {
cin >> ele;
a[mp[ele]].tim = i;
}
init(n + 2);
ll allInversions = 0;
for(int i = n; i >= 1; i--) {
allInversions += getSum(a[i].val);
update(a[i].val, 1);
}
init(N - 1);
cdq(1, n, m);
for(int i = 1; i <= m; i++) {
cout << allInversions << "\n";
allInversions -= ans[i];
}
cout.flush();
}
}
[SDOI2011]拦截导弹 - Luogu P2487
Description
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度、并且能够拦截任意速度的导弹，但是以后每一发炮弹都不能高于前一发的高度，其拦截的导弹的飞行速度也不能大于前一发。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
在不能拦截所有的导弹的情况下，我们当然要选择使国家损失最小、也就是拦截导弹的数量最多的方案。但是拦截导弹数量的最多的方案有可能有多个，如果有多个最优方案，那么我们会随机选取一个作为最终的拦截导弹行动蓝图。
我方间谍已经获取了所有敌军导弹的高度和速度，你的任务是计算出在执行上述决策时，每枚导弹被拦截掉的概率。
Sample Input
4
3 30
4 40
6 60
3 30
Sample Output
2
0.33333 0.33333 0.33333 1.00000
Solution
显然是二维LIS问题，列出dp方程为 dp[i] = max{[j<i][xj>xi][yj>yi] dp[j]} + 1
满足三维偏序，不妨用CDQ分治解决，先递归左边，再处理中间，最后递归右边（左右中的顺序会右边的某些值不是最终值但是先被计算了的问题！）
对于每一个元素成为LIS中元素的概率，则需要在DP时同时维护数量。正反两遍DP（CDQ）后，枚举每个元素，看看正反的DP值相加减1是否等于LIS，也就是看看接上去能不能成为LIS，能的话根据乘法原理，成为LIS的总次数为数量相乘值，概率则为该值除以总数量
最后，总数量怎么求？DP时已经维护了数量，只需要在求概率前枚举每个元素，看正DP值（或反DP值）为LIS时累加数量即可，该值为总数量
#include <bits/stdc++.h>
using namespace std;
const int N = (int)5e4 + 15;
struct info {
int h, v, idx, dp;
double cnt;
};
struct Tree {
int len;
double sum;
Tree(): len(0), sum(0) {}
Tree(int len, double sum): len(len), sum(sum) {}
};
info a[N], b[N];
int mph[N], mpv[N];
Tree tree[N];
inline bool cmp(const info& a, const info& b) {
return a.idx < b.idx;
}
inline bool cmp1 (const info& a, const info& b) {
return a.h != b.h ? a.h < b.h : a.v < b.v;
}
inline int lowbit(int x) {
return x & -x;
}
inline void update(int x, int len, double sum) {
for(; x < N; x += lowbit(x)) {
if(tree[x].len < len) {
tree[x] = Tree{len, sum};
} else if(tree[x].len == len) {
tree[x].sum += sum;
}
}
}
inline Tree getSum(int x) {
Tree ret;
for(; x > 0; x -= lowbit(x)) {
if(tree[x].len > ret.len) {
ret = tree[x];
} else if(tree[x].len == ret.len) {
ret.sum += tree[x].sum;
}
}
return ret;
}
inline void clearTree(int x) {
for(; x < N; x += lowbit(x)) {
tree[x] = Tree{0, 0};
}
}
inline void cdq(int l, int r, info* a) {
if(r <= l) {
return;
}
int mid = (l + r) >> 1;
cdq(l, mid, a);
sort(a + l, a + mid + 1, cmp1);
sort(a + mid + 1, a + r + 1, cmp1);
int st = l;
for(int i = mid + 1; i <= r; i++) {
while(a[st].h <= a[i].h && st <= mid) {
update(a[st].v, a[st].dp, a[st].cnt);
st++;
}
Tree res = getSum(a[i].v);
if(res.len == 0) {
continue;
}
if(res.len + 1 > a[i].dp) {
a[i].dp = res.len + 1;
a[i].cnt = res.sum;
} else if(res.len + 1 == a[i].dp) {
a[i].cnt += res.sum;
}
}
for(int i = l; i < st; i++) {
clearTree(a[i].v);
}
sort(a + mid + 1, a + r + 1, cmp);
cdq(mid + 1, r, a);
}
int main() {
int n;
while(~scanf("%d", &n)) {
for(int i = 1; i <= n; i++) {
scanf("%d%d", &a[i].h, &a[i].v);
a[i].idx = i, b[i].idx = n - i + 1;
a[i].dp = b[i].dp = 1;
a[i].cnt = b[i].cnt = 1;
mph[i] = a[i].h;
mpv[i] = a[i].v;
}
sort(mph + 1, mph + n + 1);
sort(mpv + 1, mpv + n + 1);
int toth = unique(mph + 1, mph + n + 1) - mph - 1;
int totv = unique(mpv + 1, mpv + n + 1) - mpv - 1;
for(int i = 1; i <= n; i++) {
a[i].h = lower_bound(mph + 1, mph + toth + 1, a[i].h) - mph;
a[i].v = lower_bound(mpv + 1, mpv + totv + 1, a[i].v) - mpv;
}
for(int i = 1; i <= n; i++) {
b[i].h = a[i].h;
b[i].v = a[i].v;
a[i].h = toth - a[i].h + 1;
a[i].v = totv - a[i].v + 1;
}
reverse(b + 1, b + n + 1);
cdq(1, n, a);
sort(a + 1, a + n + 1, cmp);
int maxLen = 0;
for(int i = 1; i <= n; i++) {
maxLen = max(maxLen, a[i].dp);
}
double sumCnt = 0;
for(int i = 1; i <= n; i++) {
if(a[i].dp == maxLen) {
sumCnt += a[i].cnt;
}
}
cdq(1, n, b);
sort(b + 1, b + n + 1, cmp);
printf("%d\n", maxLen);
for(int i = 1; i <= n; i++) {
if(a[i].dp + b[n - i + 1].dp - 1 == maxLen) {
printf("%.5f ", a[i].cnt * b[n - i + 1].cnt / sumCnt);
} else {
printf("0.00000 ");
}
}
puts("");
}
}
