比赛链接

A

题解

知识点：莫队，树状数组。

区间询问显然可以离线莫队，考虑端点移动对答案的影响。

不妨先考虑右端点右移一个位置，对答案的改变。假设右端点右移后在 $r$ ，我们先要知道 $[l,r-1]$ 中和 $a_r$ 相等的位置。对于每个这样的位置 $l'$ ，我们将 $[l',r-1]$ 中小于 $a_r$ 的数字个数加起来，就是右移的贡献。

我们可以先树状数组预处理出，对于每个点在它之前比它小的数字个数，记为 $les_i$ 。那么我们便可以简化最后一步的计算个数，最终答案就是 $\displaystyle \sum_{l':l' \in [l,r-1],a_{l'} = a_r} les_{r} - les_{l'}$ 。

我们发现其中 $les_r$ 是定值，若我们知道了 $[l,r-1]$ 中所有与 $a_r$ 相等的位置个数 $cnt_{a_r}$ ，那么总的贡献又可以变为 $cnt_{a_r} \cdot les_r - \displaystyle \sum_{l':l' \in [l,r-1],a_{l'} = a_r} les_{l'}$ ，因此我们可以同步维护 $cnt_i$ 表示 $[l,r]$ 中值为 $i$ 的数字个数。

同时，我们也可以同步维护 $sum_{i}$ 表示 $[l,r]$ 中所有值为 $i$ 的位置 $l'$ 的 $les_{l'}$ 的和，来直接得到最后一项求和。

类似的有其他三个操作：左端点左移、右端点左移、左端点右移。

注意，莫队分块的最佳大小是 $\dfrac{n}{\sqrt m}$ 。

时间复杂度 $O(n \sqrt m)$

空间复杂度 $O(n)$

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; template <class T>class Fenwick {    int n;    vector<T> node; public:    Fenwick(int _n = 0) { init(_n); }     void init(int _n) {        n = _n;        node.assign(n + 1, T());    }     void update(int x, T val) { for (int i = x;i <= n;i += i & -i) node[i] += val; }     T query(int x) {        T ans = T();        for (int i = x;i >= 1;i -= i & -i) ans += node[i];        return ans;    }    T query(int l, int r) {        T ans = T();        ans += query(r);        ans -= query(l - 1);        return ans;    }     int lower_bound(T val) {        int pos = 0;        for (int i = 1 << __lg(n); i; i >>= 1) {            if (pos + i <= n && node[pos + i] < val) {                pos += i;                val -= node[pos];            }        }        return pos + 1;    }    int upper_bound(T val) {        int pos = 0;        for (int i = 1 << __lg(n); i; i >>= 1) {            if (pos + i <= n && node[pos + i] <= val) {                pos += i;                val -= node[pos];            }        }        return pos + 1;    }};/// 树状数组，修改查询O(logn)，单点修改、前缀查询//* 修改操作需满足结合律，即满足线段树的lazy标记要求//* 任意区间查询只支持可以减法的运算//* 倍增查找只支持基本类型 int a[500007];int les[500007]; struct Query {    int l, r, id;}Q[500007]; int cnt[500007];ll sum_les[500007];ll cur; void add(int x, bool isLeft) {    ll res = 1LL * cnt[a[x]] * les[x] - sum_les[a[x]];    cnt[a[x]]++;    sum_les[a[x]] += les[x];    cur += (isLeft ? -1 : 1) * res;} void del(int x, bool isLeft) {    cnt[a[x]]--;    sum_les[a[x]] -= les[x];    ll res = 1LL * cnt[a[x]] * les[x] - sum_les[a[x]];    cur -= (isLeft ? -1 : 1) * res;} ll ans[500007]; int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);     int n, m;    cin >> n >> m;     Fenwick<int> fw(n);    for (int i = 1;i <= n;i++) {        cin >> a[i];        les[i] = fw.query(a[i] - 1);        fw.update(a[i], 1);    }     for (int i = 1;i <= m;i++) {        int l, r;        cin >> l >> r;        Q[i] = { l,r,i };    }     int B = n / sqrt(m);    sort(Q + 1, Q + m + 1, [&](Query a, Query b) {        if (a.l / B == b.l / B) return a.l / B & 1 ? a.r > b.r:a.r < b.r;        else return a.l / B < b.l / B;    });     int L = 1, R = 0;    for (int i = 1;i <= m;i++) {        auto [l, r, id] = Q[i];        while (L > l) add(--L, 1);        while (R < r) add(++R, 0);        while (L < l) del(L++, 1);        while (R > r) del(R--, 0);        ans[id] = cur;    }     for (int i = 1;i <= m;i++) cout << ans[i] << '\n';    return 0;}

B

题解

知识点：贪心，枚举，优先队列。

若 $k \leq 0$ ，当存在一个位置大于等于 $k$ 时，形成自环即可，逆序数为 $0$ ；否则所有位置一定小于 $0$ ，一定无解。接下来考虑 $k > 0$ 的情况。

我们先考虑全是正数的特殊情况，显然我们优先选择合法的连续区间 $[l,r]$ 的元素循环左移一次构造大环，其他位置构成自环，这样的逆序数是 $r-l$ ，可以证明是理论最优的，从中去掉某些元素会导致花费增大。这样，我们枚举所有区间构造是 $O(n^2)$ 的，用尺取法是 $O(n)$ 的。

现在问题包含了负数，尺取法就失效了，因为区间的和不具备单调性，但我们依旧可以枚举所有区间。不过，此时对于一个区间，有些位置我们是不能选的，否则就不合法了，因此选择的位置不再连续。我们先考虑不连续的位置产生的逆序数的最小值。

若在 $[l,r]$ 这个连续区间中选择了 $x$ 个数，我们可以将选中的位置对应的数循环左移一次，那么对于环上的元素相互产生了 $x-1$ 个逆序对，对于每个不在环上的元素都与环元素产生了 $2$ 个逆序对，即没被选择的点都额外产生了一个逆序对，这样产生的逆序数为 $r-l + (r-l+1-x)$ ，可以证明是理论最优的。

结合上面的结论，我们知道对于一个固定区间 $[l,r]$ ，选的数越多越好，这样贪心选择的方式就顺其自然的出现了：正数都选，随后负数选最大的直到不能再选。

这里，区间端点原则上是一定要选的，不然求出的答案会比真实答案要大。但对于这种情况的真实答案，其等价于一个更小区间的真实答案，因此即使舍弃导致求出错误答案，也不会使得最终答案错误，所以为了实现方便就允许存在这样的操作。

直接枚举每个区间取数的复杂度是 $O(n^3)$ 的。我们发现，对于每一个右端点，左端点从右到左的时候，区间长度一直在增加，那么当没被选择的数严格减小时答案才会更优，因此之前选过的负数是一定会被选上，否则没被选择的数一定比之前更大，答案不会更优。因此，用优先队列维护没被选择的负数即可，选过的就不需要考虑了。

时间复杂度 $O(n^2 \log n)$

空间复杂度 $O(n)$

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; int a[1000007];int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int n, k;    cin >> n >> k;    for (int i = 1;i <= n;i++) cin >> a[i];    if (k <= 0) {        bool ok = 0;        for (int i = 1;i <= n;i++) ok |= a[i] >= k;        if (ok) cout << 0 << '\n';        else cout << -1 << '\n';        return 0;    }     int ans = 1e9;    for (int i = 1;i <= n;i++) {        ll sum = 0;        priority_queue<int> pq;        for (int j = i;j >= 1;j--) {            if (a[j] >= 0) sum += a[j];            else pq.push(a[j]);            while (pq.size() && pq.top() + sum >= k) {                sum += pq.top();                pq.pop();            }            if (sum >= k) {                int sz = pq.size();                ans = min(ans, i - j + sz);            }        }    }    if (ans < 1e9) cout << ans << '\n';    else cout << -1 << '\n';    return 0;}

