8.11

今天主要是把几个算法融合在一起考，有两道题在考场上没想到~~（感觉自己变唐了）~~

T1 Alyona and Spreadsheet

题意

给定一个 n 行 m 列的整数矩阵$（1 ≤ n·m ≤ 100000，1 ≤ a[i][j] ≤ 10^9）$。

定义第 j 列是非递减的，当且仅当 a[i][j] ≤ a[i+1][j] 对所有 i 成立。

有 k 次询问（1 ≤ k ≤ 100000），每次给出 l, r（1 ≤ l ≤ r ≤ n），问：保留第 l 到 r 行、删去其余行后，是否存在至少一列是非递减的？存在输出 "Yes"，否则输出 "No"。

思路

核心：预处理 + $O(1)$ 查询。

对每一列 j 从上往下扫描，维护一个变量 start，表示当前列中「以第 i 行结尾的非递减段」的起始行号：

• 若 a[i][j] ≥ a[i-1][j]，则 start 不变（非递减段继续延伸）；
• 否则 start = i（非递减段从这里重新开始）。

令 pre[i] = 所有列中、以第 i 行结尾的非递减段的最早起点，即 pre[i] = min_{j} start_j(i)。

查询 (l, r)： 只需判断 pre[r] <= l。因为 pre[r] 表示存在某一列，该列从第 pre[r] 行到第 r 行是非递减的；若 pre[r] <= l，则区间 [l, r] 完全包含在该非递减段内，故 [l, r] 在该列上也是非递减的，输出 "Yes"，否则 "No"。

复杂度： 预处理 $O(n·m)$，查询 $O(1)$，总 $O(n·m + k)$。

关键点

• 约束是 n·m ≤ 100000 而非分别限制，因此用 vector <vector <int>> 按需开空间即可。
• 查询只与右端点 r 有关，因为预处理已经把「以 r 结尾的最长非递减段起点」压缩进 pre[r]。

代码

#include <bits/stdc++.h>
using namespace std;
int main () {
	int n, m;
    scanf ("%d%d", &n, &m);
    vector <vector <int> > a (n + 1, vector <int> (m + 1));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) scanf ("%d", &a[i][j]);
    }
    vector <int> pre (n + 1, n + 1);
    // pre[i]:以第i行结尾，所有列中能向上延伸到的最早起点
    for (int j = 1; j <= m; j++) {
        int start = 1;
        for (int i = 1; i <= n; i++) {
            if (i > 1 && a[i][j] < a[i - 1][j]) start = i;
            pre[i] = min (pre[i], start);
        }
    }
    int k;
    scanf ("%d", &k);
    while (k--) {
        int l, r;
        scanf ("%d%d", &l, &r);
        // pre[r] <= l:有一段的非递减序列延伸到了r，且覆盖了[l,r]
        if (pre[r] <= l) puts ("Yes");
        else puts ("No");
   }
	return 0;
}

T2 Valiant and Panvel

题意

给定一个 n×m 的网格，每个格子 (i,j) 有一栋高度为 a[i][j] 的建筑。

要求在其中选择一个 l*l 的正方形区域，使得区域内**每栋建筑的高度都 **≥ l。

求最大的 l。

思路

二分答案 + DP 判定

单调性： 若存在 l*l 的正方形满足条件，则 l-1 也一定满足（取该正方形的任意 l-1 子正方形即可，因为高度 ≥ l > l-1）。所以答案具有单调性，可以二分。

二分范围： l ∈ [1, n]（因为 n ≤ m，正方形边长不超过较短边 n）。

判定函数 check(mid)： 是否存在 mid×mid 的正方形，其中所有格子高度 ≥ mid？

把矩阵二值化：b[i][j]。 若 a[i][j] ≥ mid，则将b[i][j]记为1，代表这个格子"合格"，否则 0。问题转化为「求全1正方形的最大边长」。

用经典 DP：

• dp[i][j] = 以 (i,j) 为右下角的全1正方形最大边长
• 若 b[i][j]=1：dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
• 若 b[i][j]=0：dp[i][j] = 0

若存在 dp[i][j] ≥ mid，则 mid 可行。

复杂度

