真 nm 自闭（呲牙。

A Maxim and Biology

B Dima and a Bad XOR

给定一个 $n \times m$ 的矩阵，每一行选一个，构造一种异或和不为 $0$ 的情况。

枚举每个二进制位，统计有多少个位置必选 $1$，其他位置可选 $1$ 的，选上使得 $1$ 的总数为奇数。

C Problem for Nazar

D Stas and the Queue at the Buffet

给定 $n$ 对数 $(a_i,b_i)$，为这些数字重新安排位置，假设 $i$ 在位置 $j$ 上，他的权值是 $(j-1)\cdot a_i + (n-j) \cdot a_i$，求最小权值和。

先假设所有每个位置都选上了 $a_i$，只要在选 $b_i$ 时把 $a_i$ 的影响消除即可。

注意到越小的数系数应该越小，对 $b_i-a_i$ 排序，乘上贡献即可。

E Number of Components

给定 $n$ 个在 $[1,n]$ 范围内的数，记 $f(l,r)$ 表示，选出所有范围在 $[l,r]$ 内的数，剩下的数组成了多少条线段。求 $\sum_{l=1}^n \sum_{r=l}^n f(l,r)$。

考虑每个点作为一个线段左端点的贡献。

如果 $a_i \ge a_{i-1}$，那么左端点的范围是 $[a_{i-1}+1,a_i]$，右端点的范围是 $[a_i,n]$，否则类似的计算贡献。

F Sonya and Informatics

给定一个 $01$ 序列，做 $k$ 次操作，每次等概率选一对数交换，求最后排成不减序列的概率。

显然，顺序不影响，只要前面都是 $0$，后面都是 $1$ 即可，设有 $m$ 个 $0$，考虑 $dp[i]$ 表示前面 $m$ 个有 $i$ 个 $0$。

于是有转移方程

$$
dp[i] = dp[i] \cdot ({m \choose 2} + {n-m \choose 2}+(m-i) \cdot (n-2m+2i)) / {n \choose 2} \

• dp[i-1] \cdot (m-i+1)^2 / {n \choose 2} \
• dp[i+1] \cdot (i+1)(n-2m+i+1) / {n \choose 2}
  $$

状态数只有 $100$，转移次数很大，注意到转移矩阵是固定的，矩阵快速幂即可。

注意不要忘记原点变成缩点后的新点。

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

int cnt, bel[maxn]; // important!
namespace Tarjan {
    int tot, dfn[maxn], low[maxn], st[maxn], top, vis[maxn];
    void clear(int n) {
        tot = top = cnt = 0;
        for (int i = 1; i <= n; i++) {
            edge[i].clear(); dfn[i] = vis[i] = bel[i] = 0;
        }
    }
    void dfs(int u, int f) {
        dfn[u] = low[u] = ++tot;
        st[++top] = u; vis[u] = 1;
        int k = 0;
        for (int& v: edge[u]) {
            if (v == f && !k) {
                k++; continue;
            } 
            if (!dfn[v]) {
                dfs(v, u); low[u] = min(low[u], low[v]);
            } else if (vis[v]) low[u] = min(low[u], dfn[v]);
        }
        if (dfn[u] == low[u]) {
            cnt++; int t = 0;
            do {
                t = st[top--];
                bel[t] = cnt;
                vis[t] = 0;
            } while (t != u);
        }
    }
    void scc(int n, vector<int> * g) {
        for (int i = 1; i <= n; i++) if (!dfn[i]) Tarjan::dfs(i, 0);
        for (int i = 1; i <= n; i++) g[i].clear();
        for (int i = 1; i <= n; i++) {
            int u = bel[i];
            for (int& x: edge[i]) {
                int v = bel[x];
                if (u != v) {
                    g[u].push_back(v);
                }
            }
        }
    }
}

Record

XLor(背锅)：

• 贡献了全队的所有罚时，锅++。

• H 忘记变换缩点后的坐标，锅++。

• H wa了之后，确定算法是真的，没有出数据 check，锅++。

真 口胡选手（赛后补交全挂了，做了 $3$ 个假题可太 zz 了

A Serval and Bus

有 $n$ 个班车，始发时间 $s_i$，之后每隔 $t_i$ 发一班，求一个人在 $t$ 时候最早在何时上车。

求一下上车时间的最小值。

如果还未发车，在上车时间为始发时刻；否则，求下一辆车何时到达，上取整即可。

B Serval and Toy Bricks

C Serval and Parenthesis Sequence

给定一个长度为 $n$ 的括号序列，其中某些位置不确定，求一个匹配的括号序列，使得其自身外每个前缀都不匹配。

显然尽量选左括号即可。

D Serval and Rooted Tree

给定一棵 $n$ 个点的有根树，每个点上有一个标记 $\min$ 和 $\max$，有 $k$ 个叶子，每个叶子安排一个 $1$ 到 $k$ 的权值。

对于每个非叶子结点，他的权值是对其儿子做 $\min$ 或 $\max$ 操作，求根节点的最大权值。

对于每个结点维护其至少小于等于几个数。

