组队条件只看队长:预处理每人当队长时的最大组队人数,再把询问按地位阈值离线,用年龄离散化 + 线段树区间最大值回答。
OJ: roj
题目 ID: 1745
难度:提高+/省选-
标签:数据结构树状数组线段树离散化离线python
创建: 2026-10-07 21:03
更新: 2026-10-07 21:03
形式化题目
有
注意队长本人自然满足第二条(
约束:
关键是把"整个小组"从问题里消掉:小组是否合法,只由队长一个人决定。
给定队长
的人,这些条件互不干扰,所以"以
于是原问题变成:在满足"能同时容纳
第二条是两个年龄邻域的交集:
正解
思路
朴素做法。 对每个询问枚举所有可能的队长
第一步:把
这里有一个必须处理的细节:地位并列的人要整块插入后再统一查询。
如果把同地位的人一个一个"插入—查询",那么并列第一的队长就会漏数同地位的其他居民,
而题面明确允许并列第一当队长。做法是按
年龄值域到 lower_bound / upper_bound 转成坐标区间
第二步:把询问离线成区间最大值。 剩下的问题是对每个询问求
两个条件一个在地位上、一个在年龄上,直接做是二维查询。但注意到地位条件
start 为第一个满足 start 的那些人。
于是把询问按 start 降序排序,用一个指针从地位最高的人开始往回走,
边走边把
答案判定。 询问的答案小于
拿样例走一遍:
代码
Python 版:
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 21:03
# update_at: 2026-10-07 21:03
import sys
from bisect import bisect_left, bisect_right
# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Queries = list[tuple[int, int]] # 询问表,每项是一对 0 起的居民下标
def bit_add(bit: list[int], i: int, v: int) -> None:
"""Fenwick 单点加:把下标 i 上的计数加上 v(下标从 1 开始)。"""
while i < len(bit):
bit[i] += v
i += i & -i
def bit_sum(bit: list[int], i: int) -> int:
"""Fenwick 前缀和:统计年龄坐标落在 [1, i] 内的已插入人数。"""
total = 0
while i > 0:
total += bit[i]
i -= i & -i
return total
def leader_counts(order: list[int], rs: list[int], ages: list[int],
vals: list[int], k: int) -> list[int]:
"""cnt[u] = 以 u 当队长时小组的最大人数(地位不高于 u、年龄相差不超过 k 的人)。
按地位升序把人插入年龄树状数组,同地位的人必须整块插完再统一查询,
否则并列第一的队长会漏掉彼此(题面允许并列第一当队长)。
"""
n = len(ages)
pos = [bisect_left(vals, a) + 1 for a in ages] # 年龄 -> 离散坐标(1 起)
bit = [0] * (len(vals) + 1)
cnt = [0] * n
i = 0
while i < n:
j = i
while j < n and rs[order[j]] == rs[order[i]]:
bit_add(bit, pos[order[j]], 1) # 整块插入,保证同地位互相可见
j += 1
for t in range(i, j):
u = order[t]
lo = bisect_left(vals, ages[u] - k) + 1 # 第一个 >= a_u - k 的坐标
hi = bisect_right(vals, ages[u] + k) # 最后一个 <= a_u + k 的坐标
if lo <= hi:
cnt[u] = bit_sum(bit, hi) - bit_sum(bit, lo - 1)
else:
cnt[u] = 0 # 年龄区间里没有任何坐标
i = j
return cnt
def query_answers(cnt: list[int], order: list[int], rs: list[int], ages: list[int],
vals: list[int], queries: Queries, k: int) -> list[int]:
"""离线回答全部询问,返回按输入顺序排列的答案。
队长 L 合法当且仅当 r_L >= max(r_x, r_y) 且 a_L 同时落在两人的年龄邻域内,
此时答案就是 cnt[L];把询问按"队长最小排名"降序排序,指针从地位最高的人
往回扫,让线段树里的元素只增不减,区间查最大值即可。
"""
n = len(ages)
sorted_r = [rs[u] for u in order] # 按地位升序的地位序列
pos = [bisect_left(vals, a) for a in ages] # 线段树坐标从 0 起
size = 1
while size < len(vals):
size <<= 1
tree = [0] * (2 * size) # 下标为年龄坐标的最大值线段树
plan = [] # (队长最小排名, 年龄区间左端, 右端, 询问下标)
for qi, (x, y) in enumerate(queries):
start = bisect_left(sorted_r, max(rs[x], rs[y])) # 排名 >= start 才有资格
ql = bisect_left(vals, max(ages[x], ages[y]) - k) # 两个年龄邻域的交
qr = bisect_right(vals, min(ages[x], ages[y]) + k) - 1
plan.append((start, ql, qr, qi))
ans = [0] * len(queries)
p = n - 1
for start, ql, qr, qi in sorted(plan, reverse=True):
while p >= start:
u = order[p]
i = size + pos[u]
while i:
if cnt[u] > tree[i]: # 同一坐标可能被多个人写入,取较大者
tree[i] = cnt[u]
i >>= 1
p -= 1
best = 0
left, right = ql + size, qr + size + 1
while left < right: # 迭代式区间最大值
if left & 1:
best = max(best, tree[left])
left += 1
if right & 1:
right -= 1
best = max(best, tree[right])
left >>= 1
right >>= 1
# x、y 一定被合法队长计入,所以最大值小于 2 就说明没有合法队长
ans[qi] = best if best >= 2 else -1
return ans
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n, k = next(data), next(data)
rs = [next(data) for _ in range(n)]
ages = [next(data) for _ in range(n)]
q = next(data)
queries = [(next(data) - 1, next(data) - 1) for _ in range(q)]
order = sorted(range(n), key=rs.__getitem__) # 地位升序的居民下标
vals = sorted(set(ages)) # 年龄离散化取值表
cnt = leader_counts(order, rs, ages, vals, k)
ans = query_answers(cnt, order, rs, ages, vals, queries, k)
sys.stdout.write('\n'.join(map(str, ans)) + '\n')
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-07 21:03
* update_at: 2026-10-07 21:03
*/
// 一本通 1745《分组》
// 小组合法性只由队长决定:队长的 r 是全组最大(可并列),且全组每个人的年龄都落在
// [a_队长 - K, a_队长 + K] 内。于是分两步解决:
// 1) 预处理 cnt[i] = 以 i 当队长时小组的最大人数;
// 2) 询问 (x, y) 的队长必须满足 r >= max(r_x, r_y) 且年龄同时靠近两人,
// 把询问按"r 阈值"降序离线,用下标为年龄坐标的最大值线段树回答区间最大值。
// 复杂度 O((n + Q) log n)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 200005; // n 上限 1e5,按 2 倍安全系数开
const int MAXQ = 200005; // 询问数上限 1e5,同样按 2 倍开
int n, Q; // n = 居民数,Q = 询问数
ll K; // 组内成员与队长的年龄差距上限
// 一个居民:地位 r、年龄 a、年龄离散化坐标 agePos、当队长时的最大组队人数 cnt
struct Person {
ll r;
ll a;
int agePos;
int cnt;
};
Person p[MAXN]; // 按 r 升序排序后的居民序列,下标从 1 开始
// 原始编号 -> (地位, 年龄),离线处理询问时按编号查
struct Info {
ll r;
ll a;
};
Info info[MAXN]; // info[i] 就是第 i 号居民的原始数据
ll ageVal[MAXN]; // 年龄离散化后的取值表(升序去重),下标 1..m
int m; // 年龄的种数
int fen[MAXN]; // 树状数组:统计年龄坐标落在某个区间内的已插入人数
int seg[4 * MAXN];// 最大值线段树:下标是年龄坐标,存 cnt 的最大值
int ans[MAXQ]; // 每个询问的答案,最后按原顺序输出
// 在 ageVal[1..m] 里找第一个 >= v 的坐标(不存在返回 m+1)
int lower_idx(ll v) {
int lo = 1, hi = m, res = m + 1;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
if (ageVal[mid] >= v) {
res = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
return res;
}
// 在 ageVal[1..m] 里找最后一个 <= v 的坐标(不存在返回 0)
int upper_idx(ll v) {
int lo = 1, hi = m, res = 0;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
if (ageVal[mid] <= v) {
res = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return res;
}
// 找第一个满足 p[i].r >= need 的排名(不存在返回 n+1):
// 排名 >= 该值的人地位足够高,才有资格当队长
int first_rank(ll need) {
int lo = 1, hi = n, res = n + 1;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
if (p[mid].r >= need) {
res = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
return res;
}
// 树状数组单点加
void fen_add(int i, int v) {
for (; i <= m; i += i & -i) fen[i] += v;
}
// 树状数组前缀和
int fen_sum(int i) {
int s = 0;
for (; i > 0; i -= i & -i) s += fen[i];
return s;
}
// 线段树单点取最大值
void seg_update(int o, int l, int r, int pos, int val) {
if (l == r) {
if (val > seg[o]) seg[o] = val;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) {
seg_update(o << 1, l, mid, pos, val);
} else {
seg_update(o << 1 | 1, mid + 1, r, pos, val);
}
seg[o] = max(seg[o << 1], seg[o << 1 | 1]);
}
// 线段树区间最大值查询,区间为空时返回 0
int seg_query(int o, int l, int r, int ql, int qr) {
if (ql > r || qr < l) return 0;
if (ql <= l && r <= qr) return seg[o];
int mid = (l + r) >> 1;
return max(seg_query(o << 1, l, mid, ql, qr), seg_query(o << 1 | 1, mid + 1, r, ql, qr));
}
// 居民按地位升序,便于用"排名 >= start"表达"地位不低于 need"
bool cmpPerson(const Person &x, const Person &y) {
return x.r < y.r;
}
// 询问按队长最小排名降序,好让线段树里的元素只增不减
struct Query {
int start; // 队长最小排名
int ql; // 队长年龄区间左端(离散化坐标)
int qr; // 队长年龄区间右端(离散化坐标)
int id; // 原询问编号
};
Query qs[MAXQ];
bool cmpQuery(const Query &x, const Query &y) {
return x.start > y.start;
}
int main() {
if (scanf("%d%lld", &n, &K) != 2) return 0;
for (int i = 1; i <= n; ++i) scanf("%lld", &p[i].r);
for (int i = 1; i <= n; ++i) scanf("%lld", &p[i].a);
for (int i = 1; i <= n; ++i) {
info[i].r = p[i].r;
info[i].a = p[i].a;
}
// 年龄离散化:值域 1e9 但只有 n 个不同取值
sort(p + 1, p + n + 1, cmpPerson);
for (int i = 1; i <= n; ++i) ageVal[i] = p[i].a;
sort(ageVal + 1, ageVal + n + 1);
m = 1;
for (int i = 2; i <= n; ++i) {
if (ageVal[i] != ageVal[m]) ageVal[++m] = ageVal[i];
}
for (int i = 1; i <= n; ++i) p[i].agePos = lower_idx(p[i].a);
// 预处理 cnt[i]:先按 r 分块,同 r 的人整块插入后再统一查询,
// 这样 r 并列的人也能互相计入(并列第一同样可以当队长)
for (int i = 1; i <= n;) {
int j = i;
while (j <= n && p[j].r == p[i].r) {
fen_add(p[j].agePos, 1);
++j;
}
for (int t = i; t < j; ++t) {
int lo = lower_idx(p[t].a - K);
int hi = upper_idx(p[t].a + K);
p[t].cnt = (lo > hi) ? 0 : fen_sum(hi) - fen_sum(lo - 1);
}
i = j;
}
scanf("%d", &Q);
for (int i = 1; i <= Q; ++i) {
int x, y;
scanf("%d%d", &x, &y);
// 队长的年龄必须同时满足 |a_队长 - a_x| <= K 和 |a_队长 - a_y| <= K,
// 两个区间的交集就是下面这段
qs[i].start = first_rank(max(info[x].r, info[y].r));
qs[i].ql = lower_idx(max(info[x].a, info[y].a) - K);
qs[i].qr = upper_idx(min(info[x].a, info[y].a) + K);
qs[i].id = i;
}
sort(qs + 1, qs + Q + 1, cmpQuery);
int k = n; // 排名 (k, n] 的人已经进入线段树
for (int i = 1; i <= Q; ++i) {
while (k >= qs[i].start) {
seg_update(1, 1, m, p[k].agePos, p[k].cnt);
--k;
}
int lo = max(qs[i].ql, 1);
int hi = min(qs[i].qr, m);
int best = (lo <= hi) ? seg_query(1, 1, m, lo, hi) : 0;
// x、y 自己一定被合法队长计入,所以小于 2 就是无解
ans[qs[i].id] = (best < 2) ? -1 : best;
}
for (int i = 1; i <= Q; ++i) printf("%d\n", ans[i]);
return 0;
}复杂度
- 时间:排序与离散化
;预处理 时每个人被插入一次、 查询两次前缀和, ;询问排序 ,线段树单点更新 次、 区间查询 次,各 。总计 , 时约 次基本操作。实测 C++ 在最大点(problem10, )上约 0.10 s,远低于 1000 ms 限时。 - 空间:离散化后的年龄表、树状数组、线段树、询问数组都是
, 线段树 个 int约 0.8 MB,C++ 实测峰值约 11 MB,远低于 256 MB 限时。 - 与 Python 的关系:
main.py与main.cpp是同一算法(树状数组 + 离线线段树), 没有降级成暴力。Python 侧同样受约束,实测最大点约 0.63–0.68 s, 仍在 1000 ms 内,但余量比 C++ 小得多;若评测机比本地慢,存在 TLE 风险。 算法复杂度与 C++ 一致,不存在"Python 用暴力蒙过"的情况。
总结
- 先化简合法性条件:小组是否合法只取决于队长一个人,组员之间没有约束。 这一步把"枚举子集"的指数结构直接换成了"数点数",是本题的分水岭。
- 二维数点用"排序 + 一维树状数组":按地位升序插入、用年龄当树状数组下标, 就得到了每个前缀地位上的年龄分布。同地位的人必须整块插入再统一查询, 否则并列第一的队长会漏数同伴——这是本题最容易写错的一处。
- 离线 + 单调指针消除一维:把询问按地位阈值降序排,指针从高到低单向推进,
线段树里的元素只增不减,"地位
need"这个后缀条件就消失了, 剩下的只有年龄区间求最大值。 - 值域大就要离散化:
但只有 个不同取值, 离散化后线段树和树状数组的下标规模都是 。 - 答案
即无解: 一旦有共同队长就必然被计入,所以判无解不需要额外逻辑。 - 数据来源说明:本题素材目录里带有数据生成脚本
data.py(基于 cyaron), 说明仓库内的data/是自造数据而非官方原题数据;题面文字也属于网络重建。 因此出题意图与官方原题(同源题目见 JZOJ 3854 / Codeforces 173E “Camping Groups”) 可能存在偏差,本文的结论仅对仓库内这套数据负责。素材自带的std.cpp已实测编译后 与 10 组.out全部一致,且与本文两份代码在随机对拍中输出相同,可以互相印证。 - 本题验证记录:题面样例 1 组(4 个询问)C++ 与 Python 输出均为
4 3 -1 4, 与期望完全一致;真实数据 10 组.out逐点 diff 全部 PASS(C++ 最大点 0.10 s、 Python 最大点 0.63 s);与朴素暴力在 1200 组以上随机小数据 ( ,含 、值域退化到 1 种取值、地位与年龄大量并列等边界) 上 C++ 与 Python 均无差异。