Solution

A. Rectangles 2

题目大意：

给出一个长度为\(n\)的数列。

之后\(m\)次操作，每次要么修改一个位置，要么询问区间\([l,r]\)中严格小于\(\frac{y1+y2}{2}\)和严格大于\(\frac{y1+y2}{2}\)的数量的大小关系。

题解:

分块，每块维护一个排好序的数组，修改时进行删除和重新插入即可。

记块大小为\(k\)，时间复杂度为\(O(n\log{n} + n(\frac{n}{k}\log{n} + k))\).

取\(k=\sqrt{n\log{n}}\)，时间复杂度为\(O(n\sqrt{n\log{n}})\).

B. Tin-plate

题目大意：在长度为 \(n\) 的数组上完成三种操作。

• 询问区间 \([L, R]\) 中不小于 \(x\) 的元素个数
• 将区间 \([L, R]\) 设置为同一个值 \(x\)
• 翻转区间 \([L, R]\)

题解：分块，用 vector 维护块序列。每个块内部元素升序，维护一个 \(\text{set}\) 标记和 \(\text{reverse}\) 标记。对于询问操作，我们只需要先 \(\text{split}(l)\) 和 \(\text{split}(r+1)\) ，然后扫一遍所有的块，每个块内部二分 \(\mathcal{O}(\log n)\) 找到答案。

翻转和赋值操作同样 \(\text{split}\) 之后打标记，翻转操作还要对 vector 进行 \(\text{reverse}\) 。\(\text{split}\) 操作，我们需要保持 \(\text{split}\) 之后的两块内部元素仍然升序，这个可以通过维护元素 \((\text{value}, \text{position})\) 的 pair 实现，然后对 vector 进行 \(\text{insert}\)。

上述操作每次最多只会增加一个块，我们在某个阈值（设为 \(k\) ）之后对整个数组进行重构，注意重构之前要把每个块的标记下放到原数组。每次操作的复杂度为 \(\mathcal{O}(\frac{n}{k}+k\log n)\) ，其中 \(k\) 是块大小，重构复杂度是 \(\mathcal{O}(n\log n)\) ，总复杂度为 \(\mathcal{O}(n\log n + \frac{n}{k}n\log n + n(k\log n + \frac{n}{k}))\) 。所以 \(k=\sqrt n\) ，复杂度为 \(\mathcal{O}(n\sqrt n\log n)\) 。

C. K Minimums On The Subarray

题目大意：每次询问一个长度为 \(n\) 的数组中区间 \([l,r]\) 的前 \(k(k\leq 10)\) 小。

题解：\(\sqrt n\) 分块，块内排序，每次取出块中的前 \(k\) 小放入大小固定的优先队列。复杂度 \(\mathcal{O}(n\sqrt n k\log k)\)。

D. Frank Sinatra

题目大意：

求树上路径mex

题解：

分块求mex，修改是\(O(1)\)，询问\(O(\sqrt{n})\).

套一个树上莫队，时间复杂度\(O(n\sqrt{n})\).

E. Substring Query

题目大意：

有\(n\)个字符串\(S_1,S_2,\cdots,S_n\)，总长度不超过\(200000\).

接下来\(q\)次询问，每次给出一个区间\([l_i,r_i]\)和字符串\(P_i\)，问\(S_{l_i},\cdots,S_{r_i}\)中有多少串包含\(P_i\)这个子串。

\(P_i\)总长度不超过\(200000\).

题解：

考虑离线做，将每次询问拆为两个前缀。

\(P_i\)只会有\(\sqrt{len}\)种不同的长度，因此可以每种长度分别做。

对于长度\(k\)，扫描线，当扫到\(S_i\)时将它所有长度为\(k\)的子串hash去重之后更新答案。

时间复杂度\(O(len\sqrt{len})\).

F. Count Online

题目大意：

二维平面上有\(n\)个点，坐标范围\([0,10^9]\).

之后\(m\)次操作，每次或者加入一个新点或者询问一个矩形内的点数。

只有加点的输入是加密的，需要上一次询问的答案解密。

题解：

只有加点的输入加密，因此我们用询问中的\(x\)坐标进行离散化即可。

用线段树套std::vector来维护二维数点，\(O(n\log^2{n})\)，但是这不支持加点操作。

对于加点，我们可以先把新点存起来，每次除了线段树中的答案，还要加上这部分的贡献。

当新点累积到\(O(\sqrt{n\log{n}})\)时，重构线段树。

时间复杂度\(O(n\log^2{n} + n\sqrt{n\log{n}})\)，空间复杂度\(O(n\log{n})\).

G. Regions

题目大意：

给出一棵\(n\)个点的树，以\(1\)为根，每个点有个颜色\(r_i\).

\(m\)次询问，问有多少个二元组\((x,y)\)，满足\(r_x=r_1\)，\(r_y=r_2\)，并且\(x\)是\(y\)的祖先。