一开始，对于叶子结点显然小于等于其自身。

考虑非叶子结点，如果是取 $\max$ 操作，则会从叶子里取一个小于等于个数最少的，如果是取 $\min$ 操作，由于子树之间不相交，需要把每个儿子小于等于个数加起来即可。

E Serval and Snake

给了一个 $n \times n$ 的网格图，上面有一条蛇，你需要找到这个蛇的两端。

询问至多 $2019$ 次，每次询问一个矩形边框和蛇的相交次数，其中 $2\le n \le 1000$。

首先询问左边一整块，如果相交次数为奇数，那么两端一定分布在分界线两边，否则在同侧。

假设两端不在同一列，在询问情况一定是，某一个前缀一直是偶数，某一个后缀一直是偶数，只有中间是奇数，则这两个分界线上分别有 $1$ 个端点。

对于行，同样做这件事，询问次数至多为 $1998$ 次。

这样，我们会扣出 $4$ 条分界线，就有两组解，询问一下某个点，显然如果是头尾的话，则相交次数一定为 $1$，这样就找到了端点。

如果在同一行或者同一列，则有一个方向没有分界线。

最后这 $20$ 次询问，用来二分得到那个对应位置。

我们注意到同上类似的事情，如果一个矩形内仅有 $1$ 个端点，则相交次数一定为奇数，用这个条件二分即可。

题面

给定一个长度为 $n$ 的序列求两两异或值的第 $k$ 小。

其中 $2 \le n \le 10^6$。

分析

显然需要建一棵字典树出来。

在字典树上从大到小地往下爬，如果当前 $k$ 大于该位异或值为 $0$ 的对数，那么表示这个位置应该选 $1$，否则选 $0$。

但是把字典树建出来空间是不够的，考虑将字典树滚动掉。

从高位往低位枚举，维护序列每个点在字典树上爬的标号，这个标号是滚动的，并且记录每个结点的大小。

再维护序列上每个位置与哪个结点配对，计算每层的大小时，累加一下选择与这个数字在该位异或为 $0$ 的结点总数。

根据大小关系，更新答案和 $k$ 值，并将每个结点的配对位置往下爬。

题面

给定一个长度为 $n$ 的序列，求长度在 $[L,R]$ 范围内的子区间权值和的前 $k$ 大之和。

其中 $1 \le n,k \le 5 \times 10^5$。

分析

前 $k$ 大等价于每次选一个没有选择过的子区间中有最大权值的。

记三元组 $(o,l,r)$ 表示左端点为 $o$，右端点在区间 $[l,r]$ 范围内的一段区间，即询问 $[l,r]$ 范围内前缀和的最大值，RMQ 预处理。

用一个堆来维护最大值，显然当前时刻的最大值对应某一个三元组 $(i,L,R)$。

当我们删除这个三元组时，还需要考虑 $i$ 为左端点的其它情况。

设最大值位置为 $t$，那么可能存在次大值在 $(i,L,t-1)$ 和 $(i,t+1,R)$，特判区间是否存在，加进堆里维护。

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

int n, m, a[maxn];

struct Trie {
    static const int maxl = 25;
    int tot, ch[maxn * maxl][2], val[maxn * maxl], root[maxn];
    void clear() {
        tot = 0; ms(val, 0);
    }
    int node() {
        return ++tot;
    }
    void insert(int pre, int rt, int x) {
        pre = root[pre];
        rt = root[rt] = node();
        for (int i = maxl - 1; i >= 0; i--) {
            val[rt] = val[pre] + 1;
            int b = (x >> i) & 1;
            if (!ch[rt][b]) ch[rt][b] = node();
            ch[rt][b ^ 1] = ch[pre][b ^ 1];
            rt = ch[rt][b];
            pre = ch[pre][b];
        }
        val[rt] = val[pre] + 1;
    }
    int query(int pre, int rt, int x) {
        pre = root[pre]; rt = root[rt];
        int ans = 0;
        for (int i = maxl - 1; i >= 0; i--) {
            int b = (x >> i) & 1;
            if (val[ch[rt][b ^ 1]] - val[ch[pre][b ^ 1]]) {
                ans += 1 << i;
                rt = ch[rt][b ^ 1];
                pre = ch[pre][b ^ 1];
            } else {
                rt = ch[rt][b];
                pre = ch[pre][b];
            }
        }
        return ans;
    }
} f;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i); 
        a[i] ^= a[i - 1];
        f.insert(i - 1, i, a[i]);
    }
    char op[2]; int l, r, x;
    while (m--) {
        scanf("%s", op);
        if (op[0] == 'A') {
            n++;
            scanf("%d", a + n);
            a[n] ^= a[n - 1];
            f.insert(n - 1, n, a[n]);
        } else {
            scanf("%d%d%d", &l, &r, &x);
            // important
            if (l == 1 && r == 1) printf("%d\n", a[n] ^ x);
            else printf("%d\n", f.query(max(0, l - 2), r - 1, a[n] ^ x));
        }
    }
    return 0;
}

A The Doors

B Nirvana

C Queen

