251018 模拟赛

T1 matrix

请你构造一个非负整数组成的 \(n\) 阶方阵，满足对任意的 \(1\le i\le n\)，第 \(i\) 行和第 \(i\) 列的 \(\operatorname{mex}\) 都同时为 \(f_i\)。其中 \(f_i\) 是给定的序列，满足 \(1\le f_i\le i\)。可以证明一定有解。

\(n\le 2000\)

考虑钦定矩阵沿主对交线轴对称。由于 \(a_{1,1}=0\)，那么第一行的其他数字只能取 \(0,2,3,4,\cdots\)；第二列的 \(1\) 只能填在第二行了，那么 \(a_{2,2}=1,~a_{1,2}=0\)，第二行的其他数字只能取 \(0,3,4,5,\cdots\)；第三列的 \(1\) 只能填在第三行，\(2\) 只能填在第一行，\(3\) 只能填在第二行...找找规律，我们可以得到一个如下的构造：

0 0 2 2 2 2
. 1 0 3 3 3
. . 1 0 4 4
. . . 1 0 5
. . . . 1 0
. . . . . 1

这个构造有一个好处，就是主对交线下方的数无论如何也不会影响一列的 \(\operatorname{mex}\)。因此对每一列只需要根据 \(f_i\) 填主对交线上方的数字即可。

T3 journey

给你 \(n\) 个字符串 \(S_{1\sim n}\)，均由小写英文字母组成。定义 \(f(i,j)\) 表示考虑前 \(i\) 个字符串，将它们划分为若干组，每组恰好包含 \(j\) 个串（一个串最多被包含在一组中，可以不被包含），各组的 \(\operatorname{LCP}\) 长度之和的最大值。

对于每个 \(i\in [1,n]\)，求出 \(\bigoplus_{j=1}^{i}f(i,j)\times j\)。

\(n\le 5\times 10^5,~\sum|S_i|\le 10^6\)

考虑一个 \(f(i,j)\) 如何求出。\(\operatorname{LCP}\) 可以用 Trie 树刻画，因此先把前 \(i\) 个字符串上树，那么一组的贡献就是各字符串 \(\operatorname{LCA}\) 深度。考虑树上贪心，贪心的将子树中没匹配的字符串尽可能匹配，因为拆掉子树中已经匹配的组肯定更劣。

然而这样还是不好做。考虑将一组的 \(\operatorname{LCA}\) 的贡献拆到根链的所有点上，这样容易得到一个点的贡献是 \(\lfloor\frac{sz[u]}{j}\rfloor\)。新加一个字符串，更新路径上的 \(sz\)，也只会对 \(sz[u]\) 的因数有贡献。\(d\) 的前缀和显然是 \(O(n\log n)\) 级别的，因此总复杂度就是 \(\sum|S_i|\log n\)。

代码

#include<iostream>
#include<vector>
using namespace std;
const int N = 5e5 + 10;
const int S = 1e6 + 10;

int n;
string s;

vector<int> fac[N];
int ans[N], sum;

int chd[S][26], sz[S], nn;

void add(int p, int v) {
    sum ^= (ans[p] + v) ^ ans[p];
    ans[p] += v;
}

void insert(string &s) {
    int cur = 0;
    for(int i = 0; i < s.size(); i++) {
        int c = s[i] - 'a';
        if(!chd[cur][c]) chd[cur][c] = ++nn;
        cur = chd[cur][c];
        sz[cur]++;
        for(int j : fac[sz[cur]]) add(j, j);
    }
}

int main() {

    freopen("journey.in", "r", stdin);
    freopen("journey.out", "w", stdout);

    cin >> n >> n;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; i * j <= n; j++) {
            fac[i * j].push_back(i);
        }
    }
    for(int i = 1; i <= n; i++) {
        cin >> s;
        insert(s);
        cout << sum << endl;
    }

    return 0;
}

T4 daybreak

给定一个整数矩阵，大小 \(n\times m\)。你需要维护 \(q\) 次操作，每次操作是两种形式之一：

• 全局加 \(x\)；
• 单点修改 \(a_{x,y}\gets z\)；

每次修改之后，你需要回答一个问题：只保留 \(>0\) 的位置，矩阵会形成多少个四连通连通块？

另外，这里保证在任意时刻，对于矩阵中任意一个不在边界上的位置，四连通的四个数字中总有一个严格小于自己的值。

\(n,m\le 1000,~q\le 10^5\)

add 操作显然就是记一个 \(offset\)，等价于询问 \(\ge offset\) 的点的答案。直接做显然没啥前途。考虑拆连通块的贡献，考虑欧拉定理：

平面图欧拉定理

对于一个平面图，记点的数量为 \(V\)，边的数量为 \(E\)，面的数量为 \(F\)（不算最外面的一个面），连通块的数量为 \(G\)，那么

