题目链接：EOJ-2020“游族杯”C题 Coronavirus Battle
题意
有 (n(1leq nleq 10^5)) 个细胞，每个细胞各有一个三维坐标表示其位置，坐标由给定随机种子的伪随机数产生（随机数的范围是 unsigned long long）。病毒会对细胞进行多轮攻击，在第 (k) 轮攻击中，细胞 (i) 能够存活当且仅当存在细胞 (j) 满足 (x_jleq x_i && y_jleq y_i && z_jleq z_i && (x_j<x_i || y_j<y_i||z_j<z_i)) ，其中细胞 (j) 要满足病毒第 (k-1) 轮攻击后仍存活。求病毒攻击几轮之后能消灭所有细胞，和每个细胞各能存活几轮。
思路
解法一：枚举优化
首先容易想到三重循环的暴力解法，枚举轮数、枚举各个细胞 (i)，枚举各个细胞 (j) 判断 (j) 能否保护 (i) 。
由于坐标由随机数产生，所以细胞在坐标系上的分布是均匀的，可以发现最多攻击约 100 轮就能消灭所有细胞。但这样三重循环仍然很慢，考虑优化第二、三重循环的枚举：
- 上一轮病毒攻击后已经被消灭的细胞对后面都没有作用了，直接剔除出去，不参与下一轮的枚举；
- 对三维坐标的其中一个维度排序，比如对 (x) 轴的坐标从小到大排序，那么细胞 (j) 能够保护细胞 (i) 由于要满足 (x_jleq x_i) ，可得 (j<i) ，所以第三重循环的上界为 (i) 即可（这里说的 (i,j) 是排序后的细胞新编号）。但即使第三重循环的上界为 (i) 仍然不够优秀，我们思考如果 (j) 能保护 (i) 并且 (j) 能在这一轮后存活，那么保护 (j) 的细胞 (j_1) 其实也能够保护 (i) ；如果 (j_1) 能存活，那么保护 (j_1) 的细胞 (j_2) 也能保护 (i) ...... 这样一重重套下去，最终肯定有一个在这一轮后不能存活的细胞 (j_k) 能够保护 (i) ，且 (j_k<...<j_2<j_1<j<i) 。所以第三重循环只要枚举在这一轮已死的细胞即可，不用枚举能存活的细胞。
- 由于随机数的范围很大，所以基本不可能随机出相同的数字，所以 (x_jleq x_i && y_jleq y_i && z_jleq z_i && (x_j<x_i || y_j<y_i||z_j<z_i)) 也等价于 (x_j<x_i && y_j<y_i && z_j<z_i) 。因为这条逻辑表达式是放在最内层循环中，是程序中被执行次数最多的语句，所以这样改后能优化一些时间。
解法二：cdq分治
前置知识：cdq分治
观察到 (x_j<x_i && y_j<y_i && z_j<z_i) 这个形式和 三维偏序 问题十分相似，三维偏序问题就是 cdq 分治的典型问题。只是三维偏序问题求的是满足表达式的元素数量，而这道题并不是有多少个 (j) 能保护 (i) ，(i) 就能存活多少轮。我们用 (j_k o j_{k-1} o...j_2 o j_1) 来表示细胞 (j_k) 能保护 (j_{k-1}) ，(j_{k-1}) 能保护 (j_{k-2}) ...... (j_2) 能保护 (j_1) 这样一条保护链，那么 (j_1) 能够存活几轮就取决于这条链的长度。实际情况不是简单的链形关系，而是“有向图”形关系，如果说三维偏序问题各元素建模成“有向图”形关系后是求每个结点的前缀结点数量，那么这道题就是求每个结点的最长前缀链长度。这里只是形象化的理解，不是真要构建有向图来求解，这对于求解问题的时间空间复杂度并没有帮助。
从求数量变成求最长，cdq 分治中的树状数组维护前缀和就要变成维护前缀最大长度值。通常，cdq 分治都是先处理完 ([l,mid]) 和 ([mid+1,r]) ，再归并处理 ([l,r]) ，在这道题中，([l,r]) 要在 ([mid+1,r]) 之前处理。比如 (1 o 2 o3 o 4) ，先处理 ([1,2]) ，能知道 (2) 有 (1 o 2) 这条长度为 2 的前缀链，再处理 ([3,4]) ，能知道 (4) 有 (3 o 4) ，最后处理 ([1,4]) ，只能知道 (4) 还有 (1 o 2 o 4) 这条长度为 3 的前缀链；如果先处理 ([1,4]) ，就能更新 (3) 的前缀链长度为 3，再处理 ([3,4]) ，能用 (3) 去更新 (4) 的前缀链长度为 4 。时间复杂度 (O(nlog^2n)) 。
代码实现
枚举优化：
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 100010;
struct node {
int id;
unsigned long long x, y, z;
} cell[maxn];
int ans[maxn];
unsigned long long k1, k2;
unsigned long long CoronavirusBeats() {
unsigned long long k3 = k1, k4 = k2;
k1 = k4;
k3 ^= k3 << 23;
k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
return k2 + k4;
}
bool cmp(const node &a, const node &b) {
if (a.x != b.x) return a.x < b.x;
if (a.y != b.y) return a.y < b.y;
return a.z < b.z;
}
int main() {
int n;
cin >> n >> k1 >> k2;
for (int i = 0; i < n; i++) {
cell[i].x = CoronavirusBeats();
cell[i].y = CoronavirusBeats();
cell[i].z = CoronavirusBeats();
cell[i].id = i;
}
int lun;
sort(cell, cell+ n, cmp);
vector<int> sur; // 目前还存活的细胞
for (int i = 0; i < n; i++) sur.push_back(i);
for (lun = 1; sur.size() > 0; lun++) { // 枚举每一轮
vector<int> die, tmp_sur; // die表示在这一轮被消灭的细胞
die.push_back(sur[0]); // sur[0]是x坐标最小的细胞，肯定没被保护
ans[cell[sur[0]].id] = lun - 1;
for (int i = 1; i < sur.size(); i++) {
int ii = sur[i];
bool flag = false; // 细胞i能否在这一轮存活
/* 由于按坐标排序了，如果细胞i能在这一轮存活，那么能保护i的所有细胞中
肯定有这一轮已死的，逆否命题就是如果这一轮已死的所有细胞都不能保护i，
那么i也不能存活 */
for (int j : die) {
if (cell[j].x < cell[ii].x || cell[j].y < cell[ii].y || cell[j].z < cell[ii].z) {
flag = true;
break;
}
}
if (flag) tmp_sur.push_back(ii);
else {
ans[cell[ii].id] = lun - 1;
die.push_back(ii);
}
}
sur = tmp_sur;
}
printf("%d
", lun - 1);
for (int i = 0; i < n; i++) printf("%d%c", ans[i], "
"[i==n]);
return 0;
}
cdq分治：
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100010;
struct node {
int id;
unsigned long long x, y, z;
} cell[maxn], tmp_c[maxn];
int ans[maxn], tr[maxn], n;
unsigned long long tmp[maxn];
unsigned long long k1, k2;
unsigned long long CoronavirusBeats() {
unsigned long long k3 = k1, k4 = k2;
k1 = k4;
k3 ^= k3 << 23;
k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
return k2 + k4;
}
bool cmpx(const node &a, const node &b) {
return a.x < b.x;
}
bool cmpy(const node &a, const node &b) {
return a.y < b.y;
}
void change() { // 对z轴的值离散化
for (int i = 0; i < n; i++) tmp[i] = cell[i].z;
sort(tmp, tmp + n);
for (int i = 0; i < n; i++) cell[i].z = lower_bound(tmp, tmp + n, cell[i].z) - tmp + 1;
}
int lowbit(int x) {
return x & -x;
}
void update(int x, int val) {
while (x <= n) tr[x] = max(tr[x], val), x += lowbit(x);
}
int query(int x) {
int res = 0;
while (x) res = max(res, tr[x]), x -= lowbit(x);
return res;
}
void recover(int x) {
while (x <= n) tr[x] = 0, x += lowbit(x);
}
void cdq_solve(int l, int r) {
int mid = (l + r) >> 1;
for (int i = l; i <= mid; i++) tmp_c[i] = cell[i];
for (int i = mid + 1; i <= r; i++) tmp_c[i] = cell[i];
sort(tmp_c + l, tmp_c + mid + 1, cmpy);
sort(tmp_c + mid + 1, tmp_c + r + 1, cmpy);
int j = l;
for (int i = mid + 1; i <= r; i++) {
for (; j <= mid && tmp_c[j].y < tmp_c[i].y; j++) {
update(tmp_c[j].z, ans[tmp_c[j].id]);
}
ans[tmp_c[i].id] = max(ans[tmp_c[i].id], query(tmp_c[i].z) + 1);
}
int delj = j;
for (int i = l; i < delj; i++) recover(tmp_c[i].z);
}
void cdq(int l, int r) {
if (l == r) return ;
int mid = (l + r) >> 1;
cdq(l, mid);
cdq_solve(l, r);
cdq(mid + 1, r);
}
int main() {
scanf("%d %llu %llu", &n, &k1, &k2);
for (int i = 0; i < n; i++) {
cell[i].x = CoronavirusBeats();
cell[i].y = CoronavirusBeats();
cell[i].z = CoronavirusBeats();
cell[i].id = i;
ans[i] = 1;
}
sort(cell, cell+ n, cmpx);
change();
cdq(0, n - 1);
printf("%d
", *max_element(ans, ans + n));
for (int i = 0; i < n; i++) printf("%d%c", ans[i] - 1, "
"[i==n-1]);
return 0;
}