给定一棵 $n$ 个点的有根树，每个点有一个权值 $c_i$ 表示是否尊重它的父亲，删除满足它自己不尊重父亲且它的孩子也不尊重它的的结点，然后将这个点的儿子连向该点的父亲，直到不能删除为止，如果同时有多个点可以删除，则删除标号最小的点。

$dfs$ 扫一遍，维护一下每个点被多少个儿子尊重，将所有尊重数为 $0$ 且自己不尊重父亲的点拿出来排序即可。

D The Beatles

给定一个长度为 $n\cdot k$ 的环，环上编号为 $1,k+1,2k+1,\dots$ 的点为汉堡王，一个人从环上某个点出发，每次走 $l$ 步直到回到起点。

我们不知道出发点和步长，只知道一开始距离汉堡王的最近距离，以及跳一步后与最近的汉堡王距离。

求最少和最多跳多少次回到起点。

随便枚举一下起点和终点，注意到起点并不重要，只有相对位置重要，对于步长 $l$，跳的步数为 $nk \over \gcd(nk,l)$。

E Lynyrd Skynyrd

给定 $1$ 到 $n$ 的排列 $p$，给定一个长度为 $m$ 的序列 $a$，每次询问 $a$ 的子串是否含有一个子序列是 $p$ 的一个循环串。

对于序列 $a$ 内的每个位置，搞出其下一步跳到哪里为在 $p$ 串上对应的下一个位置。

考虑倍增，设 $dp[i][j]$ 表示第 $i$ 个位置在 $p$ 上跳 $2^j$ 个到达的位置。

之后容易得到，每个点跳 $n-1$ 步到达的位置，即从某一个位置开始，最短一个子串，包含了子序列是 $p$ 的一个循环串。

对于每个询问 $[l,r]$，即在这个区间内选一个右端点最小的子串满足条件，如果这个右端点在 $r$ 的左边，即含有这样的循环串，反之不含有，这部分也可以预处理得到。

时间复杂度：$O(m\log n + q)$。

被唐老师弄自闭了呀 T^T。

A 解方程

给定自然数 $n$，求解

$$
\sqrt{x-\sqrt{n}}+\sqrt{y}-\sqrt{z}=0
$$

不定方程方程所有自然数解 $(x,y,z)$ 之积求和，或者指出不定方程解有无穷多个。

首先注意到，若 $n$ 为完全平方数，有无穷多组解。

否则，尝试对 $x-\sqrt{n}$ 因式分解为平方式，对比系数可得

$$
\begin{cases}
x = y+{n \over 4y} \
y = y \
z = {n \over 4y}
\end{cases}
$$

因此，$n$ 必须是 $4$ 的倍数，之后枚举 ${n \over 4}$ 的每个因子算贡献即可，同时等价于求其约数个数和约数和。

此时，时间复杂度为 $O(T \cdot \sqrt{n})$，然而并不能通过。

此时可以用 $Pollard Rho$ 快速分解出质因数（误）。

预处理出 $10^5$ 以内的素数，枚举每个素因子试除，算贡献即可。

由于素数分布，素数个数除掉了一个 $\log$。

因此，时间复杂度为 $O(T \cdot {\sqrt{n} \over \log 10^9})$

B 旅途

给定一个长度为 $n$ 的环，起点为 $1$，有 $m$ 天，每天顺时针走一步的概率为 $p$，逆时针走一步的概率为 $q$，否则原地停留。

令 $f(i)$ 表示最后一共游玩 $i$ 个城市的概率，求 $\sum_{i=1}^{n} i^k f(i)$。

若没有游玩所有城市，则游玩过的城市是环上的一个区间。

考虑 $dp[t][x][y]$ 表示第 $t$ 天，玩到顺时针 $x$ 个城市，逆时针 $y$ 个城市概率。

其中，$x,y \le 0$ 且 $x+y+1\le min(n-1,i)$。

初始状态 $dp[1][0][0] = 1$。

转移方程

$$
dp[t][x+1][max(y-1,0)]+=dp[t-1][x][y] \cdot p \
dp[t][max(x-1,0)][y+1]+=dp[t-1][x][y] \cdot q \
dp[t][x][y] += dp[t-1][x][y] \cdot (100-p-q)
$$

C 项链与计数

给了一个项链的定义，简单来说项链是由简单环 $c_1,c_2,\dots,c_n$ 按顺序连接的一条无向图路径，其中相邻两个有唯一公共点，其余均没有公共点和公共边。

给定 $m$ 条边，从没有边开始按顺序加边进去，对于每次加边操作，求出当前有多少点对之前存在一个项链。

观察这个定义，他的意思其实是将项链看成两条路径，一个项链其实是两点之间的多条不同路径，即双联通。

所以，题目询问的是每次操作后的所有双联通分量的大小，增量维护。

首先，扣出图上边编号最小的一棵生成树（森林），因为要保证树边是最先加入进来的。

然后，为森林标上根和每个点的父亲。

加边操作时，如果是树边，对答案无影响，否则，并查集维护每个双联通分量的大小。

加边操作对应两个点往上跳到公共祖先，将两条路径上的所有双联通分量合并。