30 · 回顾六：BFS、二分与容器

把格子看成点，相邻且数字不同就连一条边。「数字不同」是对称的，所以这是一张无向图。

询问「从 (i,j) 能走到多少格」等价于求 (i,j) 所在连通块的大小。

同一连通块里任意两点可达集合相同，块内一点也走不到块外，所以块内所有格子的答案都等于块大小。

于是每个块只 BFS 一次：数出块大小，再把大小写回块内所有格子。之后每个询问 O(1) 查表。

实现上让 ans 数组兼作访问标记：0 = 没处理，−1 = 已入队、大小待定，正数 = 块大小。

复杂度 O(n² + m)：每格只入队一次，询问只查表。若每个询问单独 BFS，最坏 10⁵ × 10⁶ = 10¹¹，必 TLE。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
int n, m;
char g[MAXN][MAXN];            // g[i][j]：'0' 或 '1'，行列从 1 开始
int ans[MAXN][MAXN];           // 0 = 未处理，-1 = 已入队待定，正数 = 块大小
int cells[MAXN * MAXN];        // 当前块内的格子，压成 i * MAXN + j
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

// 把 (sx, sy) 所在的整个连通块算完，并把块大小写回块内每一格
void fill_block(int sx, int sy) {
    queue<pair<int,int>> q;
    q.push({sx, sy});
    ans[sx][sy] = -1;          // 入队就标记，不能等出队

    int cnt = 0;
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        cells[cnt++] = x * MAXN + y;       // 记下块内格子，等会儿统一回填
        for (int d = 0; d < 4; ++d) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 1 || nx > n || ny < 1 || ny > n) continue;
            if (ans[nx][ny] != 0) continue;            // 已属于某个块
            if (g[nx][ny] == g[x][y]) continue;        // 只能走到数字不同的格
            ans[nx][ny] = -1;
            q.push({nx, ny});
        }
    }
    for (int k = 0; k < cnt; ++k)                  // 同块同答案
        ans[cells[k] / MAXN][cells[k] % MAXN] = cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) cin >> g[i][j];   // 读 char 会自动跳过换行

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (ans[i][j] == 0) fill_block(i, j);      // 每块只算一次

    while (m--) {
        int i, j;
        cin >> i >> j;
        cout << ans[i][j] << "\n";                     // 询问退化成查表
    }
    return 0;
}

check(H)：Σ max(0, hᵢ − H) ≥ M。H 越大能锯到的越少，check 单调（真…真假…假）。

要的是最后一个 check 为真的 H，于是用「上取整 mid + 可行则 l = mid」那一套。

上界取 mx = max(hᵢ)（再高就一棵也锯不到），下界 0（题目保证总和 > M，H = 0 一定可行）。

check 里的 sum 必须 long long：10⁶ 棵 4×10⁵ 的树，总量 4×10¹¹，int 直接溢出。

复杂度 O(N log mx) ≈ 10⁶ × 19 ≈ 2×10⁷ 次运算，1 秒内稳过。

边界提醒：答案可能是 0（树都很矮），也可能是 mx，所以 l、r 的初值必须覆盖这两端。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;
int n, h[MAXN];
long long need;              // M 到 2×10⁹，用 int 比较会溢出

// 锯片高度为 H 时，得到的木材是否够 M 米
bool check(int H) {
    long long sum = 0;
    for (int i = 1; i <= n; ++i) {
        if (h[i] > H) {
            sum += h[i] - H;
            if (sum >= need) return true;   // 够了就提前退出
        }
    }
    return false;
}

int main() {
    scanf("%d%lld", &n, &need);

    int mx = 0;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &h[i]);
        if (h[i] > mx) mx = h[i];
    }

    int l = 0, r = mx;                      // 答案一定在 [0, 最高的树] 内
    while (l < r) {
        int mid = l + (r - l + 1) / 2;      // 上取整：求最大值必须这么写
        if (check(mid)) l = mid;            // mid 可行，答案不小于 mid
        else            r = mid - 1;        // mid 不可行，答案更小
    }
    printf("%d\n", l);
    return 0;
}

check(X)：从左往右贪心累加，能装就装，装不下就开新段，数出最少段数 cnt。

cnt ≤ M 说明 X 可行——段数不够可以把某段再切开，段数只会更多，而上限仍是 X。

段数随 X 单调不增，所以「最小可行 X」可以二分，用「下取整 mid + 可行则 r = mid」那一套。