• 二分：O(log n) 次
• 每次 check：O(n·m)
• 总计：O(n·m·log n)，所有测试用例之和 $≤ 10^6$，$log n ≤ 20$，约 $2×10^7$ 次操作，可以过。

关键点

• 单调性是二分的前提：l 可行 ⇒ l-1 也可行。
• check 用「最大全1正方形」DP，$O(n·m)$ 内完成。
• 题目保证 n ≤ m，所以二分上界直接取 n。
• 发现 dp[i][j] ≥ mid 即可提前 break，节省时间。

代码

#include <bits/stdc++.h>
using namespace std;
int check (int mid, int n, int m, vector <vector <int> >& a) {
	bool ok = false;
	vector <vector <int> > dp (n + 1, vector <int> (m + 1, 0));
    for (int i = 1; i <= n && !ok; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j] >= mid) {
                dp[i][j] = min (dp[i - 1][j], min (dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                if (dp[i][j] >= mid) {
                    ok = true;
                    break;
                }
            }
        }
    }
    if (ok) return true;
    return false;
}
int main () {
	int T;
    scanf ("%d", &T);
    while (T--) {
        int n, m;
        scanf ("%d%d", &n, &m);
        vector <vector <int> > a (n + 1, vector <int> (m + 1));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) scanf ("%d", &a[i][j]);
        }
        int l = 1, r = n;
        while (l < r) {
            int mid = (l + r + 1) / 2;
            if (check (mid, n , m, a)) l = mid;
            else r = mid - 1;
        }
        printf ("%d\n", l);
    }
	return 0;
}

T3 To Become Max

题意

给定长度为 n 的数组 a。一次操作：选择下标 $i（1 ≤ i ≤ n-1）$且 $a[i] ≤ a[i+1]$，将 a[i] 加 1。

最多进行 k 次操作，求 $max(a_1, a_2, ..., a_n)$ 的最大可能值。

思路

二分答案 + 贪心判定

单调性： 若能通过 ≤ k 次操作让某个元素达到 x，则 x-1 也一定能达到（少操作一次即可）。所以答案具有单调性，可以二分。

二分范围： [maxA, maxA + k]，其中 maxA = max(a)。不操作时答案就是 maxA；最多 k 次操作每次让一个元素 +1，上界不超过 maxA + k。

判定函数 check(x)： 能否让某个 a[i] 达到 x？

关键观察：要让 a[i] 达到 x，操作时需要 a[i] ≤ a[i+1]，所以 a[i] 最多能被加到 a[i+1]+1。若 a[i+1] 不够大，需要先提升 a[i+1]。以此类推：

• 位置 i 需要达到 x
• 位置 i+1 需要达到 x-1（这样 a[i] 才能被操作到 x）
• 位置 i+2 需要达到 x-2
• ...
• 位置 i+j 需要达到 x-j

从 i 往右扫描，维护 need（当前位置需要达到的值，初始为 x）：

• 若 a[j] ≥ need：位置 j 已足够，停止扫描（更右的位置 need 更小，更易满足）
• 若 a[j] < need：需要把 a[j] 提到 need，操作数 += need - a[j]，然后 need -= 1
• 特判： 若 j == n（最后一个元素）且 a[j] < need，则失败——最后一个元素没有右邻，不能被操作

若存在某个起点 i 使得总操作数 ≤ k，则 x 可行。

复杂度

• 二分：$O(log(maxA + k))$ ≈ $O(28)$ 次
• 每次 check：$O(n²)$（枚举起点 i，往右扫描）
• 总计：$O(n²·log)$，n ≤ 1000，约 $2.8×10^7$，可以过

关键点

