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$，求解

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

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

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

因此，$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$。

转移方程

C 项链与计数

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

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

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

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

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

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

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

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

开始日常 AtCoder 的 ABC 场以外题解（不咕咕咕的话。

A Regular Triangle

B Red or Blue

C Snuke the Wizard

给定一个长度为 $n$ 的一排房间，每个房间有个字母，一开始每个房间只有一个人。

之后有 $q$ 次操作，每次操作将待在所有房间字母为 $s_i$ 的房间内的所有人，向左或右平移一个格子。

若移动到最左边和最右边之外，这个人就没得了，求最后剩多少人。

注意到，人是一个格子一个格子平移的，不会有人跨越的现象。

因此掉落到左边一定是一个前缀，掉到右边的一定是一个后缀，二分前缀和后缀的长度即可。

降智严重，sb 二分竟然没想到。

D Modulo Operations

好题！

给定一个数字 $x$，有一个集合 $S$，每次随机从集合内删除一个数 $y$，将当前数字 $x$ 变成 $x$ mod $y$。

求将集合删光时，当前数字的期望。

注意到，每次都是取模操作，所以当前数字一定是单调不增的。其次，若一开始选了一个比较小的数字，则后面可以任意选择较大的数而不会产生影响。

这就等价于，给定一个单调递减的操作序列 $S$，对于第 $i$ 个操作，有 $1 \over n-i+1$ 的概率，对当前数取模。

对于已经进行过的 $i-1$ 次操作，每个数都有一个出现的概率，于是我们考虑第 $i$ 个数对于每个概率的影响，若选了这个数，进行这个操作，反之代表这个数会进行之后的操作。

也就是对于 $f(i,x)$ 表示进行到第 $i$ 次操作时，当前数为 $x$ 的概率，有转移方程

显然只要操作序列单调递减，上述转移正确；若操作序列不单调递减，则会在某一个上升处，这个位置的数对概率的影响并没有计算到。

模板

1
2
3
4
5
6
7
8
9
10
11
12

int pre[maxn];
void init() {
    for (int i = 1; i <= n; i++) pre[i] = i;
}
int find(int x) {
    return x == pre[x] ? x : pre[x] = find(pre[x]);
}
void join(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return ;
    pre[x] = y;
}

A Detective Book

B Good String

C Playlist

有 $n$ 首歌，每首歌有长度 $t_i$ 和好听度 $b_i$，选出至多 $k$ 首歌，他们的权值是好听度的最小值乘时长和，求最大权值。

按照好听度排序，倒着维护长度的前 $k$ 大。

D Minimum Triangulation

F Extending Set of Points

一个点集，若有点 $(x_1,y_1),(x_1,y_2),(x_2,y_1)$ 则也会有点 $(x_2,y_2)$。

给定一串加点或删点操作序列，若之前出现过当前点则为删点，否则为加点，求每次操作后的点数。

将两个维度拆开，加入一个点 $(x,y)$ 意味着编号为 $x$ 的白点连向了编号为 $y$ 的黑点，否则为删边。

每次询问就是询问，一个联通块内黑点数乘白点数，对所有联通块求和。

于是，我们要维护一个带删边的并查集，以及集合大小信息。

线段树分治 + 带撤销并查集。

线段树分治，即对时间维建立线段树，将每个点的贡献放到线段树的结点上打 $\log n$ 个标记。

最后，分治时统计当前区间的贡献，这个地方需要有并查集的撤销操作。