D - Cross Explosion

考察对Set的使用，尤其是prev函数

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<bool>> st(n + 1, vector<bool>(m + 1, false));
    vector<set<int>> u(m + 2), d(m + 2), l(n + 2), r(n + 2);
    for (int i = 0; i <= n + 1; i ++ )
        for (int j = 0; j <= m + 1; j ++ ){
            l[i].insert(j), r[i].insert(j);
            u[j].insert(i), d[j].insert(i);
        }

    auto gao = [&](int x, int y){ //爆破函数
        st[x][y] = true;
        l[x].erase(y);
        r[x].erase(y);
        u[y].erase(x);
        d[y].erase(x);
    };

    int q;
    cin >> q;
    int cnt = 0;
    while (q -- ){
        int x, y;
        cin >> x >> y;
        if (!st[x][y]){
            gao(x, y);
        }else{
            //4个方向
            //右
            auto ir = r[x].upper_bound(y),
                il = prev(l[x].upper_bound(y)),
                iu = prev(u[y].upper_bound(x)),
                id = d[y].upper_bound(x);
            if (*ir >= 1 && *ir <= m) {
                gao(x, *ir);
            }
            if (*il >= 1 && *il <= m){
                gao(x, *il);
            }
            if (*iu >= 1 && *iu <= n){
                gao(*iu, y);
            }
            if (*id >= 1 && *id <= n){
                gao(*id, y);
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            ans += !st[i][j];
    cout << ans;
}

E - Avoid K Partition

考虑dp
dp[i]表示只考虑前i个并以第i个结尾的方案数
可以枚举前一个分界点来进行N^2的暴力转移
if ()
dp[i] += dp[j] (j < i && sum[i] - sum[j] != K)
统计满足 $sum[j] != sum[i] - K$ 太难，因为左边是变量
不妨反向统计 $sum[i] - sum[j] = K$
那么 $sum[j] = sum[i] - K$
然后用总数减去不合法j的方案数。
map记录sum[i]
思考：典型的01分类讨论，DP优化题目，记得初始化空集

#define int long long
const int mod = 998244353;

void solve(){
    int n, K;
    cin >> n >> K;
    int f[n+1] = {};
    int S = 1, sum = 0; // 
    map<int, int> mp;
    mp[0] = 1;
    for (int i = 1; i <= n; i ++ ){
        int x;
        cin >> x;
        sum += x;
        f[i] = ((S - mp[sum - K]) % mod + mod) % mod;
        S += f[i], S %= mod;
        mp[sum] = (mp[sum] + f[i]) % mod;
    }
    cout << f[n];
}

F - Dividing Game

注意到是求最小的最大值 $x$,经典二进制搜索
对于每次搜索
枚举 $i:1-n$ 作为起点的可行性。由于是环，所以经典做法——数组加倍数组拉开环。
对于起点 $i$：
如何走一步到 $j$ 使得总操作尽量可行,经典贪心思路: $找到满足[i, j] \geq x 的最小j$
因为 $k$ 人，所以进行 $k$ 次操作就能判断是否可行。
但是时间上是 $N^2$,需要优化。
思考优化走的操作,经典倍增—— $f[i][j]代表i进行2^j分割能到达的位置$
时间就从 $k 优化到 logk$
真正难点
思考不作为分割点的数目如何求，只要检查起点可行的数目，在用总数相减即可。
结论：如果一个位置作为起点不会被切割，也不会在其他位置作为起点的时候被切割，画图感性理解一下。

#define int long long
const int N = 2e5 + 10, inf = 1e9;

int n, k;
int a[N * 2], f[N * 2][31];

int check(int x)
{
    int q = 0, r = 0;
    for (int i = 1; i <= n * 2; i++)
    {
        while (q < x && r < n * 2){
            q += a[++r];
        }
        if (q >= x){
            f[i][0] = r;
        }
        else{
            f[i][0] = inf;
        }
        q -= a[i];
    }
    // 倍增
    for (int j = 1; j <= 30; j++)
        for (int i = 1; i <= n * 2; i++)
            if (f[i][j - 1] + 1 <= n * 2 && f[f[i][j - 1] + 1][j - 1] <= n * 2)
                f[i][j] = f[f[i][j - 1] + 1][j - 1];
            else
                f[i][j] = inf;
    int res = 0;
    // 求方案数
    for (int i = 1; i <= n; i++)
    {
        int px = i;
        for (int j = 30; j >= 0; j -- )
        {
            if (k >> j & 1){
                px = f[px][j] + 1;
            }
            if (px > i + n)
                break;
        }
        if (px <= i + n){
            ++ res;
        }
    }
    return res;
}

void solve()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        a[i + n] = a[i];
    }
    int l = 0, r = 2e9;
    while (l < r){
        int mid = (l + r + 1) / 2;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << l << ' ' << n - check(l) ;
}