• 最后一个元素不能被操作（没有 a[n+1]），这是判定失败的关键边界。
• 要让 a[i] 达到 x，只需 a[i+1] ≥ x-1（而非 x），因为 a[i] ≤ a[i+1] 时能 +1 到 a[i+1]+1... 实际上 a[i] 能加到 a[i+1]+1，所以 a[i+1] ≥ x-1 即可让 a[i] 达到 x。因此 need 每往右一位减 1。
• 遇到 a[j] ≥ need 即可提前停止，无需扫到底。
• cost 可能很大（达 $2×10^{11}$），需用 long long。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool check (int x, int n, int k, vector <int>& a) {
    for (int i = 1; i <= n; i++) {
        int need = x;
        ll cost = 0;
        bool ok = true;
        for (int j = i; j <= n; j++) {
            if (need <= 0) break;
            if (a[j] >= need) break;
            if (j == n) {
                ok = false;
                break;
            }
            cost += need - a[j];
            need --;
        }
        if (ok && cost <= k) return true;
    }
    return false;
}
int main () {
	int T;
    scanf ("%d", &T);
    while (T--) {
        int n, k;
        scanf ("%d%d", &n, &k);
        vector <int> a (n + 1);
        int maxa = 0;
        for (int i = 1; i <= n; i++) {
            scanf ("%d", &a[i]);
            maxa = max (maxa, a[i]);
        }
        int l = maxa, r = maxa + k;
        while (l < r) {
            int mid = (l + r + 1) / 2;
            if (check (mid, n, k, a)) l = mid;
            else r = mid - 1;
        }
        printf ("%d\n", l);
    }
	return 0;
}

T4 Rudolf and the River

题意

河流为 n 行 m 列的网格，第 i 行第 j 列的深度为 a[i][j]，其中第一列和最后一列深度为 0（河岸）。

要在连续 k 行各建一座桥。每座桥在某一行 i 上，从 (i,1) 到 (i,m) 安装支撑柱：

• 支撑柱成本 = a[i][j] + 1
• (i,1) 和 (i,m) 必须安装支撑柱
• 相邻两个支撑柱 (i,j1) 和 (i,j2) 的距离 |j1-j2|-1 不能超过 d

求 k 座桥的最小总成本。

思路

第一步：每行建桥的最小成本（DP + 单调队列）

对单行，设 dp[j] = 在第 j 列放支撑柱时的最小总成本。

• dp[1] = a[1] + 1 = 1（第 1 列必须放）
• dp[j] = a[j] + 1 + min(dp[l])，其中 l ∈ [j-d-1, j-1]

  - 距离约束：|j - l| - 1 ≤ d ⇒ l ≥ j - d - 1

这是一个滑动窗口最小值问题，用单调队列维护窗口 [j-d-1, j-1] 内 dp 的最小值，每次 $O(1)$ 取队首。

单行复杂度 $O(m)$。

第二步：连续 k 行的最小和（滑动窗口）

算出每行成本 cost[1..n] 后，求长度为 k 的连续子数组和的最小值。

用滑动窗口维护窗口内和，O(n)。

总复杂度

O(n·m) 每个测试用例，所有测试用例之和 $≤ 2×10^5$，可接受。

关键点

• 距离定义：|j1-j2|-1 ≤ d，所以前一个支撑柱位置 l ≥ j-d-1，窗口大小为 d+1。
• 单调队列维护滑动窗口最小值，避免 O(m·d) 的暴力。
• 成本可能很大（单行最高约 $2×10^11$，k 行最高约 $2×10^{13}$），需用 long long。
• 第 1 列和第 m 列必须放支撑柱，所以 dp[1] 固定为 1，dp[m] 即为该行答案。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main () {
	int T;
    scanf ("%d", &T);
    while (T--) {
        int n, m, k, d;
        scanf ("%d%d%d%d", &n, &m, &k, &d);
        vector <ll> cost (n + 1);
        for (int i = 1; i <= n; i++) {
            vector <int> a (m + 1);
            for (int j = 1; j <= m; j++) scanf ("%d", &a[j]);
            vector <ll> dp (m + 1);
            deque <int> q; // 维护窗口[j - d - 1, j - 1]内dp的最小值
            dp[1] = 1;
            q.push_back (1);
            for (int j = 2; j <= m; j++) {
                while (!q.empty () && q.front () < j - d- 1) q.pop_front ();
                // 删除超出窗口的队首
                dp[j] = a[j] + 1 + dp[q.front ()];
                while (!q.empty () && dp[q.back ()] >= dp[j]) q.pop_back ();
                // 删除>=dp[j]的队尾
                q.push_back (j);
            }
            cost[i] = dp[m];
        }
        ll sum = 0;
        for (int i = 1; i <= k; i++) sum += cost[i]; 
        ll ans = sum;
        for (int i = k + 1; i <= n; i++) {
            sum = sum + cost[i] - cost[i - k];
            ans = min (ans, sum);
        }
        printf ("%lld\n", ans);
    }
	return 0;
}

