题目描述
https://ac.nowcoder.com/acm/contest/33189/E
简要题意：给定 $n$ 三元组 $(x_i,y_i,z_i)$，每个三元组有一个颜色 $c_i$，现在有 $q$ 次询问，每次询问给定一个三元组 $(x_i,y_i,z_i)$，求有多少种颜色的三元组 $(x_j,y_j,z_j)$ 满足 $x_j\le x_i,y_j\le y_i,z_j\le z_i$，强制在线
$n,q\le 2\times 10^6,1\le x_i,y_i,z_i\le 400$
Solution
注意到三元组的权值范围很小，我们考虑对于每个位置预处理答案
从二维入手，对于同一种颜色的二元组，我们按照 $x_i$ 排序，容易发现 $x_i\le x_j,y_i\le y_j$ 的 $(x_j,y_j)$ 是没有用的，我们直接将其删除即可，那么剩下的二元组一定满足第一位递减，第二维递增，那么我们可以做一个这样的容斥
考虑三维如何处理，我们按照第三维排序，然后用 $set$ 维护前两维的情况动态加入和删除即可
时间复杂度 $O(n\log n +400^3+q)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
| #include <iostream>
#include <algorithm>
#include <set>
#include <random>
#define maxn 1000010
#define maxm 410
#define ll long long
using namespace std;
const int p = 998244353;
int n, q;
int d[maxm][maxm][maxm];
struct node {
int x, y, z;
friend bool operator < (const node &u, const node &v) {
if (u.x == v.x) return u.y < v.y;
return u.x < v.x;
}
} a[maxn]; set<node> S;
inline void del(set<node>::iterator it, int z) {
--d[it -> x][it -> y][z];
auto pre = it, nxt = next(it);
if (nxt != S.end()) ++d[nxt -> x][it -> y][z];
if (it != S.begin()) pre = prev(it), ++d[it -> x][pre -> y][z];
if (pre != it && nxt != S.end()) --d[nxt -> x][pre -> y][z];
S.erase(it);
}
inline void add(node x) {
++d[x.x][x.y][x.z];
auto it = S.insert(x).first, pre = it, nxt = next(it);
if (nxt != S.end()) --d[nxt -> x][it -> y][it -> z];
if (it != S.begin()) pre = prev(it), --d[it -> x][pre -> y][it -> z];
if (pre != it && nxt != S.end()) ++d[nxt -> x][pre -> y][it -> z];
}
bool check_n(node x) {
auto it = S.upper_bound(x);
if (it == S.end()) return 0;
if (it -> y >= x.y) return del(it, x.z), 1;
else return 0;
}
bool check_p(node x) {
auto it = S.upper_bound(x);
if (it == S.begin()) return 0;
if (prev(it) -> y <= x.y) return 1;
else return 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> q;
for (int o = 1; o <= n; ++o) {
int l; vector<node> vec; cin >> l;
for (int i = 1; i <= l; ++i) cin >> a[i].x >> a[i].y >> a[i].z;
sort(a + 1, a + l + 1, [](const node &u, const node &v) { return u.z < v.z; });
S.clear();
for (int i = 1; i <= l; ++i) {
while (check_n(a[i])) ;
if (!check_p(a[i])) add(a[i]);
}
} const int N = 400;
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= N; ++j)
for (int k = 1; k <= N; ++k) d[i][j][k] += d[i - 1][j][k];
for (int j = 1; j <= N; ++j)
for (int i = 1; i <= N; ++i)
for (int k = 1; k <= N; ++k) d[i][j][k] += d[i][j - 1][k];
for (int k = 1; k <= N; ++k)
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= N; ++j) d[i][j][k] += d[i][j][k - 1];
int seed; cin >> seed;
mt19937 rng(seed);
uniform_int_distribution<> u(1, 400);
ll ans = 0, lans = 0;
while (q--) {
int IQ = (u(rng) ^ lans) % 400 + 1;
int EQ = (u(rng) ^ lans) % 400 + 1;
int AQ = (u(rng) ^ lans) % 400 + 1;
lans = d[IQ][EQ][AQ];
ans= (ans * seed + lans) % p;
} cout << ans << "\n";
return 0;
}
|