C

题解

知识点：图匹配，竞赛图。

将 $(x,y+n)$ 的关系转化为 $(x,y)$ ，那么原图会变为一个竞赛图，而原图的匹配关系则变为竞赛图的若干条不相交的路径。

首先竞赛图一定有一条哈密顿路径，因此答案至少为 $n-1$ 。

当且仅当每个点都在一个哈密顿回路时（每个点都在大于等于 $3$ 强连通分量内），答案才为 $n$ 。可以根据兰道定理：竞赛图强连通，当且仅当从小到大的度数序列的前缀和 $s[1,i]$ 严格大于 $\dbinom{i}{2}$ 。我们可以枚举度数序列，找到所有强连通分量。

时间复杂度 $O(n^2)$

空间复杂度 $O(n)$

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; int deg[3007];int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int n;    cin >> n;    for (int i = 1;i <= n;i++)        for (int j = 1;j <= n;j++) {            int x;            cin >> x;            deg[i] += x;        }     // (x,y+n)看为(x,y)的边，可转化为竞赛图    // 竞赛图必有哈密顿路径答案至少为n - 1，当且仅当所有点可以在大于等于3的环中时答案为n    /// 兰道定理：一个序列是竞赛图的分数序列当且仅当度数序列前缀和s[1,i]大于等于C(i,2)，i=n时等于    /// 兰道定理：竞赛图强连通当且仅当度数序列前缀和s[1,i]严格大于C(i,2)    sort(deg + 1, deg + n + 1);    int s = 0;    for (int i = 1, j = 0;i <= n;i++) {        s += deg[i];        if (s == i * (i - 1) / 2) { // 此时不强连通            if (i - j <= 2) { // [j,i)的点是强连通的，若小于等于2则不能成环，                cout << n - 1 << '\n';                return 0;            }            j = i;        }    }    cout << n << '\n';    return 0;}