T5:Messenger in MAC

题意

n 条消息，每条有 a[i] 和 b[i]。选一个子集 $p_1,p_2,...,p_k$（阅读顺序可任意），阅读时间 $= sum(a[p_i]) + sum(|b[p_i]-b[p_i+1]|)$。求时间 ≤ l 时最多读多少条。

约束

• $1 ≤ t ≤ 5×10^4，1 ≤ n ≤ 2000$
• $1 ≤ a[i], b[i] ≤ 10^9，1 ≤ l ≤ 10^9$
• 所有测试用例 $n^2$ 之和 $≤ 4×10^6$

思路

关键观察：阅读顺序优化

选定子集后，阅读顺序可以任意。要使 sum(|b差|) 最小，按 b 排序阅读最优。

证明：b 值是一维点，访问所有点的最短路径就是排序后首尾相连，路径长 = max(b) - min(b)。

所以总时间 = **sum(a) + max(b) - min(b)**。

暴力算法（O(n²logn)）

1. 按 b 排序
2. 枚举 i1（b 最小的消息）和 ik（b 最大的消息）
3. b 贡献固定 = b[ik] - b[i1]，a[i1] 和 a[ik] 必须选
4. 中间 (i1, ik) 的消息用大根堆贪心选 a 最小的

大根堆贪心

固定 i1，ik 从 i1+1 往右扫：

• 每次把 a[ik-1] 加入候选池（它变成中间消息）
• 预算 = l - (b[ik]-b[i1]) - a[i1] - a[ik]
• 弹出堆中最大的 a 直到 sumA ≤ 预算
• 若 total = a[i1]+a[ik]+(b[ik]-b[i1])+sumA ≤ l，更新答案 = 堆大小 + 2

复杂度

• 枚举 $i1: O(n)$
• 每个 i1 扫 $ik: O(n)$
• 堆操作: O(log n)$
• 总: $$O(n²logn)，sum n^2 ≤ 4×10^6$，可接受

关键点

• 按 b 排序阅读使 b 贡献 = max(b) - min(b)，这是核心转化
• 大根堆贪心：维护候选池中 a 最小的若干个，超出预算就弹最大
• i1** 和 ik 必须选**：a[i1] 和 a[ik] 不进堆，直接计入 total
• 数据范围 $10^9$，用 long long
• 单独选一条消息：时间 = a[i]，需 a[i] ≤ l

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main () {
    int T;
    scanf ("%d", &T);
    while (T--) {
        int n;
        ll l;
        scanf ("%d%lld", &n, &l);
        vector <pair <ll, ll> > item (n);
        for (int i = 0; i < n; i++) scanf ("%lld%lld", &item[i].second, &item[i].first);
        sort (item.begin (), item.end ());
        int ans = 0;
        for (int i1 = 0; i1 < n; i1++) {
            priority_queue <ll> q;
            ll sumA = 0;
            for (int ik = i1; ik < n; ik++) {
                q.push (item[ik].second);
                sumA += item[ik].second;
                ll tmp = item[ik].first - item[i1].first;
                while (!q.empty () && sumA + tmp > l) {
                    sumA -= q.top ();
                    q.pop ();
                }
                ans = max (ans, (int) q.size ());
            }
        }
        printf ("%d\n", ans);
    }
    return 0;
}

T6:Set To Max (Hard Version)

题意

给定长度为 n 的数组 a 和 b。操作：选 [l,r]，令 x=max(a[l..r])，把 a[l..r] 都赋为 x。判断能否通过若干次操作把 a 变成 b。

约束

• $1 ≤ t ≤ 10^4，1 ≤ n ≤ 2×10^5$
• $1 ≤ a[i], b[i] ≤ n$
• 所有测试用例 n 之和 $≤ 2×10^5$

思路

基本观察

1. 操作只增不减：a[i] 只会变大或不变。所以 a[i] > b[i] 直接 NO。
2. a[i] == b[i]：不需要操作，跳过。
3. a[i] < b[i]：必须被某个操作覆盖，且操作的 max = b[i]。

种子与传播