下界必须取 max(Aᵢ)：否则 X 比某个数还小时，check 会把「单个元素已超限」的段也当成一段，二分会输出一个装不下的假答案。例：A = 10 1 1、M = 3，正确答案 10，下界取 1 会输出 2。

上界取总和 ΣAᵢ（只分一段），10⁵ × 10⁸ = 10¹³，必须 long long。

复杂度 O(N log ΣA) ≈ 10⁵ × 44，稳过。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
int n, m, a[MAXN];

// 每段和不超过 X 时，最少要分成几段
bool check(long long X) {
    int cnt = 1;                 // 至少一段
    long long sum = 0;           // 当前段的和
    for (int i = 1; i <= n; ++i) {
        if (sum + a[i] <= X) {
            sum += a[i];         // 能装就装：段数越少越容易满足 cnt <= m
        } else {
            ++cnt;               // 装不下，开新段
            sum = a[i];
        }
    }
    return cnt <= m;
}

int main() {
    scanf("%d%d", &n, &m);

    long long l = 0, r = 0;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        if (a[i] > l) l = a[i];  // 下界：最大的那个数
        r += a[i];               // 上界：全部装进一段
    }

    while (l < r) {
        long long mid = l + (r - l) / 2;
        if (check(mid)) r = mid;        // X 够大，试试更小
        else            l = mid + 1;    // X 太小，段数超了
    }
    printf("%lld\n", l);
    return 0;
}

贪心：每次取当前最小的两堆合并。

论证：把合并过程画成一棵二叉树，叶子是原堆。某堆被计入答案的次数等于它在树中的深度，深度大的位置应该放小重量——所以最小的两堆适合做最深的兄弟。

交换论证：若最深的两个兄弟不是当前最小的两堆，把最小的两堆换到那两个位置上，总和不会变大。所以第一步合并最小的两堆一定不亏，合并出的新堆继续参与同样的问题。

实现：小根堆，重复 n − 1 次「弹两个、累加、压回」。每次两个 pop 一个 push，共 O(n log n)。

n = 1 时不进入循环，答案 0——循环条件写 size() > 1 自动处理。

答案上限是「总和 × 合并次数」量级，用 long long 一劳永逸（题目保证 < 2³¹，但别省这个类型）。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);

    // 小根堆：top() 是当前最小的那一堆
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = 0; i < n; ++i) {
        int x;
        scanf("%d", &x);
        pq.push(x);
    }

    long long ans = 0;
    while (pq.size() > 1) {
        int a = pq.top(); pq.pop();      // 最小
        int b = pq.top(); pq.pop();      // 次小
        ans += a + b;                    // 本次合并的代价
        pq.push(a + b);                  // 新堆放回去，继续参与
    }
    printf("%lld\n", ans);
    return 0;
}

把所有乘客按到达顺序排进一个队列，每个元素存 (到达时刻, 国籍)。船与人的层级被压平。

维护 cnt[c] = 窗口内国籍 c 的人数，以及 ans = 窗口内不同国籍数。

一艘船到达：先把它的 kᵢ 个乘客逐个入队并更新 cnt（从 0 到 1 时 ans++）。

再把队头所有「到达时刻 ≤ tᵢ − 86400」的乘客弹出，弹出时 cnt−−，减到 0 时 ans−−。

为什么用 queue：时间递增，过期的永远在队头，且不会有人「重新进来」。每个乘客进队一次、出队一次。

复杂度 O(Σkᵢ) = 3×10⁵ 次操作。若每艘船都把窗口内的乘客重扫一遍，是 O(n·Σkᵢ)，必 TLE。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
int cnt[MAXN];                 // cnt[c]：窗口内国籍 c 的乘客数

int main() {
    int n;
    scanf("%d", &n);

    queue<pair<int,int>> q;    // (到达时刻, 国籍)，按时间排队
    int ans = 0;               // 窗口内不同国籍数

    for (int i = 0; i < n; ++i) {
        int t, k;
        scanf("%d%d", &t, &k);
        for (int j = 0; j < k; ++j) {
            int c;
            scanf("%d", &c);
            q.push({t, c});            // 同一艘船的人分享同一个到达时刻
            if (cnt[c] == 0) ++ans;    // 这个国家在窗口里从无到有
            ++cnt[c];
        }
        // 队伍左端：超过 24 小时的人出队
        while (!q.empty() && q.front().first <= t - 86400) {
            int c = q.front().second;
            q.pop();
            --cnt[c];
            if (cnt[c] == 0) --ans;    // 这个国家在窗口里彻底消失
        }
        printf("%d\n", ans);
    }
    return 0;
}