Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"workbook":{"problemsBrief":"{\"CodeForces-1774A\":[\"Add Plus Minus Sign\",22167,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/1774\\\"\\u003ePolynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!)\\u003c/a\\u003e\"],\"AtCoder-arc090_a\":[\"Candies\",1250,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/abc087\\\"\\u003eAtCoder Beginner Contest 087\\u003c/a\\u003e\"],\"CodeForces-1841A\":[\"Game with Board\",25254,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/1841\\\"\\u003eEducational Codeforces Round 150 (Rated for Div. 2)\\u003c/a\\u003e\"],\"CodeForces-1536A\":[\"Omkar and Bad Story\",20324,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/1536\\\"\\u003eCodeforces Round 724 (Div. 2)\\u003c/a\\u003e\"],\"CodeForces-1715A\":[\"Crossmarket\",23438,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/1715\\\"\\u003eCodeforces Round 816 (Div. 2)\\u003c/a\\u003e\"],\"AtCoder-codefestival_2016_quala_b\":[\"Friendly Rabbits\",120,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/code-festival-2016-quala\\\"\\u003eCODE FESTIVAL 2016 qual A\\u003c/a\\u003e\"],\"AtCoder-math_and_algorithm_ai\":[\"How Many Guests?\",2,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/math-and-algorithm\\\"\\u003eアルゴリズムと数学 演習問題集\\u003c/a\\u003e\"],\"洛谷-P1540\":[\"机器翻译\",85755,\"NOIP2010 提高组\"],\"AtCoder-abc079_c\":[\"Train Ticket\",1493,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/abc079\\\"\\u003eAtCoder Beginner Contest 079\\u003c/a\\u003e\"],\"CodeForces-1844A\":[\"Subtraction Game\",24044,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/1844\\\"\\u003eCodeforces Round 884 (Div. 1 + Div. 2)\\u003c/a\\u003e\"],\"AtCoder-tessoku_book_t\":[\"LCS\",2,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/tessoku-book\\\"\\u003e競技プログラミングの鉄則 演習問題集\\u003c/a\\u003e\"],\"AtCoder-tessoku_book_u\":[\"Block Game\",1,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/tessoku-book\\\"\\u003e競技プログラミングの鉄則 演習問題集\\u003c/a\\u003e\"],\"AtCoder-tessoku_book_v\":[\"Sugoroku\",1,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/tessoku-book\\\"\\u003e競技プログラミングの鉄則 演習問題集\\u003c/a\\u003e\"],\"AtCoder-tessoku_book_l\":[\"Printer\",3,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/tessoku-book\\\"\\u003e競技プログラミングの鉄則 演習問題集\\u003c/a\\u003e\"],\"AtCoder-tessoku_book_m\":[\"Close Pairs\",3,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/tessoku-book\\\"\\u003e競技プログラミングの鉄則 演習問題集\\u003c/a\\u003e\"],\"AtCoder-tessoku_book_o\":[\"Compression\",3,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/tessoku-book\\\"\\u003e競技プログラミングの鉄則 演習問題集\\u003c/a\\u003e\"],\"AtCoder-tessoku_book_p\":[\"Dungeon 1(※初版第 1 刷の B22 も同じ問題です)\",2,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/tessoku-book\\\"\\u003e競技プログラミングの鉄則 演習問題集\\u003c/a\\u003e\"],\"AtCoder-tessoku_book_q\":[\"Dungeon 2\",2,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/tessoku-book\\\"\\u003e競技プログラミングの鉄則 演習問題集\\u003c/a\\u003e\"],\"AtCoder-abc175_a\":[\"Rainy Season\",12035,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/abc175\\\"\\u003eAtCoder Beginner Contest 175\\u003c/a\\u003e\"],\"AtCoder-tessoku_book_r\":[\"Subset Sum\",2,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/tessoku-book\\\"\\u003e競技プログラミングの鉄則 演習問題集\\u003c/a\\u003e\"],\"AtCoder-tessoku_book_s\":[\"Knapsack 1\",4,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/tessoku-book\\\"\\u003e競技プログラミングの鉄則 演習問題集\\u003c/a\\u003e\"],\"AtCoder-tessoku_book_g\":[\"Event Attendance\",2,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/tessoku-book\\\"\\u003e競技プログラミングの鉄則 演習問題集\\u003c/a\\u003e\"],\"AtCoder-tessoku_book_h\":[\"Two Dimensional Sum\",50,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/tessoku-book\\\"\\u003e競技プログラミングの鉄則 演習問題集\\u003c/a\\u003e\"],\"AtCoder-tessoku_book_i\":[\"Winter in ALGO Kingdom\",3,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/tessoku-book\\\"\\u003e競技プログラミングの鉄則 演習問題集\\u003c/a\\u003e\"],\"AtCoder-tessoku_book_j\":[\"Resort Hotel\",2,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/tessoku-book\\\"\\u003e競技プログラミングの鉄則 演習問題集\\u003c/a\\u003e\"],\"AtCoder-tessoku_book_k\":[\"Binary Search 1\",34,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/tessoku-book\\\"\\u003e競技プログラミングの鉄則 演習問題集\\u003c/a\\u003e\"]}","joined":false,"groups":{}},"managingGroups":{},"author":"im0use2","updateTime":1690294548000,"title":"算法初学者的试题集(自用","dislikeCnt":0,"content":"- 算法专题训练\n\n- 枚举\n\n[problem:AtCoder-abc175_a] rate:100\n[problem:AtCoder-arc090_a] rate:310枚举列\n[problem:AtCoder-abc079_c] rate:337\n[problem:AtCoder-codefestival_2016_quala_b] rate:400 $O(n)$而不是$O(n^2)$ 巧妙枚举\n\n- 队列\n\n[problem:洛谷-P1540] 队列初使用\n\n- codeforces 层次训练(自己通过创建 contest 进行测试)\n\n- codeforces 800 (worked)\n\n[problem:CodeForces-1841A] 手玩样例\n[problem:CodeForces-1715A] \n[problem:CodeForces-1774A] 奇偶性质\n[problem:CodeForces-1844A] 手玩样例\n[problem:CodeForces-1536A] 模拟\n\n阅表\n\n- 计算量(时间复杂度)\n\n- 排序\n\n- 冒泡排序\n\n需要n次循环,每次循环遍历所有的位置将两个相邻之间位置关系不对的进行交换 `swap(a[i], a[i + 1])`。共 $O(n^2)$\n\n```c++\nfor (int i \u003d 0; i \u003c n; i++)\n\tfor (int j \u003d 0; j \u003c n - 1; j++)\n\t\tif (array[j] \u003e array[j + 1] \n\t\t\tswap(array[j], array[j + 1]);\n```\n\n- 逆序对\n\n理解冒泡排序的一个好的工具。每次交换是因为存在 `a \u003c b \u0026\u0026 array[a] \u003e array[b]` 这样的一对用 $(a,b)$ 形容的位置。\n\n```\n数字 1, 2, 2, 6, 3, 5, 9, 8\n位置 1, 2, 3, 4, 5, 6, 7, 8\n```\n\n其中位置对 $(4, 5),(4,6)$ 等等是逆序对。\n\n一个数组进行冒泡排序,排好序后,不存在逆序对。\n\n比如 `4, 3, 2, 1` 存在 `3 + 2 + 1 \u003d 6` 个逆序对,表示在冒泡排序中需要进行 6 次交换才能有序。\n\n排序api,`std::sort`\n\n```c++\nvector\u003cint\u003e v \u003d {4, 5, 2, 1};\nsort(v.begin(), v.end()); // 1, 2, 4, 5\n\nint n \u003d 4;\nint a[] \u003d {4, 5, 2, 1};\nsort(a, a + n); // 1, 2, 4, 5\n```\n\n- 队列\n\nqueue 提供两个O(1)操作,头部移除,尾部插入,仅能访问头部和尾部。\n\n应用实例:\n\n```c++\nqueue\u003cint\u003e q;\nq.push(3);\nq.push(2);\nq.push(5);\ncout \u003c\u003c q.front() \u003c\u003c \"\\n\"; // 3\nq.pop();\ncout \u003c\u003c q.front() \u003c\u003c \"\\n\"; // 2\n```\n\n- 累加和(前后缀和)\n\n例题1:[problem:AtCoder-math_and_algorithm_ai]\n\n问题是给一个长度为n的数组,有q次询问,每次询问给出 $l,r$,问 $a_l+a_{l+1}+a_{l+2}+...+a_r$ 的值。\n\n如果每次枚举求解和的话需要 $O(n)$ 的时间,于是这里有一个方法可以先求出 $presum(r)$ 表示 $a_1+a_2+...+a_r$ 的和。\n\n开始推导,\n\n```c\npresum[i] \u003d a[1] + a[2] + ... + a[i - 1] + a[i]\npresum[i - 1] \u003d a[1] + a[2] + ... + a[i - 1]\npresum[i] \u003d presum[i - 1] + a[i] // 递推公式\n\npresum[r] \u003d a[1] + a[2] + ... + a[r]\npresum[l - 1] \u003d a[1] + a[2] + ... + a[l - 1] + a[l] + a[l + 1] + ... + a[r]\npresum[r] - presum[l - 1] \u003d a[l] + a[l + 1] + ... + a[r] // 所以我们的答案就是 presum[r] - presum[l - 1]\n```\n\n当数组a不变时,可以先算出每个 `presum[i]` 需要 $O(n)$ 的时间,然后每次给出 `presum[r] - presum[l - 1]` 需要 $O(1)$ 的时间。\n\n实现如下:\n\n```c++\n#include \u003cbits/stdc++.h\u003e\nusing namespace std;\nint main() {\n int N, Q;\n cin \u003e\u003e N \u003e\u003e Q;\n vector\u003cint\u003e A(N + 1); // 开一个大小为N+1的数组\n for (int i \u003d 1; i \u003c\u003d N; i++) cin \u003e\u003e A[i];\n vector\u003cint\u003e presum(N + 1); // 前缀和数组\n for (int i \u003d 1; i \u003c\u003d N; i++) presum[i] \u003d presum[i - 1] + A[i]; // 如何预处理前缀和数组\n while (Q--) {\n int L, R; // 表示一个区间 [L, R]\n std::cin \u003e\u003e L \u003e\u003e R;\n std::cout \u003c\u003c presum[R] - presum[L - 1] \u003c\u003c \"\\n\";\n }\n return 0;\n}\n```\n\n例题2:[problem:AtCoder-tessoku_book_g]\n\n假设有 $1,2,..,n$ 个位置,每个位置有一个数字 $0$,给出 $q$ 次操作,每次给出 $l,r$,在 $l,l+1,l+2,...,r$ 这些位置上的数字加上 $1$,然后最后输出每个位置的数字是多少。\n\n假如对给定的 $l,r$ 的每个位置枚举操作,那么需要 $O(n)$ 的时间。\n\n我们可以先操作完最后再输出,于是有一个方法。$presum(r)$ 表示 $a_1+a_2+...+a_r$ 的和,$different(r)$ 表示 $different(r)\u003dpresum(r)-presum(r-1)$,即前缀和减去上一个前缀和。\n\n开始推导\n\n```c++\npresum[i] \u003d a[1] + a[2] + ... + a[i - 1] + a[i]\npresum[i - 1] \u003d a[1] + a[2] + ... + a[i - 1]\ndifferent[i] \u003d presum[i] - presum[i - 1] \u003d a[i] // 说明了 different 就是 a\npresum[i] - presum[i - 1] \u003d different[i]\npresum[i] \u003d presum[i - 1] + different[i]\npresum[i] \u003d different[1] + different[1] + ... + different[i]\n```\n\n假设我们这次操作的数组为 `different`,要求出的数组为 `presum`。要求出的数组初始时都是 $0$,我们使用循环先计算出 `different`。\n\n```c++\nint n \u003d 7;\nvector\u003cint\u003e presum(n + 1);\nvector\u003cint\u003e different(n + 1);\nfor (int i \u003d 1; i \u003c\u003d n; i++) different[i] \u003d presum[i] - presum[i - 1];\n```\n\n当然了当 `presum` 都是 $0$,`different` 也都是 $0$,不用求。\n\n假设 `presum` 在 $L,L+1,...,R$ 位置都加 $1$,那我给 `different[L]` 加 $1$,因为 `presum[i] \u003d different[1] + different[1] + ... + different[i]` 表示 `i` 位置只受小于 `i` 的数字影响,则大于或者等于 `L` 的位置都会加 $1$,然后我再给 `different[R + 1]` 减 $1$,则大于 $R$ 的位置,同时加 $1$ 和减 $1$,所以不变,最终只有 $L,L+1,...,R$ 实现了加 $1$,其他位置不变。\n\n实现如下:`df` 表示 `different`,`pr` 表示 `presum`。\n\n```c++\n#include \u003cbits/stdc++.h\u003e\nusing namespace std;\nint main() {\n int D, N;\n cin \u003e\u003e D \u003e\u003e N;\n vector\u003cint\u003e df(D + 1);\n while (N--) {\n int L, R;\n cin \u003e\u003e L \u003e\u003e R;\n df[L]++;\n df[R + 1]--; // 上面提到的两个操作\n }\n vector\u003cint\u003e pr(D + 1);\n for (int i \u003d 1; i \u003c\u003d D; i++) pr[i] \u003d pr[i - 1] + df[i]; // 通过公式从different算出presum\n for (int i \u003d 1; i \u003c\u003d D; i++) cout \u003c\u003c pr[i] \u003c\u003c \"\\n\";\n return 0;\n}\n```\n\n例题3:[problem:AtCoder-tessoku_book_h]\n\n给一个二维方格,每个格子里都有一个数字,有 $q$ 次询问,每次询问从左上 $(A, B)$ 到右下 $(C, D)$ 之间的格子的数字之和。\n\n我们使用 $presum(x,y)$ 表示从左上角 $(1,1)$ 到右下角 $(x,y)$ 的数字之和。\n\n大致如下:\n\n```c++\nint sum \u003d 0;\nfor (int i \u003d 1; i \u003c\u003d x; i++)\n\tfor (int j \u003d 1; j \u003c\u003d y; j++)\n\t\tsum +\u003d a[i][j];\npresum[x][y] \u003d sum;\n```\n\n这就是 `presum[x][y]` 的含义。\n\n`presum` 具有一些特点,开始推导。\n\n```c++\npresum[x][y] \u003d presum[x - 1][y] + (a[x][1] + a[x][2] + ... + a[x][y]);\npresum[x][y] \u003d presum[x][y - 1] + (a[1][y] + a[2][y] + ... + a[x][y]);\n```\n\n好像没什么用,我们想求从左上 $(A, B)$ 到右下 $(C, D)$ 之间的格子的数字之和,怎么办呢?\n\n```c++\n(A - 1, B - 1) (A - 1, D)\n\t\t (A, B) (A, D)\n\t\t ... \n(C, B - 1) (C, B) (C, D)\nans(a, b, c, d) \u003d presum[c][d] - presum[c][b - 1] - presum[a - 1][d] + presum[a - 1][b - 1]\n```\n\n因为根据长方形,我就需要减去上面那一坨 `presum[c][b - 1]` 和左边那一坨 `presum[a - 1][d]`,但是当减去这两坨后,发现多减去了一坨,这一坨就是 `presum[a - 1][b - 1]`,那就再加上。(为什么这么做,你动手画一画,看看能不能理解?)\n\n那怎么求 `presum` 呢,那就先对一维进行累加和运算,再对另一维进行累加和运算。\n\n假设我先通过行将数值加到 `presum`。\n\n比如第一行为 `1, 2, 3`,则通过这一操作 `presum[1][i] \u003d presum[1][i - 1] + a[1][i]` 使得 `presum \u003d {1, 3, 6}`。\n\n```c++\nfor (int i \u003d1; i \u003c\u003d n; i++)\n\tfor (int j \u003d 1; j \u003c\u003d m; j++)\n\t\tpresum[i][j] \u003d presum[i][j - 1] + a[i][j]; // 对第 i 行进行累加和运算\n```\n\n然后再通过每列加上上一列,得到当前列。即presum已经是a了,通过 `presum[i] \u003d presum[i - 1] + a[i]` 公式进行推导,变成了 `presum[i] \u003d presum[i - 1] + presum[i]`。在带上列即 `presum[i][j] \u003d presum[i - 1][j] + presum[i][j]`。\n\n实现如下:\n\n```c++\n#include \u003cbits/stdc++.h\u003e\nusing namespace std;\nint main() {\n using ll \u003d long long;\n int H, W;\n cin \u003e\u003e H \u003e\u003e W;\n vector\u003cvector\u003cll\u003e\u003e X(H + 1, vector\u003cll\u003e(W + 1));\n for (int i \u003d 1; i \u003c\u003d H; i++) \n for (int j \u003d 1; j \u003c\u003d W; j++)\n cin \u003e\u003e X[i][j];\n vector\u003cvector\u003cll\u003e\u003e pr(H + 1, vector\u003cll\u003e(W + 1));\n for (int i \u003d 1; i \u003c\u003d H; i++)\n for (int j \u003d 1; j \u003c\u003d W; j++)\n pr[i][j] \u003d pr[i][j - 1] + X[i][j]; // 行累加\n for (int j \u003d 1; j \u003c\u003d W; j++)\n for (int i \u003d 1; i \u003c\u003d H; i++)\n pr[i][j] \u003d pr[i - 1][j] + pr[i][j]; // 列累加\n int Q;\n cin \u003e\u003e Q;\n while (Q--) {\n int A, B, C, D;\n cin \u003e\u003e A \u003e\u003e B \u003e\u003e C \u003e\u003e D;\n cout \u003c\u003c pr[C][D] - pr[C][B - 1] - pr[A - 1][D] + pr[A - 1][B - 1] \u003c\u003c \"\\n\";\n }\n return 0;\n}\n```\n\n例题4:[problem:AtCoder-tessoku_book_i]\n\n给一个二维方格,初始每个格子的数字都是 $0$,然后有 $q$ 次操作,每次操作对左上 $(A, B)$ 到右下 $(C, D)$ 之间的格子的数字都加上 $1$。\n\n这里再用 `different` 感觉不合适,那就直接用 `a` 表示,结果用 `presum` 表示,均为二维数组。`presum` 同上面的定义。\n\n我们也有一个对 a 的加点方式,使得可以最后再求 `presum`。(我也不可能想到的方法,但是学习了,理解了,会用了,就是自己的。)\n\n将 `a[A][B]` 加 $1$,此时所以坐标 $(X\\ge A,Y\\ge B)$ 都会受到这个加的影响,但是我们只是想给定的矩形区域内加 $1$,于是我们发现需要在 `a[A][D + 1]` 和 `a[C + 1][B]` 处减 $1$,但是要给 `a[C + 1][D + 1]` 加上 $1$。\n\n实现如下:\n\n```c++\n#include \u003cbits/stdc++.h\u003e\nusing namespace std;\nusing ll \u003d long long;\nconst int N \u003d 1505;\nll X[N][N], presum[N][N];\nint main() {\n int H, W, N;\n cin \u003e\u003e H \u003e\u003e W \u003e\u003e N;\n while (N--) {\n int A, B, C, D;\n cin \u003e\u003e A \u003e\u003e B \u003e\u003e C \u003e\u003e D;\n X[A][B]++;\n X[A][D + 1]--;\n X[C + 1][B]--;\n X[C + 1][D + 1]++;\n }\n for (int i \u003d 1; i \u003c\u003d H; i++)\n for (int j \u003d 1; j \u003c\u003d W; j++)\n presum[i][j] \u003d presum[i][j - 1] + X[i][j];\n for (int j \u003d 1; j \u003c\u003d W; j++)\n for (int i \u003d 1; i \u003c\u003d H; i++)\n presum[i][j] \u003d presum[i - 1][j] + presum[i][j];\n for (int i \u003d 1; i \u003c\u003d H; i++) {\n for (int j \u003d 1; j \u003c\u003d W; j++) {\n cout \u003c\u003c presum[i][j] \u003c\u003c \" \";\n }\n cout \u003c\u003c \"\\n\";\n }\n return 0;\n}\n```\n\n例题5:[problem:AtCoder-tessoku_book_j]\n\n在 $1,2,...,n$ 上的每个位置有一个数字,给出 $q$ 次询问,每次询问给出 $l,r$,问忽略 $l,l+1,l+2,...,r$ 这些位置的最大数字。\n\n设 $premax(R)$ 表示 $a_1,a_2,...,a_R$ 的最大值,$sufmax(L)$ 表示 $a_L,a_{L+1},...,a_n$ 的最大值,$answer(L, R)$ 表示我们要求的值。\n\n开始推导\n\n```c++\npremax[R] \u003d max(a[1], a[2], ..., a[R])\npremax[L - 1] \u003d max(a[1], a[2], ..., a[L - 1])\nsufmax[L] \u003d max(a[L], a[L + 1], ..., a[n])\nsufmax[R + 1] \u003d max(a[R + 1], a[R + 2], ..., a[n])\nanswer(L, R) \u003d max(a[1], a[2], ..., a[L - 1], a[R + 1], a[R + 2], ..., a[n])\n\u003d max( max(a[1], a[2], ..., a[L - 1]), max(a[R + 1], a[R + 2], ..., a[n]) )\n\u003d max( premax[L - 1], sufmax[R + 1] )\n```\n\n所以当每个位置的值不变时,可以先算出 $premax,sufmax$,然后通过 `max( premax[L - 1], sufmax[R + 1] )` 计算出答案。\n\n```c++\n#include \u003cbits/stdc++.h\u003e\nusing namespace std;\nusing ll \u003d long long;\nint main() {\n int N;\n cin \u003e\u003e N;\n vector\u003cint\u003e A(N + 2);\n for (int i \u003d 1; i \u003c\u003d N; i++) cin \u003e\u003e A[i];\n vector\u003cint\u003e premax(N + 2);\n for (int i \u003d 1; i \u003c\u003d N; i++) premax[i] \u003d max(premax[i - 1], A[i]); \n vector\u003cint\u003e sufmax(N + 2);\n for (int i \u003d N; i \u003e\u003d 1; i--) sufmax[i] \u003d max(sufmax[i + 1], A[i]);\n int D;\n cin \u003e\u003e D;\n while (D--) {\n int L, R;\n cin \u003e\u003e L \u003e\u003e R;\n cout \u003c\u003c max(premax[L - 1], sufmax[R + 1]) \u003c\u003c \"\\n\";\n }\n return 0;\n}\n```\n\n- 二分搜索\n\n例题1:[problem:AtCoder-tessoku_book_k]\n\n在 $1,2,...,n$ 位置上都有数字 $a_i$,满足 $a_1\u003ca_2\u003c...\u003ca_n$,即随着下标的增加,数字也会增加。问数字 $x$ 在第几个位置。\n\n如果使用枚举,时间是 $O(n)$ 的,这里我们要求使用更加快速的方法,在计算量为 $O(n)$ 的条件下完成。\n\n首先我们有一个范围是从 $L$ 到 $R$,然后找到它的中点位置 `mid \u003d (L + R) / 2`,然后让目标值与中点位置的数值进行比较,如果中点位置更大,则目标值出现的位置肯定小于 `mid`,则让 `R \u003d mid - 1`,如果中点的位置更小,则目标值出现的位置肯定大于 `mid`,则让 `L \u003d mid + 1`。\n\n于是我们写下 cpp 代码\n\n```c++\n#include \u003cbits/stdc++.h\u003e\nusing namespace std;\nusing ll \u003d long long;\nint main() {\n int N, X;\n cin \u003e\u003e N \u003e\u003e X;\n vector\u003cint\u003e A(N + 1);\n for (int i \u003d 1; i \u003c\u003d N; i++) cin \u003e\u003e A[i];\n int L \u003d 1, R \u003d N;\n while (L \u003c\u003d R) {\n int mid \u003d (L + R) / 2;\n if (A[mid] \u003e X) R \u003d mid - 1; // 中点值较大 说明在左边\n else if (A[mid] \u003c X) L \u003d mid + 1; // 中点值较小 说明在右边\n else {\n cout \u003c\u003c mid \u003c\u003c \"\\n\";\n return 0;\n }\n }\n return 0;\n}\n```\n\n例题2:[problem:AtCoder-tessoku_book_l]\n\n有 $1,2,...,n$ 台机器,上有个数字表示生产产品的速度 $a_i$,表示每 $a_i$ 秒生产出一件产品,则问第 $x$ 件产品的产出时间。\n\n那么我们可以使用枚举,枚举前 $i$ 秒产生了多少件产品, 当产品数出现大于或者等于 $x$ 时,输出秒数。每次计算前 $i$ 秒的生产产品数,需要 $O(n)$ 的计算量,因为 $x$ 在 `1e9` 范围内,所以我们枚举会超过限制时间。\n\n这里有一个做法。假定一个时间下限 $L$ 和一个时间上限 $R$,这时候我们的答案肯定在这里面。然后找到它的中点位置 `mid \u003d (L + R) / 2`,然后让计算出中点位置的秒数产生产品数 `word(mid)`,目标值与 `work(mid)` 进行比较,如果 `work(mid)` 更大,则目标值出现的位置肯定小于或者等于 `mid`,则让 `R \u003d mid`,如果 `work(mid)` 更小,则目标值出现的位置肯定大于 `mid`,则让 `L \u003d mid + 1`。\n\n每次计算 `work(mid)` 就是计算前 `mid` 秒产生产品数,可以使用枚举,第一件产品产生 `mid / a[1]`,第二件产品产生 `mid / a[2]`,最终算出所有机器的产出,计算量为 $O(n)$。\n\n外面使用了二分搜索,所以是 $O(n\\times \\log n)$,$n\u003d100000,n\\log n\\approx 1.6\\times 10^6$。\n\n科普 `c++ lambda函数写法`\n\n```c++\n// 非递归函数\nauto 函数名 \u003d [\u0026](参数列表) -\u003e 返回类型 {\n 函数实现\n};\n// 比如 sum(a, b) \u003d a + b\nauto sum \u003d [\u0026](int a, int b) -\u003e int {\n return a + b;\n};\n```\n\n`lambda` 函数的好处,可以使用当前定义的局部变量,即使不使用全局变量,也不需要写很多的传参。\n\n```c++\n#include \u003cbits/stdc++.h\u003e\nusing namespace std;\nusing ll \u003d long long;\nint main() {\n int N, K;\n cin \u003e\u003e N \u003e\u003e K;\n vector\u003cint\u003e A(N);\n for (int i \u003d 0; i \u003c N; i++) cin \u003e\u003e A[i];\n auto work \u003d [\u0026](int mid) -\u003e ll { \n ll ans \u003d 0;\n for (int i \u003d 0; i \u003c N; i++) ans +\u003d mid / A[i];\n return ans;\n };\n int L \u003d 1, R \u003d 1e9;\n while (L \u003c R) {\n int mid \u003d (L + R) / 2;\n auto w \u003d work(mid);\n if (w \u003c K) L \u003d mid + 1;\n else R \u003d mid;\n }\n cout \u003c\u003c L \u003c\u003c \"\\n\";\n return 0;\n}\n```\n\n例题3:[problem:AtCoder-tessoku_book_m]\n\n在 $1,2,...,n$ 位置上都有数字 $a_i$,满足 $a_1\u003ca_2\u003c...\u003ca_n$,即随着下标的增加,数字也会增加。问存在多少对 $(i,j)$ 满足 $i\u003cj,a[j]-a[i]\\le k$。\n\n做法,对 $a[i]$ 找到一个 $a[j]\u003e\u003da[i]+k$,则有 $(i,i+1),(i,i+2),...,(i,j-1)$ 共 $j-i-1$ 对结果。\n\n但是这样也是很费时的,可以对每个 $j$ 去找 $i$,并且下一个可以由上一个进行推导。\n\n$i$ 表示左端点,$j$ 表示右端点,遍历所有的 $j$,每次 $j$ 往右移动一格,判断 `a[j] \u003e a[i] + k`,如果有则 $i$ 向右移动一个,如果满足再向右移动一格,直到这个式子不满足条件。此时 $(i,j),(i+1,j),...,(j-1,j)$ 是满足的,共 $j-i$ 个,并且 $j$ 永远是不同的,所以直接加到答案中。\n\n实现如下:\n\n```c++\n#include \u003cbits/stdc++.h\u003e\nusing namespace std;\nusing ll \u003d long long;\nint main() {\n int N, K;\n cin \u003e\u003e N \u003e\u003e K;\n vector\u003cint\u003e A(N + 1);\n for (int i \u003d 1; i \u003c\u003d N; i++) cin \u003e\u003e A[i];\n ll ans \u003d 0;\n for (int i \u003d 1, j \u003d 1; j \u003c\u003d N; j++) {\n while (A[j] - A[i] \u003e K) i++; // 大于K,左端点 i 不断加 1\n ans +\u003d j - i; // 满足条件的 (i,i+1),(i,i+2),...,(i,j-1)\n }\n cout \u003c\u003c ans \u003c\u003c \"\\n\";\n return 0;\n}\n```\n\n例题4:[problem:AtCoder-tessoku_book_m]\n\n$4$ 个箱子,每个箱子里有 $n$ 个数字,各箱子取一个数字一共获取 $4$ 个数字,问有没有可能这 $4$ 个数字之和为 $x$。\n\n那么我们可以使用枚举,需要枚举第一个箱子的数字,然后再枚举第二个箱子的数字,然后再枚举第三个箱子的数字,最后再枚举第四个箱子的数字,最终计算量为 $O(n^4),n\u003d1000,n^4\u003d1e12$,于是会超过限制时间。\n\n这里有一个方法。我先计算前两个箱子中抽取数字的和并记录在 `sum1` 数组中,然后对 `sum1` 进行排序,这需要 $O(n^2+n^2\\log{n^2})$ 的时间和 $O(n^2)$ 的空间,然后在计算后两个箱子中抽取数字的和 `sum`,然后判断是不是和前面的 `sum1` 的和等于 $x$,可以使用二分搜索进行判断,这需要 $O(n^2\\log{n^2})$ 的计算量。\n\n实现如下:\n\n```c++\n#include \u003cbits/stdc++.h\u003e\nusing namespace std;\nusing ll \u003d long long;\nint main() {\n int N, K;\n cin \u003e\u003e N \u003e\u003e K;\n vector\u003cint\u003e A(N);\n for (int i \u003d 0; i \u003c N; i++) cin \u003e\u003e A[i];\n vector\u003cint\u003e B(N);\n for (int i \u003d 0; i \u003c N; i++) cin \u003e\u003e B[i];\n vector\u003cint\u003e C(N);\n for (int i \u003d 0; i \u003c N; i++) cin \u003e\u003e C[i];\n vector\u003cint\u003e D(N);\n for (int i \u003d 0; i \u003c N; i++) cin \u003e\u003e D[i];\n vector\u003cint\u003e sum1(N * N);\n for (int i \u003d 0; i \u003c N; i++)\n for (int j \u003d 0; j \u003c N; j++)\n sum1[i * N + j] \u003d A[i] + B[j];\n sort(sum1.begin(), sum1.end());\n for (int i \u003d 0; i \u003c N; i++) \n for (int j \u003d 0; j \u003c N; j++) {\n int sum \u003d C[i] + D[j];\n int L \u003d 0, R \u003d N * N - 1;\n while (L \u003c\u003d R) {\n int mid \u003d (L + R) / 2;\n if (sum1[mid] + sum \u003d\u003d K) {\n cout \u003c\u003c \"Yes\\n\";\n return 0;\n } else if (sum1[mid] + sum \u003e K) {\n R \u003d mid - 1;\n } else {\n L \u003d mid + 1;\n }\n }\n }\n cout \u003c\u003c \"No\\n\";\n return 0;\n}\n```\n\n例题5:[problem:AtCoder-tessoku_book_o]\n\n给一个数组 $a$,对其进行压缩成 $b$,要求保持其大小关系。即要求算出 $a$ 中每个数字是大小第几大的数字。\n\n例如 `a \u003d [4, 10, 3, 6] -\u003e b \u003d [2, 4, 1, 3]`。\n\n首先我们复制一份 $a$ 为 $c$,将 $c$ 排序去重,计算量为 $O(n\\log n)$,然后对 $a$ 中的每个数字使用例题1中的方法去找该数字是第几大,通过二分搜索技术,使得总计算量变为 $O(n\\times \\log n)$。\n\n实现如下:\n\n```c++\n#include \u003cbits/stdc++.h\u003e\nusing namespace std;\nusing ll \u003d long long;\nint main() {\n int N;\n cin \u003e\u003e N;\n vector\u003cint\u003e A(N);\n for (int i \u003d 0; i \u003c N; i++) cin \u003e\u003e A[i];\n auto C \u003d A; // 将 A 复制给 C\n sort(C.begin(), C.end());\n C.erase(unique(C.begin(), C.end()), C.end()); // 排序去重 api 库函数\n for (int i \u003d 0; i \u003c N; i++) cout \u003c\u003c lower_bound(C.begin(), C.end(), A[i]) - C.begin() + 1 \u003c\u003c \" \"; // 二分 api 库函数 lower_bound(begin, end, x)表示在 begin 到 end 中找到 \u003e\u003d x 的位置并返回,然后减去 begin 加 1 就是第几个位置\n return 0;\n}\n```\n\n- 动态规划\n\n例题1:[problem:AtCoder-tessoku_book_p]\n\n有 $1,2,...,n$ 个位置,一个人想从 $1$ 去往 $n$,有以下两种走路方式。\n\n- 从 $i-1$ 到 $i$ 花费 $a_i$ 分钟 $2\\le i\\le n$\n- 从 $i-2$ 到 $i$ 花费 $b_i$ 分钟 $3\\le i\\le n$\n\n问从 $1$ 去往 $n$ 的最短时间。\n\n设 $mintime(x)$ 表示从 $1$ 到 $x$ 的最短时间。有两种运动方式,那么 $mintime(x)$ 分别与 $mintime(x - 1) + a(i)$ 和 $mintime(x - 2) + b(i)$ 相关,定义是最短时间,所以我们取两个之中最小值即 $\\min(mintime(x - 1) + a(i), mintime(x - 2) + b(i))$\n\n实现如下:\n\n```c++\n#include \u003cbits/stdc++.h\u003e\nusing namespace std;\nusing ll \u003d long long;\nint main() {\n int N;\n cin \u003e\u003e N;\n vector\u003cint\u003e A(N + 1);\n for (int i \u003d 2; i \u003c\u003d N; i++) cin \u003e\u003e A[i];\n vector\u003cint\u003e B(N + 1);\n for (int i \u003d 3; i \u003c\u003d N; i++) cin \u003e\u003e B[i];\n vector\u003cint\u003e mintime(N + 1);\n for (int i \u003d 2; i \u003c\u003d N; i++) {\n int min_time \u003d mintime[i - 1] + A[i]; // A 的运动 i - 1 -\u003e i\n if (i \u003e\u003d 3) min_time \u003d min(min_time, mintime[i - 2] + B[i]); // B 的运动 i - 2 -\u003e i\n mintime[i] \u003d min_time; // 最后赋给 mintime[i]\n }\n cout \u003c\u003c mintime[N] \u003c\u003c \"\\n\";\n return 0;\n}\n```\n\n例题2:[problem:AtCoder-tessoku_book_q]\n\n有 $1,2,...,n$ 个位置,一个人想从 $1$ 去往 $n$,有以下两种走路方式。\n\n- 从 $i-1$ 到 $i$ 花费 $a_i$ 分钟 $2\\le i\\le n$\n- 从 $i-2$ 到 $i$ 花费 $b_i$ 分钟 $3\\le i\\le n$\n\n问从 $1$ 去往 $n$ 的最短时间的走路的路径。\n\n与上一题唯一一点不同就是要输出这个最短时间的路径。\n\n设 $mintime(x)$ 表示从 $1$ 到 $x$ 的最短时间。获取 $mintime(x)$ 的两种获得方式的时候,我们可以记录一下,是谁运动到了 $x$ 这个地方,设为 $prepos(x)$ 表示 $x$ 的上一个位置。$mintime(x - 1) + a(i)$ 和 $mintime(x - 2) + b(i)$ 俩谁更小,就是有谁移动过来的。\n\n```c++\nif (mintime[x - 1] + a[i] \u003c mintime[x - 2] + b[i]) prepos[x] \u003d x - 1;\nelse prepos[x] \u003d x - 2;\n```\n\n实现如下:\n\n```c++\n#include \u003cbits/stdc++.h\u003e\nusing namespace std;\nusing ll \u003d long long;\nint main() {\n int N;\n cin \u003e\u003e N;\n vector\u003cint\u003e A(N + 1);\n for (int i \u003d 2; i \u003c\u003d N; i++) cin \u003e\u003e A[i];\n vector\u003cint\u003e B(N + 1);\n for (int i \u003d 3; i \u003c\u003d N; i++) cin \u003e\u003e B[i];\n vector\u003cint\u003e mintime(N + 1), prepos(N + 1);\n for (int i \u003d 2; i \u003c\u003d N; i++) {\n if (i \u003d\u003d 2) {\n mintime[i] \u003d A[i];\n prepos[i] \u003d i - 1;\n } else {\n if (mintime[i - 1] + A[i] \u003c mintime[i - 2] + B[i]) { // i - 1 -\u003e i\n mintime[i] \u003d mintime[i - 1] + A[i];\n prepos[i] \u003d i - 1;\n } else { // i - 2 -\u003e i\n mintime[i] \u003d mintime[i - 2] + B[i];\n prepos[i] \u003d i - 2;\n }\n }\n }\n int pos \u003d N;\n std::vector\u003cint\u003e path; // 收集路径信息\n do {\n path.push_back(pos);\n pos \u003d prepos[pos];\n } while (pos !\u003d 1);\n path.push_back(1);\n reverse(path.begin(), path.end()); // 数组逆序\n cout \u003c\u003c path.size() \u003c\u003c \"\\n\";\n for (int i \u003d 0; i \u003c path.size(); i++)\n cout \u003c\u003c path[i] \u003c\u003c \" \";\n return 0;\n}\n```\n\n例题3:[problem:AtCoder-tessoku_book_r]\n\n给出 $n,n\\le 60$ 个数字 $a_i\\le 10000$,问是否可以取其中的一些数字使得它们的和为 $x\\le 10000$。\n\n令 $dp(i,j)\u003d1/0$ 表示是否可以前 $i$ 个数字中取出的数字和为 $j$。计算量为 $O(60x)$。\n\n例题4:[problem:AtCoder-tessoku_book_s]\n\n经典背包。$dp(i,j)$ 表示前 $i$ 个物品重量和为 $j$ 的最大收益,答案为 $max(dp(N,1 \u003c\u003d j \u003c\u003d W))$。计算量为 $O(NW)$。\n\n例题5:[problem:AtCoder-tessoku_book_t]\n\n经典 LCS。$dp(i,j)$ 表示 $S$ 的前 $i$ 字符和 $T$ 的前 $j$ 字符的最大匹配长度。计算量为 $O(|S|\\times |T|)$。\n\n例题5:[problem:AtCoder-tessoku_book_u]\n\n给出 $1,2,...,n$ 位置,将这些位置全部消除,有两种消除方式。\n\n- 从最左边删除一个数字。\n- 从最右边删除一个数字。\n\n给出一些加点,如果 $p_i$ 在 $i$ 前面消除,会获得 $a_i$,问在所有删除方法中可以获得最大的值。\n\n定义 $dfs(l,r)$ 表示删除区间 $(l,r)$ 获得的最大值,然后记忆化搜索。\n\ncode:[record 记忆化搜索](https://atcoder.jp/contests/tessoku-book/submissions/43954147)\n\n例题6:[problem:AtCoder-tessoku_book_v]\n\n给两个数组,当前位置为 $1$,有两种移动方式。\n\n- 进入 $a_i$ 获得 100。\n- 进入 $b_i$ 获得 150。\n\n问到 $n$ 的最大获得。\n\n\n\n- 数学\n\n- 技巧\n\n- 启发式\n\n- 数据结构\n\n- 图\n\n- 额外的技巧\n\n例题:\n\n给定一个长度为 $n$ 的数组,请你找出一个区间 $[l,r]$,满足以下条件:\n\n- $al\\ne \\min(a_l,a_{l+1},...,a_{r})$\n- $al\\ne \\max(a_l,a_{l+1},...,a_{r})$\n- $ar\\ne \\min(a_l,a_{l+1},...,a_{r})$\n- $ar\\ne \\max(a_l,a_{l+1},...,a_{r})$\n\n如果有多组可行解,输出任意一种,如果不存在这样的区间,输出 $−1$。\n\n这里给出一种方法,首先考虑 $(1,2,...,n)$ 这个区间,如果 $1$ 这个位置是最大值或者最小值,则右边去掉多少数字,都不是合法区间,因为 $1$ 已经是最大的了,或者是最小的。那么我们把 $1$ 这个位置删除,同理如果最右边是最大或者最小值我们也可以把它删除,最终留下的位置即合法区间,如果什么也没有留下,那么表示不存在这样的合法区间。使用 `multiset` 进行删除操作,计算量 $O(n\\log n)$。\n\ncode:[minmax_interval1](https://github.com/swapfloor/cp-beginner/blob/main/tags/bonus/minmax_interval1.cpp)\n\n第二种方法(我自己的土方法),前提是需要知道怎么求下一个数值更大的位置(方法:单调栈)。先求出下一个数值更大的位置 $ng$,下一个数值更小的位置 $nl$,上一个数值更大的位置 $pg$,上一个数值更小的位置 $pl$,设置一个树状数组求后缀中的最大合法左端点,然后枚举左端点,求右边有没有点的合法左端点在当前左端点的位置或者是右边的位置。求上述四个数组的计算量为 $O(n)$,枚举左端点需要 $n$ 次,每次使用树状数组的搜索需要 $O(log n)$,共需要 $O(n\\log n)$。\n\ncode:[minmax_interval2](https://github.com/swapfloor/cp-beginner/blob/main/tags/bonus/minmax_interval2.cpp)","threadId":152208,"likeCnt":0,"createTime":1690178868000,"isWorkbook":true,"viewCnt":242,"openness":2,"fav":false,"id":3873,"trustable":false}