356

学习：二进制枚举以及加强搜索，pbds，缩点思想。

A - Subsegment Reverse

给你正整数 $N$ 、 $L$ 和 $R$ 。
对于长度为 $N$ 的序列 $A=(1,2,\dots ,N)$ ，翻转 $[L,R]$ 区间的数字。
打印操作后的序列。

void solve() {
    int n, l, r;cin >> n >> l >> r;
    vector<int>a(n + 1);
    for (int i = 1;i <= n;i++)a[i] = i;
    reverse(a.begin() + l, a.begin() + r + 1);
    for (int i = 1;i <= n;i++)cout << a[i] << " ";
}

B - Nutrients

高桥非常注重健康，他担心自己是否从饮食中摄入了足够的 $M$ 营养素。

对于 $i$ /-种营养素，他的目标是每天至少摄入 $A_i$ 个单位。

今天，他吃了 $N$ 种食物，从 $i$ 种食物中摄入了 $X_{i,j}$ 单位的营养素 $j$ 。

确定他是否达到了所有 $M$ 种营养素的目标。

模拟：

#define int long long
int s[110][110];
void solve() {
    int n, m;cin >> n >> m;
    vector<int> a(m + 1);
    for (int i = 1;i <= m;i++)cin >> a[i];
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> s[i][j];
        }
    }
    for (int i = 1;i <= m;i++) {
        int sum = 0;
        for (int j = 1;j <= n;j++) {
            sum += s[j][i];
        }
        if (sum < a[i]) {
            cout << "No\n";return;
        }
    }
    cout << "Yes\n";
}

C - Keys

你有 $N$ 个编号为 $1,2,\dots ,N$ 的密钥。
其中一些是真钥匙，其他的是假钥匙。

有一扇门，门 X，你可以插入任意数量的钥匙。只有插入至少 $K$ 把真钥匙，X 门才会打开。

你已经对这些钥匙进行了 $M$ 次测试。 $i$ 次测试的结果如下：

• 您将 $C_i$ 把 $A_{i,1},A_{i,2},\dots ,A_{i,C_i}$ 把钥匙插入了 X 号门。
• 测试结果用一个英文字母 $R_i$ 表示。
  • $R_i=$ o 表示在 $i$ -th 测试中门 X 打开了。
  • $R_i=$ x 表示在 $i$ -th测试中门X没有打开。

有 $2^N$ 种可能的钥匙组合，其中哪些是真钥匙，哪些是假钥匙。在这些组合中，找出与任何测试结果都不矛盾的组合数。
给定的测试结果有可能是错误的，没有一个组合满足条件。在这种情况下，报告 $0$ 。

根据题目意思就是让枚举钥匙的所有可能性，对于每一种可能性带入给定的条件看是否满足，若满足计为一种答案

DFS / 二进制枚举：时间复杂度：$O(2^{n}nm)<5e7$

int a[110][20];
void solve() {
    int n, m, tar;cin >> n >> m >> tar;
    vector<int> c(m + 1), is(m + 1);
    for (int i = 1;i <= m;i++) {
        cin >> c[i];
        for (int j = 1;j <= c[i];j++) {
            cin >> a[i][j];
        }
        char op;cin >> op;
        is[i] = (op == 'o');
    }
    int ans = 0;
    for (int i = 0;i < (1 << n);i++) {
        vector<int> pan(n + 1);
        for (int j = 0;j < n;j++) {
            if (i & (1 << j)) {
                pan[j + 1] = 1;
            }
        }
        int ok = 1;
        for (int j = 1;j <= m;j++) {
            int sum = 0;
            for (int k = 1;k <= c[j];k++) {
                if (pan[a[j][k]])sum++;
            }
            if (sum >= tar && !is[j]) ok = 0;
            if (sum < tar && is[j]) ok = 0;
        }
        if (ok)ans++;
    }
    cout << ans << '\n';
}

D - Masked Popcount

给定整数 $N$ 和 $M$ ，计算和 ${\displaystyle \sum _{k=0}^N}$ $\mathrm{p}\mathrm{o}\mathrm{p}\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}$ $(k\mathrm{\&}M)$ . modulo $998244353$ 。

位运算：
根据 $\mathrm{\&}$ 的性质，只有两个都为 1 时 $\text{popcount}$ 才会增加，所以只需要枚举 $M$ 为 1 的位

区间 $[0,n]$ 之间若在第 $i$ 位，发现是 $2^n$ 个 0 和 $2^n$ 个 1 交替的(即周期位 $2^{i+1}$)，可以先算出 $n$ 覆盖了多少个周期，在最后一个周期内又覆盖了多少个 1