交互题。

题解：

可以通过记忆化来使得询问都是不同的。预处理两个点都大于 \(\sqrt{n}\) 的情况，复杂度是 \(O(n\sqrt{n})\)。

对于询问\((r1,r2)\)，我们选择对应点数少的去做，这样复杂度为\(O(n\sqrt{n}\cdot k)\)，\(k\)为求一个点的答案的时间复杂度。

通过求欧拉回路序，并将每个点的入栈序与出栈序分别加入对应颜色的两个std::vector中，我们就既可以求某个颜色的点在某个子树中的数量也可以求在某个点到根路径中的数量了，时间复杂度都是\(O(\log{n})\).

总的时间复杂度为\(O(n\sqrt{n}\log{n})\)，空间复杂度\(O(n)\).

H. Alphabet Soup

题目大意：圆周上有 \(n\) 个点，用 \(s\) 种颜色给它们染色，如果两种方案旋转后等价，就视为本质相同。求本质不同的方案数。

题解：将相邻点的角度作差，得到一个长为 \(n\) 的序列，设它的循环节长度为 \(t\)，那么显然每旋转 \(t\) 个点才能够和原图重合。根据 \(Polya\) 定理，答案为 \(\displaystyle{\frac{t}{n}\sum_{k=1}^{\frac{n}{t}}s^{gcd(kt,n)}}\)。求循环节可以对 \(n\) 的每个质因子二分后验证（不二分也行）。

I. Toral Tickets

题目大意：给你一个 \(n\times m\) 个格子的矩形，可以用黑白两种颜色给每个格子染色。现在要将它卷成一个甜甜圈的形状，方法是先将两条较长的边粘在一起成为一个圆柱，然后再将两个圆形底粘在一起（如果是正方形，就有两种粘贴顺序）。如果两个甜甜圈可以由同一个矩形得到，那么它们本质相同。求本质不同的方案数。

题解：最后的甜甜圈以中心轴旋转显然是等价的，但是还要注意到甜甜圈从内向外翻也是等价的，这可以通过在第二步操作中选择不同的列为中心得到，另外最初的矩形翻转 \(180^{\circ}\) 也还是等价的。我们将这 \(2nm\) 种置换的循环节暴力求出来后套 \(Polya\) 定理即可。正方形的情况旋转 \(90^{\circ}\) 即可。

时间复杂度 \(\mathcal{O}(n^{2}m^{2})\)。

J. Harmonic Triples

题目大意：求满足 \(1\le a<b<c\le n\) 及以下两个条件之一的三元组 \((a,b,c)\) 的个数

• \(gcd(a,b)=1,gcd(a,c)=1,gcd(b,c)=1\)
• \(gcd(a,b)>1,gcd(a,c)>1,gcd(b,c)>1\)

题解：建一个 \(n\) 个点的完全图，若 \(gcd(a,b)=1\) 则 \(a,b\) 间连一条红边，否则连一条蓝边。那么我们要求的即为同色三角形的个数，即为 \({n\choose 3}\) 减去异色三角形的个数，即为 \(\frac{1}{2}\sum_{i=1}^{n}(i点连的红边数)\times(i点连的蓝边数)\)，以求红边数为例：答案为 \(\sum_{d\mid i}\mu(d)\lfloor\frac{n}{d}\rfloor\)。

时间复杂度 \(\mathcal{O}(n\log n)\)。

K. Perfect Powers

题目大意：求 \([A,B]\) 中的完全乘方数的数量。\(A,B\) 可能为负数。

题解：\(-1,0,1\) 单独考虑。\([2,B]\) 中的完全乘方数数量为 \(\sum_{i=2}^{\infty}-\mu(i)(\lfloor\sqrt[i]{B}\rfloor-1)\)，\([-A,-2]\) 中的完全乘方数数量为 \(\sum_{i\ge3,2\nmid i}^{\infty}-\mu(i)(\lfloor\sqrt[i]{A}\rfloor-1)\)。

L. Network Instability

题目大意：\(n\) 个点，\(m\) 条边的简单无向图，每个点有一个颜色。\(q\) 次操作，每次将点 \(v_i\) 的颜色改为 \(c_i\)，每次操作之后输出有多少条边的两个端点颜色不同。

题解：对点按度数与 \(\sqrt m\) 的关系分类。如果修改的点是 big 的，枚举它的 big 的邻点，更新答案。对于每一个 big 点，我们同时维护每种颜色在它的 small 的邻点的出现次数。

如果修改的点是 small 的，我们枚举它的每个邻点，如果是 small，那么更新答案；如果是 big，那么修改 big 的颜色数组。

总复杂度是 \(\mathcal{O}(q\sqrt m)\)。注意 small – small 的边和 big – big 的边我们可能会重复计算，需要给每条边维护一个是否被计算的标记。