class Solution {
public:
    vector<string> country = {"", "+*-", "+**-", "+***-"};

    string maskPII(string s) {
        int at = s.find("@");
        if (at != string::npos) {
            transform(s.begin(), s.end(), s.begin(), ::tolower);
            return s.substr(0, 1) + "*****" + s.substr(at-1);
        }
        s = regex_replace(s, regex("[^0-9]"), "");
        return country[s.size()-10] + "***-***-" + s.substr(s.size()-4);
    }
};

整体二分是一种在省选~NOI难度中常用的技巧，其一般思想为：将询问离线，对所有询问同时进行二分，在二分的过程中逐渐将询问分为 “答案在 $[l, mid]$ 中的” 和 “答案在 $[mid+1, r]$ 中的” 两类，直到区间长度变为 $1$。
对比 CDQ分治 是基于对时间进行分治，而整体二分是基于对值域进行分治。

一般来说整体二分并不是必需的技巧，但对于数据结构水平较差，或码力不足的选手，整体二分能够显著降低一些数据结构题目设计数据结构、思维和代码实现等各个方面的难度。

为此，整体二分依然是省选~NOI水平的OI选手值得掌握的技巧。

例题1

有一个长度为 $n$ 的序列，序列的每个位置维护一个无序数组（可重集合）。

有 $m$ 个操作，操作有以下两种：

• 将区间 $[l, r]$ 中每个集合加上一个数 $c$
• 询问将区间 $[l, r]$ 中所有集合并起来后，第 $k$ 小的数

限制：

• $n, m, c \leqslant 50000$
• $k \leqslant 2.5 \times 10^9$

分析：

本题和动态区间第 $k$ 小问题类似，区间在于每个位置存储的数的数量不再是一个。同时本题仍然可以作为 树套树 的练习题，但需要对标记永久化等技巧有较好的理解。

我们现在考虑如何使用整体二分来解决本题。

将所有的操作（包括修改与询问）离线，在值域上二分。

设当前二分的区间是 $[l, r]$，中点是 $mid$，扫描所有操作：

• 如果是修改操作，且加入的值 $c < mid$，那么将修改操作对应的区间 +1，然后修改操作加入左区间。否则，修改操作加入右区间。
• 如果是询问操作，查询询问的区间和 $sum$，若 $sum < k$，则加入左区间。否则，k -= sum，询问加入右区间。

其中，区间加、区间求和操作可以使用一颗线段树来维护。

总时间复杂度为 $O((n+m)\log n \log c)$。($\log n$ 是线段树单次修改时间复杂度，$\log c$ 是二分层数，也等于每个操作（修改或询问)被应用的次数上界）

算法分析

首先 $A_1$ 显然有 $P-1$ 种选择，对于之后的选法，由于 $A_1 + A_2 + \cdots A_i \not\equiv 0 \pmod P$，所以总是有一个数不能选，那么每个数就有 $P-2$ 种选择。

于是，最后的答案就是 $(P-1)\cdot (P-2)^{N-1}$

C++ 代码

#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif

using namespace std;
using mint = modint1000000007;

int main() {
    int n, p;
    cin >> n >> p;

    mint ans = p-1;
    ans *= mint(p-2).pow(n-1);
    cout << ans.val() << '\n';

    return 0;
}

算法分析

可以考虑对答案进行枚举
注意到，若存在 $\gcd(x, y) = d$，则在 $A \sim B$ 之间至少存在两个数是 $d$ 的倍数
于是，我们可以找到不超过 $B$ 的 $d$ 的最大倍数 $x$，然后判断是否满足 $x-i \geqslant A$ 即可！

C++ 代码

a, b = map(int, input().split())
ans = 0
for d in range(1, 200001):
    x = b//d*d 
    if x-d >= a:
        ans = d
print(ans)

import math
t = int(input())
for _ in range(t):
    a, b = map(int, input().split())
    print(math.gcd(a, b))

class Solution {
public:
    int longestSubsequence(string s, int k) {
        reverse(s.begin(), s.end());
        int res = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '0') ++res;
            else if (i < 30) {
                if (k >= (1<<i)) {
                    ++res;
                    k -= 1<<i;
                }
            }
        }
        return res;
    }
};

算法

(模拟)

Python 代码

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

ans = []
for x in a:
    if x not in b:
        ans.append(x)
for x in b:
    if x not in a:
        ans.append(x)
ans.sort()
print(*ans)

class Solution:
    def kItemsWithMaximumSum(self, numOnes: int, numZeros: int, numNegOnes: int, k: int) -> int:
        res = min(k, numOnes)
        k -= min(k, numOnes)
        k -= min(k, numZeros)
        res -= k 
        return res

算法

(模拟)

假设答案为 $ans$

根据题意，则有 $\frac{ans}{Z} < \frac{Y}{X}$
$\Rightarrow ans \cdot X < YZ \Rightarrow ans \cdot \leqslant YZ-1 \Rightarrow ans \leqslant \frac{YZ-1}{X}$

Python 代码

x, y, z = map(int, input().split())
print((y*z-1)//x)

class Solution:
    def maxWidthOfVerticalArea(self, points: List[List[int]]) -> int:
        points.sort()
        res = 0
        for i in range(1, len(points)):
            res = max(res, points[i][0]-points[i-1][0])
        return res