对于 a[i] < b[i]，设 v = b[i]。需要找到「种子」j 使得 a[j] = v，然后操作 [min(i,j), max(i,j)] 把区间内所有值提升到 v。

但操作区间 [l,r] 必须满足两个条件：

• max(a[l..r]) = v：区间内所有 a[k] ≤ v（否则 max > v）
• 不破坏其他位置：区间内所有 b[k] ≥ v（否则 a[k] 被提到 v > b[k]，无法恢复）

算法

对每个 a[i] < b[i] 的位置 i，v = b[i]：

1. 二分 + ST表 求最大的可操作区间 [L, R] 包含 i：

   • L = 最小的左端点使 [L,i] 内 max(a) ≤ v 且 min(b) ≥ v

    - R = 最大的右端点使 [i,R] 内 max(a) ≤ v 且 min(b) ≥ v

2. 在 posA[v] 中二分查找 是否有种子位置落在 [L, R] 内

3. 若无种子 → NO

复杂度

• ST表建表 $O(n log n)$，每次查询 $O(1)$
• 每个位置二分 $O(log n)$，共 $O(n log n)$
• 总复杂度 $O(n log n)$

关键点

• ST表：维护 a 的区间最大值和 b 的区间最小值，支持 $O(1)$ 区间查询
• 二分边界：[L,R] 是 i 能向两侧扩展的最大范围，使得区间内 max(a) ≤ v 且 min(b) ≥ v
• 种子查找：posA[v] 有序，用 lower_bound 找 ≥ L 的第一个位置，检查是否 ≤ R
• **为什么 **min(b) ≥ v：操作会把区间内所有 a 提到 v，若某位置 b[k] < v，则 a[k] 被提到 v > b[k]，无法恢复
• **为什么 **max(a) ≤ v：若区间内 a[k] > v，则 max > v，操作结果不是

代码

#include <bits/stdc++.h>
using namespace std;
int sta[200010][20], stb[200010][20];
int lg[200010];
void buildST (int n, vector <int>& a, vector <int>& b) {
    for (int i = 1; i <= n; i++) {
        sta[i][0] = a[i];
        stb[i][0] = b[i];
    }
    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            sta[i][j] = max (sta[i][j - 1], sta[i + (1 << (j - 1))][j - 1]);
            stb[i][j] = max (stb[i][j - 1], stb[i + (1 << (j - 1))][j - 1]);
        }
    }
}
int querya (int l, int r) {
    int k = lg[r - l + 1];
    return max (sta[l][k], sta[r - (1 << k) + 1][k]);
}
int queryb (int l, int r) {
    int k = lg[r - l + 1];
    return min (stb[l][k], stb[r - (1 << k) + 1][k]);
}
int main () {
	int T;
    scanf ("%d", &T);
    while (T--) {
        int n;
        scanf ("%d", &n);
        vector <int> a (n + 1), b (n + 1);
        for (int i = 1; i <= n; i++) scanf ("%d", &a[i]);
        for (int i = 1; i <= n; i++) scanf ("%d", &b[i]);
        bool ok = true;
        for (int i = 1; i <= n; i++) {
            if (a[i] > b[i]) {
                ok = false;
                break;
            }
        }
        if (!ok) {
            puts ("NO");
            continue;
        }
        buildST (n, a, b);
        vector <vector <int> > posa (n + 1);
        for (int i = 1; i <= n; i++) posa[a[i]].push_back (i);
        for (int i = 1; i <= n && ok; i++) {
            if (a[i] == b[i]) continue;
            int v = b[i];
            int l = 1, r = i, L = i;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (querya (mid, i) <= v && queryb (mid, i) >= v) {
                    L = mid;
                    r = mid - 1;
                }
                else l = mid + 1;
            }
            l = i, r = n;
            int R = i;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (querya (i, mid) <= v && queryb (i, mid) >= v) {
                    R = mid;
                    l = mid + 1;
                }
                else r = mid - 1;
            }
            int idx = lower_bound (posa[v].begin (), posa[v].end (), L) - posa[v].begin ();
            if (idx == (int) posa[v].size () || posa[v][idx] > R) ok = false;
        }
        if (ok) puts ("YES");
        else puts ("NO");
    }
	return 0;
}