\[ V+F=E+G \]

证明考虑加一个点或者一条边，然后进行归纳。

其中 \(\ge offset\) 的点数、边数显然容易维护。对于面数，考虑还没用到的性质：这个性质告诉我们，矩阵内部不存在极小值。因此，每一个连通块中间不会存在气泡。因此一个面只可能是一个 \(1\times 1\) 的小矩形。离散化之后用 BIT 简单维护即可。

代码

#include<iostream>
#include<vector>
#include<algorithm>
#define int long long
using namespace std;
const int N = 1010;
const int Q = 1e5 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;

struct Op {
    int op, x, y, z;
};

int n, m, nq;
int a[N][N];
int b[N][N][2], c[N][N];

vector<Op> q;

int num[N * N + Q], nn;
void lisanhua() {
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) num[++nn] = a[i][j];
    }
    int offset = 0;
    for(Op &o : q) {
        if(o.op == 0) num[++nn] = (o.z -= offset);
        else offset += o.x;
    }
    sort(num + 1, num + 1 + nn);
    nn = unique(num + 1, num + 1 + nn) - (num + 1);
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) a[i][j] = lower_bound(num + 1, num + 1 + nn, a[i][j]) - num;
    }
    for(Op &o : q) {
        if(o.op == 0) o.z = lower_bound(num + 1, num + 1 + nn, o.z) - num;
    }
}

namespace BIT {
    int sum[N * N + Q];
    inline void insert(int p, int v) {
        for(int i = 1; i <= nn + 2; i += i & -i) sum[i] += v;
        for(int i = p + 1; i <= nn + 2; i += i & -i) sum[i] -= v;
    }
    inline int query(int p) {
        int res = 0;
        for(int i = p; i > 0; i -= i & -i) res += sum[i];
        return res;
    }
}

signed main() {

    freopen("daybreak.in", "r", stdin);
    freopen("daybreak.out", "w", stdout);

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> n >> m >> nq;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    for(int i = 1; i <= nq; i++) {
        string op; int x, y, z;
        cin >> op;
        if(op == "add") {
            cin >> x;
            q.push_back({1, x});
        } else {
            cin >> x >> y >> z;
            q.push_back({0, x, y, z});
        }
    }

    lisanhua();
    num[++nn] = INF;

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) BIT::insert(a[i][j], 1);
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j < m; j++) b[i][j][0] = min(a[i][j], a[i][j + 1]), BIT::insert(b[i][j][0], -1);
    }
    for(int i = 1; i < n; i++) {
        for(int j = 1; j <= m; j++) b[i][j][1] = min(a[i][j], a[i + 1][j]), BIT::insert(b[i][j][1], -1);
    }
    for(int i = 1; i < n; i++) {
        for(int j = 1; j < m; j++) c[i][j] = min(b[i][j][0], b[i + 1][j][0]), BIT::insert(c[i][j], 1);
    }

    int offset = 0;
    for(Op &o : q) {
        if(o.op == 0) {
            int x = o.x, y = o.y, z = o.z;
            BIT::insert(a[x][y], -1), BIT::insert(a[x][y] = z, 1);
            if(x > 1) BIT::insert(b[x - 1][y][1], 1), BIT::insert(b[x - 1][y][1] = min(a[x - 1][y], a[x][y]), -1);
            if(y > 1) BIT::insert(b[x][y - 1][0], 1), BIT::insert(b[x][y - 1][0] = min(a[x][y - 1], a[x][y]), -1);
            if(x < n) BIT::insert(b[x][y][1], 1), BIT::insert(b[x][y][1] = min(a[x][y], a[x + 1][y]), -1);
            if(y < m) BIT::insert(b[x][y][0], 1), BIT::insert(b[x][y][0] = min(a[x][y], a[x][y + 1]), -1);
            if(x > 1 && y > 1) BIT::insert(c[x - 1][y - 1], -1), BIT::insert(c[x - 1][y - 1] = min(b[x - 1][y - 1][0], b[x][y - 1][0]), 1);
            if(x > 1 && y < m) BIT::insert(c[x - 1][y], -1), BIT::insert(c[x - 1][y] = min(b[x - 1][y][0], b[x][y][0]), 1);
            if(x < n && y > 1) BIT::insert(c[x][y - 1], -1), BIT::insert(c[x][y - 1] = min(b[x][y - 1][0], b[x + 1][y - 1][0]), 1);
            if(x < n && y < m) BIT::insert(c[x][y], -1), BIT::insert(c[x][y] = min(b[x][y][0], b[x + 1][y][0]), 1);
        } else {
            offset += o.x;
        }
        int x = lower_bound(num + 1, num + 1 + nn, -offset + 1) - num;
        cout << BIT::query(x) << '\n';
    }

    return 0;
}