D

题解

知识点：因数集合。

由条件 $b \mid c$ ，我们枚举所有 $c$ 的因数，可以求出 $a$ ，最后验证一下即可。

时间复杂度 $O(\sqrt c)$

空间复杂度 $O(\sqrt c)$

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; void get_factor(int n, vector<int> &factor) {    for (int i = 1;i * i <= n;i++) {        if (!(n % i)) {            factor.push_back(i);            if (i != n / i) factor.push_back(n / i);        }    }} bool solve() {    int k, c, n;    cin >> k >> c >> n;     vector<int> factor;    get_factor(c, factor);     int ans = 0;    for (auto b : factor) {        if ((c - b) % k) continue;        int a = (c - b) / k;        if (a <= 0 || gcd(a, b) < n) continue;        ans++;    }    cout << ans << '\n';    return true;} int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int t = 1;    cin >> t;    while (t--) {        if (!solve()) cout << -1 << '\n';    }    return 0;}

E

题解

知识点：递归，分治。

不难发现区间的嵌套关系是一个树状结构，天然满足递归的性质，我们把每个不被约束的数字单独看作一个约束区间方便实现。

对于一个约束区间 $[l,r]$ ，分类讨论：

1. 若没有子约束，若要求奇数，我们随便交换两个即可，否则不用交换。

2. 若有子约束，统计子约束的影响，若和自己同奇偶则无需改动，否则随意选两个相邻约束区间，取左边的最大值和右边的最小值交换即可。

时间复杂度 $O(m(n+m))$

空间复杂度 $O(m)$

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; int n, m;array<int, 3> seg[1007];int p[1007], cnt; void dfs(int l, int r, int w = -1) {    if (l == r) {        p[l] = ++cnt;        return;    }    int pos = l, wsum = 0;    vector<pair<int, int>> sub_seg;    for (int i = 1;i <= m;i++) {        auto [l1, r1, w1] = seg[i];        if (pos <= l1 && r1 <= r && (w == -1 || r1 - l1 + 1 < r - l + 1)) {            while (pos < l1) {                dfs(pos, pos, -1);                sub_seg.push_back({ pos,pos });                pos++;            }            sub_seg.push_back({ l1,r1 });            dfs(l1, r1, w1);            pos = r1 + 1;            wsum ^= w1;        }    }    while (pos <= r) {        dfs(pos, pos, -1);        sub_seg.push_back({ pos,pos });        pos++;    }    if (w != -1 && w != wsum) {        auto [l1, r1] = sub_seg[0];        auto [l2, r2] = sub_seg[1];        int x = find(p + l1, p + r1 + 1, r1) - p;        int y = find(p + l2, p + r2 + 1, l2) - p;        swap(p[x], p[y]);    }} int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    cin >> n >> m;    for (int i = 1;i <= m;i++) {        int l, r, w;        cin >> l >> r >> w;        seg[i] = { l,r,w };        if (l == r && w) {            cout << -1 << '\n';            return 0;        }    }    sort(seg + 1, seg + m + 1, [&](auto a, auto b) { return a[0] == b[0] ? a[1] > b[1]:a[0] < b[0];});     dfs(1, n);     for (int i = 1;i <= n;i++) cout << p[i] << " \n"[i == n];    return 0;}

