分组

GitHub跳转原题关系图返回列表

组队条件只看队长:预处理每人当队长时的最大组队人数,再把询问按地位阈值离线,用年龄离散化 + 线段树区间最大值回答。

OJ: roj

题目 ID: 1745

难度:提高+/省选-

标签:数据结构树状数组线段树离散化离线python

创建: 2026-10-07 21:03

更新: 2026-10-07 21:03

形式化题目

有 nn 个居民,第 ii 个人有地位 rir_i 和年龄 aia_i。一个小组 SS 合法,当且仅当存在 队长 L∈SL \in S 满足

rj⩽rL    (∀j∈S),∣aj−aL∣⩽K    (∀j∈S). r_j \leqslant r_L \;\; (\forall j \in S), \qquad |a_j - a_L| \leqslant K \;\; (\forall j \in S).

注意队长本人自然满足第二条(∣aL−aL∣=0⩽K|a_L - a_L| = 0 \leqslant K),第一条允许并列第一。 给出 QQ 个询问,每个询问给两个不同的居民 x,yx, y,求同时包含 xx 与 yy 的合法小组 的最大大小 ∣S∣|S|;不存在这样的小组时输出 −1-1。

约束:2⩽n⩽1052 \leqslant n \leqslant 10^5,0⩽K⩽1090 \leqslant K \leqslant 10^9, 1⩽ri,ai⩽1091 \leqslant r_i, a_i \leqslant 10^9,1⩽Q⩽1051 \leqslant Q \leqslant 10^5,1⩽x,y⩽n1 \leqslant x, y \leqslant n,x≠yx \neq y。

关键是把"整个小组"从问题里消掉:小组是否合法,只由队长一个人决定。 给定队长 LL,能和他同组的人恰好是那些

rj⩽rL且∣aj−aL∣⩽K r_j \leqslant r_L \quad \text{且} \quad |a_j - a_L| \leqslant K

的人,这些条件互不干扰,所以"以 LL 为队长"的小组最大人数可以直接数出来:

cnt[L]=#{ j:rj⩽rL,  aL−K⩽aj⩽aL+K }. \mathrm{cnt}[L] = \#\{\, j : r_j \leqslant r_L,\; a_L - K \leqslant a_j \leqslant a_L + K \,\}.

于是原问题变成:在满足"能同时容纳 xx 与 yy"的队长里,找 cnt\mathrm{cnt} 最大的那个。 队长 LL 能容纳 xx 与 yy 的充要条件是

rL⩾max⁡(rx,ry),aL∈[max⁡(ax,ay)−K,  min⁡(ax,ay)+K]. r_L \geqslant \max(r_x, r_y), \qquad a_L \in [\max(a_x, a_y) - K,\; \min(a_x, a_y) + K].

第二条是两个年龄邻域的交集:aLa_L 必须同时靠近 xx 和 yy,而这个交集非空当且仅当 ∣ax−ay∣⩽2K|a_x - a_y| \leqslant 2K——这也解释了样例里 x=2,y=5x = 2, y = 5 为什么输出 −1-1。

正解

思路

朴素做法。 对每个询问枚举所有可能的队长 LL,再花 O(n)O(n) 数一遍 cnt[L]\mathrm{cnt}[L],总复杂度 O(Qn2)O(Q n^2),n=Q=105n = Q = 10^5 时不可行。瓶颈有两处: cnt\mathrm{cnt} 被反复重算,以及队长的筛选条件带着一个二维约束(地位一维、年龄一维)。

第一步:把 cnt\mathrm{cnt} 一次算完。 数 cnt[L]\mathrm{cnt}[L] 就是"统计地位不超过 rLr_L、年龄落在一个区间内的人数",这是典型的二维数点。固定 LL 时年龄是一段区间, 所以按地位升序把人依次插入一棵下标为年龄的树状数组,插入完第 kk 个人之后, 树状数组里正好是"地位排名 ⩽k\leqslant k"的全部人,此时对 LL 查询年龄区间和即可。

这里有一个必须处理的细节:地位并列的人要整块插入后再统一查询。 如果把同地位的人一个一个"插入—查询",那么并列第一的队长就会漏数同地位的其他居民, 而题面明确允许并列第一当队长。做法是按 rr 分组,一组人全部插入后才对本组每个人查询。

年龄值域到 10910^9,但只有 nn 个不同取值,先离散化到 1..m1..m(m⩽nm \leqslant n)。 查询区间 [aL−K,aL+K][a_L - K, a_L + K] 用 lower_bound / upper_bound 转成坐标区间 [lo,hi][\mathrm{lo}, \mathrm{hi}],答案就是前缀和之差。

第二步:把询问离线成区间最大值。 剩下的问题是对每个询问求

max⁡{ cnt[L]  :  rL⩾max⁡(rx,ry),    aL∈[ql,qr] }. \max \{\, \mathrm{cnt}[L] \;:\; r_L \geqslant \max(r_x, r_y),\;\; a_L \in [\mathrm{ql}, \mathrm{qr}] \,\}.

两个条件一个在地位上、一个在年龄上,直接做是二维查询。但注意到地位条件 rL⩾needr_L \geqslant \text{need} 只是把候选人截成"排名 ⩾\geqslant start 的后缀": 把人按 rr 升序排好后,取 start 为第一个满足 r⩾needr \geqslant \text{need} 的排名, 合法队长恰好是排名 ⩾\geqslant start 的那些人。

