NC 26253 坐标离散化 + 线段树BIT

题意

传送门 NC 26253

题解

每一轮遍历一次进行标记 $O(n^2)$，需要优化标记每一个妹子的算法。处理 $(a_i,b_i)$ 这样的二元组间大小关系，考虑先使其中一维有序。假设将妹子按降序排序，从前向后遍历，此时保证遍历到当前妹子 $i$ 获取的信息都是满足 $a_j>a_i$ 的妹子的信息，此时仅考虑 $b_i$ 与 $b_j$ 间的关系即可：若不存在 $j$ 使得 $b_j>b_i$，显然数组中没有妹子重要程度大于妹子 $i$；反之，查询满足 $b_j>b_i$ 的妹子 $j$ 标号的最大值 $mx$，那么妹子标号为 $mx+1$。那么以 $b_i$ 为区间索引，$RMQ$ 维护区间最大值即可。

线段树

线段树实现的 $RMQ$。

#include <bits/stdc++.h> using namespace std; #define maxn 100005 #define sg_size (1 << 18) - 1 struct girl { int a, b, id; bool operator<(const girl &b) const { return a > b.a; } } gs[maxn]; int n, a[maxn], b[maxn], t[maxn], id[sg_size]; int compress(int *x, int n) { vector<int> xs(n); for (int i = 0; i < n; i++) { xs[i] = x[i]; } sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end()); for (int i = 0; i < n; i++) { x[i] = lower_bound(xs.begin(), xs.end(), x[i]) - xs.begin(); } return xs.size(); } int query(int a, int b, int k, int l, int r) { if (b <= l || r <= a) { return 0; } else if (a <= l && r <= b) { return id[k]; } int chl = (k << 1) + 1, chr = (k << 1) + 2, m = (l + r) >> 1; return max(query(a, b, chl, l, m), query(a, b, chr, m, r)); } void update(int a, int b, int x, int k, int l, int r) { if (a <= l && r <= b) { id[k] = x; } else if (a < r && l < b) { int chl = (k << 1) + 1, chr = (k << 1) + 2, m = (l + r) >> 1; update(a, b, x, chl, l, m); update(a, b, x, chr, m, r); id[k] = max(id[chl], id[chr]); } } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d%d", a + i, b + i); } int sz = compress(b, n); for (int i = 0; i < n; i++) { gs[i] = {a[i], b[i], i}; } sort(gs, gs + n); for (int i = 0; i < n; i++) { int cur = query(gs[i].b, sz, 0, 0, sz) + 1; t[gs[i].id] = cur; update(gs[i].b, gs[i].b + 1, cur, 0, 0, sz); } for (int i = 0; i < n; i++) { printf("%d\n", t[i]); } return 0; }

BIT

考虑到 $RMQ$ 查询区间是后缀区间，那么将 $b_i$ 按降序排序的索引赋值，将查询区间转换为前缀区间。此时考虑到 $BIT$ 维护前缀信息的性质，此处可以实现基于 $BIT$ 的 $RMQ$。

#include <bits/stdc++.h> using namespace std; #define maxn 100005 struct girl { int a, b, id; bool operator<(const girl &b) const { return a > b.a; } } gs[maxn]; int n, a[maxn], b[maxn], t[maxn], bit[maxn]; int compress(int *x, int n) { vector<int> xs(n); for (int i = 0; i < n; i++) { xs[i] = x[i]; } sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end()); for (int i = 0; i < n; i++) { x[i] = xs.end() - lower_bound(xs.begin(), xs.end(), x[i]); } return xs.size(); } void add(int i, int x) { while (i <= n) { bit[i] = max(bit[i], x); i += i & -i; } } int mx(int i) { int res = 0; while (i > 0) { res = max(bit[i], res); i -= i & -i; } return res; } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d%d", a + i, b + i); } compress(b, n); for (int i = 0; i < n; i++) { gs[i] = {a[i], b[i], i}; } sort(gs, gs + n); for (int i = 0; i < n; i++) { int cur = mx(gs[i].b) + 1; t[gs[i].id] = cur; add(gs[i].b, cur); } for (int i = 0; i < n; i++) { printf("%d\n", t[i]); } return 0; }