很容易计算：对于第 $i$ 位：${\displaystyle \text{ans=}\lfloor \frac{n}{2^{i+1}}\rfloor +[(nmod{2}^{i+1})-2^i][nmod{2}^{i+1}>2^i]}$

$n+1$ 是因为这里算的个数是将 0 算入了，则后面少算了一位需要补上。

#define int long long
constexpr int mod = 998244353;
void solve() {
    int n, m;cin >> n >> m;
    int sum = 0;
    n++;
    for (int i = 0;i <= __lg(m);i++) {
        if ((m >> i) & 1) {
            int x = n / (1ll << (i + 1));
            int y = n % (1ll << (i + 1));
            sum = (sum + x * (1ll << i) + max(y - (1ll << i), 0ll)) % mod;
        }
    }
    cout << sum << '\n';
}

E - Max/Min

给定 $A$ 数组，计算：${\displaystyle \sum _{i=1}^N\sum _{j=i+1}^N\lfloor \frac{max(A_i,A_j)}{min(A_i,A_j)}\rfloor }$

当某个数字相同的个数为 $x$ 时，答案就是 $\frac{x(x-1)}{2}$

当两个数不同时，对于 $x$,当 $y\in [kx,(k+1)x-1]$ 答案就是 $k$。

先用一个数组 $c_i$ 表示 $i$ 在 $a$ 数组中有多少个，用 $s_i$ 表示 $c_i$ 前缀和 $s_r-s_{l-1}$ 表示在 $[l,r]$ 中的数字个数

对于每个 $x\in [1,M]$，枚举 $x$ 的倍数，看区间 $[kx,(k+1)x-1]$，即 $V=s_{(k+1)x-1}-s_{kx-1}$，对于这种情况：$V\times k\times c_x$

jiangly:

void solve() {
    int n;cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    const int M = *max_element(a.begin(), a.end());

    vector<int> c(M + 1);
    for (auto x : a) {
        c[x]++;
    }

    vector<int> s(M + 1);
    for (int i = 1; i <= M; i++) {
        s[i] = s[i - 1] + c[i];
    }

    int ans = 0;
    for (int x = 1; x <= M; x++) {
        ans += c[x] * (c[x] - 1) / 2;
        for (int y = x; y <= M; y += x) {
            int v = s[min(y + x - 1, M)] - s[max(x, y - 1)];
            ans += c[x] * v * (y / x);
        }
    }
    cout << ans << "\n";
}

F - Distance Component Size Query

给你一个整数 $K$ 。对于初始为空的集合 $S$ ，请依次处理以下两种类型的 $Q$ 查询：

• 1 x: 给出一个整数 $x$ 。如果 $x$ 在 $S$ 中，则从 $S$ 中删除 $x$ 。否则，在 $S$ 中加入 $x$ 。
• 2 x: 给出一个在 $S$ 中的整数 $x$ 。考虑一个图，图中的顶点是 $S$ 中的数，且当且仅当两个数之间的绝对差最多为 $K$ 时，这两个数之间有一条边。请打印包含 $x$ 的连通部分中的顶点数。

_pbds 中的平衡树

主要思路就是建立两个集合，一个记录现在的集合，一个记录缩点后的集合。

缩点就是将每个联通块且将最大的数字缩成一个点。

这样之后若要查询 x 连通块的大小，则就是这个连通块在第一个集合中的位置减去上一个连通块在第一个集合中的位置。

ordered_set<int> s1;set<int> s2;  // s1是所有点的点集  s2会把一个连通块的点缩成最大那个点
// （s1要求rank，所以必须用PBDS,s2普通set也可以）

void solve() {
    ll q, k;cin >> q >> k;
    // 这里插几个哨兵是为了方便出题，边界上的prev next 就能统一了
    s1.insert(-4e18), s1.insert(4e18);
    s2.insert(-4e18), s2.insert(4e18);
    while (q--) {
        ll op, x;cin >> op >> x;
        if (op == 1) {
            if (s1.find(x) == s1.end()) {
                auto it = s1.insert(x).first;
                ll w1 = *prev(it), w2 = *next(it);  // x左右两个点编号
                if (x - w1 <= k) s2.erase(w1);
                if (w2 - x <= k)
                    ;  // x就不用插入s2了
                else
                    s2.insert(x);
            } else {
                auto it = s1.find(x);
                ll w1 = *prev(it), w2 = *next(it);  // x左右两个点编号
                s1.erase(x), s2.erase(x);           // x在s2里不存在也没影响
                if (w2 - w1 > k) s2.insert(w1);     // 让w1复活 （原来是活的也不影响）
            }
        } else {
            auto it = s2.lower_bound(x);  // 找到x所在连通块最大的点
            cout << s1.order_of_key(*it) - s1.order_of_key(*prev(it)) << '\n';
        }
    }
}