G

题解

知识点：双指针。

尺取法枚举区间即可。

时间复杂度 $O(n)$

空间复杂度 $O(n)$

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; int a[100007];int cnt[5];int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int n, k;    cin >> n >> k;    for (int i = 1;i <= n;i++) cin >> a[i];     int ans = 1e9;    int l = 1, r = 1;    while (l <= n) {        while (r <= n) {            if (cnt[1] && cnt[2] && cnt[3] && cnt[4] >= k) break;            cnt[a[r]]++;            r++;        }        if (cnt[1] && cnt[2] && cnt[3] && cnt[4] >= k) ans = min(ans, r - l);        cnt[a[l]]--;        l++;    }    cout << ans << '\n';    return 0;}

H

题解

知识点：贪心，背包dp。

注意到背包大小是递增的，因此我们考虑后 $min(n,m)$ 个背包即可。

一个显然的方法是，考虑了前 $i$ 次，共处理前 $j$ 个奶酪的最大价值。但这样，转移时我们要枚举最后一次处理了多少奶酪，并进行背包dp，复杂度是 $O(n^3 \max\{sz_i\})$ 的。

我们可以考虑预处理区间 $[i,j]$ 且背包大小是 $k$ 时的最大价值，复杂度是 $O(n^2 \max\{sz_i\})$ 的，而对于之前的转移复杂度就变为 $O(n^3)$ 了。

时间复杂度 $O(n^2 \max\{ sz_i \} + n^3)$

空间复杂度 $O(m+n^2 \max\{sz_i\})$

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; int a[207], b[207];int sz[100007];ll f[207][207][207];ll g[207][207];int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int n, m;    cin >> n >> m;    for (int i = 1;i <= n;i++) cin >> a[i] >> b[i];    for (int i = 1;i <= m;i++) cin >> sz[i];     for (int i = 1;i <= n;i++) {        for (int j = i;j <= n;j++) {            for (int k = 0;k <= sz[m];k++) {                f[i][j][k] = f[i][j - 1][k];                if (k >= a[j]) f[i][j][k] = max(f[i][j][k], f[i][j - 1][k - a[j]] + b[j]);            }        }    }    reverse(sz + 1, sz + m + 1);    m = min(m, n);    reverse(sz + 1, sz + m + 1);    for (int i = 1;i <= m;i++) {        for (int j = 0;j <= n;j++) {            for (int k = 0;k <= j;k++) {                g[i][j] = max(g[i][j], g[i - 1][j - k] + f[j - k + 1][j][sz[i]]);            }        }    }    cout << g[m][n] << '\n';    return 0;}

I

题解

知识点：位运算，线性dp。

先预处理前缀异或和方便处理，并考虑按位计算贡献。

我们先考虑一个简单的问题，求出所有子区间的异或和的和，与蓝桥杯省赛的一道题完全一致。朴素求所有子区间，最暴力的就是 $O(n^3)$ 选完再求，稍微优化一点是 $O(n^2)$ 枚举右端点左端点可以递推，但实际左端点的递推过程也可以 $O(1)$ 解决，因此最佳复杂度就是 $O(n)$ 的，具体解法如下。

