【题解】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 
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;
}
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