于是把询问按 start 降序排序,用一个指针从地位最高的人开始往回走, 边走边把 cnt\mathrm{cnt} 插入一棵下标为年龄坐标的最大值线段树。 指针只降不升,线段树里的元素只增不减,所以每个询问只需一次区间查最大值, 总代价 O((n+Q)log⁡n)O((n + Q) \log n)。这正是"离线 + 单调指针把二维问题降成一维"的标准套路。

答案判定。 询问的答案小于 22 就输出 −1-1。理由是:只要 xx 与 yy 存在共同的合法队长, 那么 xx 和 yy 自己都会被这个队长计入 cnt\mathrm{cnt}(队长地位够高、年龄也够近), 所以最大值至少是 22;反过来最大值为 00 或 11 说明没有任何队长能同时容纳两人。

拿样例走一遍:n=5n = 5,K=1K = 1,r=(1,5,4,1,2)r = (1,5,4,1,2),a=(4,4,3,2,2)a = (4,4,3,2,2)。 按地位排序后是 1(4), 4(2), 5(2), 3(3), 2(4)1(4),\,4(2),\,5(2),\,3(3),\,2(4)(括号里是年龄)。 第 3 个人(原编号 3,r=4r = 4,a=3a = 3)当队长时,地位不超过他的人有 1,4,5,31, 4, 5, 3,其中年龄落在 [2,4][2,4] 的正是这四个,所以 cnt=4\mathrm{cnt} = 4。 询问 (5,3)(5, 3) 要求 rL⩾max⁡(2,4)=4r_L \geqslant \max(2,4) = 4、aL∈[max⁡(2,3)−1,min⁡(2,3)+1]=[2,4]a_L \in [\max(2,3) - 1, \min(2,3) + 1] = [2, 4], 队长 3(cnt=4\mathrm{cnt} = 4)满足条件,答案 44,与样例一致。 询问 (2,5)(2,5) 要求 aL∈[max⁡(4,2)−1,min⁡(4,2)+1]=[3,3]a_L \in [\max(4,2) - 1, \min(4,2) + 1] = [3, 3], 只有 a=3a = 3 的队长 3 可以,但它不满足 rL⩾max⁡(5,2)=5r_L \geqslant \max(5, 2) = 5, 区间里没有合法队长,输出 −1-1。

代码

Python 版:

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++ 版(同一算法):

cpp
/**
 * 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;
}

复杂度

  • 时间:排序与离散化 O(nlog⁡n)O(n \log n);预处理 cnt\mathrm{cnt} 时每个人被插入一次、 查询两次前缀和,O(nlog⁡n)O(n \log n);询问排序 O(Qlog⁡Q)O(Q \log Q),线段树单点更新 nn 次、 区间查询 QQ 次,各 O(log⁡n)O(\log n)。总计 O((n+Q)log⁡n)O((n + Q) \log n), n=Q=105n = Q = 10^5 时约 3×1063 \times 10^6 次基本操作。实测 C++ 在最大点(problem10, n=Q=105n = Q = 10^5)上约 0.10 s,远低于 1000 ms 限时。
  • 空间:离散化后的年龄表、树状数组、线段树、询问数组都是 O(n+Q)O(n + Q), 线段树 4n4n 个 int 约 0.8 MB,C++ 实测峰值约 11 MB,远低于 256 MB 限时。
  • 与 Python 的关系:main.py 与 main.cpp 是同一算法(树状数组 + 离线线段树), 没有降级成暴力。Python 侧同样受 O((n+Q)log⁡n)O((n + Q) \log n) 约束,实测最大点约 0.63–0.68 s, 仍在 1000 ms 内,但余量比 C++ 小得多;若评测机比本地慢,存在 TLE 风险。 算法复杂度与 C++ 一致,不存在"Python 用暴力蒙过"的情况。

总结

  • 先化简合法性条件:小组是否合法只取决于队长一个人,组员之间没有约束。 这一步把"枚举子集"的指数结构直接换成了"数点数",是本题的分水岭。
  • 二维数点用"排序 + 一维树状数组":按地位升序插入、用年龄当树状数组下标, 就得到了每个前缀地位上的年龄分布。同地位的人必须整块插入再统一查询, 否则并列第一的队长会漏数同伴——这是本题最容易写错的一处。
  • 离线 + 单调指针消除一维:把询问按地位阈值降序排,指针从高到低单向推进, 线段树里的元素只增不减,"地位 ⩾\geqslant need"这个后缀条件就消失了, 剩下的只有年龄区间求最大值。
  • 值域大就要离散化:ai⩽109a_i \leqslant 10^9 但只有 nn 个不同取值, 离散化后线段树和树状数组的下标规模都是 O(n)O(n)。
  • 答案 <2< 2 即无解:x,yx, y 一旦有共同队长就必然被计入,所以判无解不需要额外逻辑。
  • 数据来源说明:本题素材目录里带有数据生成脚本 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);与朴素 O(Qn2)O(Qn^2) 暴力在 1200 组以上随机小数据 (n⩽60n \leqslant 60,含 K=0K = 0、值域退化到 1 种取值、地位与年龄大量并列等边界) 上 C++ 与 Python 均无差异。