枚举固定的右端点 $r$ ，若一个位置 $l-1$ 使得 $[1,l-1]$ 的异或和第 $k$ 位和 $[1,r]$ 的异或和第 $k$ 位不同，那么 $[l,r]$ 的异或和第 $k$ 位为 $1$ ，就会在以 $r$ 为右端点的这个状态产生 $2^k$ 的贡献。

因此，我们考虑维护 $[1,r-1]$ 所有前缀（可以为空）异或和第 $k$ 位的 $0,1$ 个数 $sum_{k,0/1}$ ，便可轻松获得前缀与 $[1,r]$ 的异或和第 $k$ 位不同的个数。例如$[1,r]$ 的异或和第 $k$ 位为 $1$ ，那么贡献就是 $2^k \cdot sum_{k,0}$ 。最后，把 $[1,r]$ 的异或和的每位情况加到 $sum$ 即可。此时，我们可以得到以 $r$ 为右端点的所有子区间的异或和。

对于这个简单问题，我们直接加到答案里即可。但为了原来问题的处理，我们考虑求 $f_i$ 表示右端点小于等于 $i$ 的所有子区间的异或和之和。这个只需要求出以 $r$ 为右端点的所有子区间的异或和后保存在 $f_r$ ，最后枚举完所有右端点后做前缀和即可。

回到原来的问题，发现其实就是分段求异或和再乘起来，求所有情况的和。问题与 $k$ 子段问题非常相似，考虑线性dp。设 $f_{i,j}$ 表示分了 $i$ 段，且所有区间右端点小于等于 $j$ 时的答案，状态顺序交换也是可以写的，不过会麻烦一点。 $i=1$ 时，$f_{1,j}$ 即上述简单问题最终答案，其实之后的递推思路是完全类同的。

当分了 $i$ 段时，枚举第 $i$ 段固定的右端点 $j$ ，若一个位置 $l-1$ 使得 $[1,l-1]$ 的异或和第 $k$ 位和 $[1,j]$ 的异或和第 $k$ 位不同，那么 $[l,j]$ 的异或和第 $k$ 位为 $1$ ，就会在分了 $i$ 段最后一段以 $j$ 为右端点的这个状态（不是 $f_{i,j}$）产生 $2^k \cdot f_{i-1,l-1}$ 的贡献。

因此，我们考虑维护 $[1,j-1]$ 所有前缀（可以为空）分了 $i-1$ 段且异或和的第 $k$ 位为 $0,1$ 时的总贡献 $sum_{k,0/1}$ ，便可轻松获得前缀与 $[1,j]$ 的异或和第 $k$ 位不同时，前缀分了 $i-1$ 段的总贡献。例如$[1,r]$ 的异或和第 $k$ 位为 $1$ ，那么贡献就是 $2^k \cdot sum_{k,0}$ 。最后，根据 $[1,j]$ 的异或和每位情况，将 $f_{i-1,j}$ 加到 $sum$ 即可。此时，我们可以得到分了 $i$ 段，且最后一段以 $j$ 为右端点的答案。我们对其做前缀和即可得到 $f_{i,j}$ 。

这类问题最关键的是，枚举右端点时，将左端点的 $O(n)$ 递推，根据异或的性质优化为对每位贡献的 $O(1)$ 求和，即拆位求和的优化。

时间复杂度 $O(n)$

空间复杂度 $O(n)$

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; const int P = 998244353;int a[200007];int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int n;    cin >> n;    for (int i = 1;i <= n;i++) cin >> a[i], a[i] ^= a[i - 1];     vector<int> f(n + 1, 1);    for (int i = 1;i <= 3;i++) {        vector<int> g(n + 1);        array<array<int, 2>, 30> sum{};        for (int j = 0;j <= n;j++) {            for (int k = 0;k < 30;k++) {                (g[j] += (1LL << k) * sum[k][~(a[j] >> k) & 1] % P) %= P;                (sum[k][(a[j] >> k) & 1] += f[j]) %= P;            }        }        for (int j = 1;j <= n;j++) (g[j] += g[j - 1]) %= P;        swap(f, g);    }    cout << f[n] << '\n';    return 0;}