【题解】JZOJ3854 分组

JZOJ 3854

题意

有 $n$ 个人，每个人有地位 $r_i$ 和年龄 $a_i$，对于一个若干人组成的小组，定义其队长为地位最高的成员（若相等则取二者均可），其他成员的年龄与队长的差不能超过 $k$。$q$ 次询问，若将 $x,y$ 安排在同一个小组，那么这个小组最多多少人。

题解

先预处理每个人当队长时小组最多有多少人。设这个值为 $cn{t}_i$。

具体来说，按 $r$ 排序，对于 $i$ 需要求前面 $i$ 个人有多少个人的年龄在 $[a_i-k,a_i+k]$ 的区间内。用一个动态开点权值线段树即可。下标是年龄。

考虑对询问离线。不妨假设 $r_x\le r_y$，那么对于一个询问 $i$，能够包含 $x_i,y_i$ 的队长的范围是 $r\ge r_{y_i},\max (a_{x_i},a_{y_i})-k\le a\le \min (a_{x_i},a_{y_i})+k$。因为与 $x,y$ 的年龄差要同时小于 $k$，所以选范围小的区间。

按 $r_y$ 为关键值将询问从大到小排序。然后一个动态开点权值线段树，下标是年龄，叶子节点存储 $cn{t}_i$。这样对于一个询问，只需要查找在 $[\max (a_{x_i},a_{y_i})-k,\min (a_{x_i},a_{y_i})+k]$ 区间内的最大值即可。

时间复杂度 $O(n\log w)$。

实现

记得判 -1。注意输入的标号是排序前的标号，要处理一下。

#include <bits/stdc++.h>
using namespace std;
const int N = 100005, W = 1e9;
int n, K, Q, ans[N], vp[N], cnt[N];
int tr[N << 4], mx[N << 4], rt1 = 0, rt2 = 0, tot1 = 0, tot2 = 0, ls1[N << 4], rs1[N << 4], ls2[N << 4], rs2[N << 4];
struct mem {int r, ag, id;bool operator< (const mem &T) const { return r < T.r; }
} a[N];
struct Query {int x, y, id;bool operator< (const Query &T) const { return a[y].r > a[T.y].r; }
} q[N];
void upd1(int &rt, int x, int y, int pos, int val) {if (!rt) rt = ++tot1;if (x == y) { tr[rt] += val; return; }int mid = x + y >> 1;if (pos <= mid) upd1(ls1[rt], x, mid, pos, val);else upd1(rs1[rt], mid + 1, y, pos, val);tr[rt] = tr[ls1[rt]] + tr[rs1[rt]];
}
int qry1(int rt, int x, int y, int l, int r) {if (l > y || r < x || !rt) return 0;if (l <= x && y <= r) return tr[rt];int mid = x + y >> 1;return qry1(ls1[rt], x, mid, l, r) + qry1(rs1[rt], mid + 1, y, l, r);
}
void upd2(int &rt, int x, int y, int pos, int val) {if (!rt) rt = ++tot2;if (x == y) { mx[rt] = max(mx[rt], val); return; }int mid = x + y >> 1;if (pos <= mid) upd2(ls2[rt], x, mid, pos, val);else upd2(rs2[rt], mid + 1, y, pos, val);mx[rt] = max(mx[ls2[rt]], mx[rs2[rt]]);
}
int qry2(int rt, int x, int y, int l, int r) {if (l > y || r < x || !rt) return 0;if (l <= x && y <= r) return mx[rt];int mid = x + y >> 1;return max(qry2(ls2[rt], x, mid, l, r), qry2(rs2[rt], mid + 1, y, l, r));
}
int main() {scanf("%d%d", &n, &K);for (int i = 1; i <= n; i++) scanf("%d", &a[i].r), a[i].id = i;for (int i = 1; i <= n; i++) scanf("%d", &a[i].ag);sort(a + 1, a + n + 1);for (int i = 1; i <= n; i++) vp[a[i].id] = i;for (int i = 1; i <= n; ) {int j = i;while (a[j].r == a[j + 1].r) upd1(rt1, 1, W, a[j].ag, 1), j++;upd1(rt1, 1, W, a[j].ag, 1);for (; i <= j; i++) cnt[i] = qry1(rt1, 1, W, a[i].ag - K, a[i].ag + K);}scanf("%d", &Q);for (int i = 1; i <= Q; i++) {scanf("%d%d", &q[i].x, &q[i].y), q[i].x = vp[q[i].x], q[i].y = vp[q[i].y], q[i].id = i;if (q[i].x > q[i].y) swap(q[i].x, q[i].y);}sort(q + 1, q + Q + 1);int k = n;for (int i = 1; i <= Q; i++) {while (q[i].y <= k) upd2(rt2, 1, W, a[k].ag, cnt[k]), k--;ans[q[i].id] = qry2(rt2, 1, W, max(a[q[i].x].ag, a[q[i].y].ag) - K, min(a[q[i].x].ag, a[q[i].y].ag) + K);if (ans[q[i].id] < 2) ans[q[i].id] = -1;}for (int i = 1; i <= Q; i++) printf("%d\n", ans[i]);return 0;
}