高爸的杂题练习 2

AHOI2013 作业

给你长度为$n$的序列$A$，有$m$个询问$(l,r,a,b)$，求

1. $\sum_{i\in[l,r]}[a\le A_i\le b]$。即求元素个数。
2. $|\{A_i|i\in[l,r],a\le A_i\le b\}|$。即求数值个数。

$n,m\le 10^5$。

摘要：莫队，离散化，树状数组。

代码

SDOI2016 模式字符串

给你一棵$n$个点的树，每个点上有一个字符。给你一个串$|S|$。

求有多少个有序点对$(u,v)$，使得$u$到$v$的路径组成的字符串以$S$为循环节。

$n,|S|\le 10^5$。

摘要：点分治，哈希。

考虑点分治，那么我们考虑有多少经过当前重心的合法路径。

以当前重心为根，设$f(i)$表示$i$子树内以$i$结束的$S$的循环串路径个数（向上的路径），$g(i)$表示子树内以$i$开始的$S$的循环串路径个数（向下的路径）。然后我们求出$i$到根路径的字符串的哈希值以及其反串的哈希值，在哈希表里查一下匹配之类的就可以计算出经过当前重心的方案数了。

细节写炸，弃坑了……

时间复杂度$O(n\log_2n)$。

ZJOI2007 捉迷藏

给你一棵树$n$个点的树，支持$m$个询问：

1. 改变一个点的颜色（黑白）
2. 求黑点构成的虚树的直径

$n\le 10^5,m\le 5\times 10^5$。

摘要：点分树，堆。

点分树上，每个点维护两个堆$A_u,B_u$，$A_u$是到点分树上父亲的距离集合，$B_u$是点分树上儿子的$A_u$的堆顶集合。这样的话每个点的答案就可以用$B_u$的最大值和次大值求出。

对答案开一个堆。然后修改的时候在路径上删除再加入即可。

堆要支持删除。

时间复杂度$O(n\log_2^2n+m\log_2n)$（可以先预处理距离免得倍增）。

代码

ZJOI2015 幻想乡战略游戏

给一棵$n$阶的点边带权的树$T$，初始时点权$d_u$为$0$。有$q$次操作，每次修改某个点的点权，要求在每次操作后询问

$$\min_{u\in T}\left\{ \sum_{v\in T}\text{dist}(u,v)d_v \right\}$$

其中$d_v$是点权，$\text{dist}$表示两点的距离（路径长度）。

特殊性质：每个点度数不超过$D$。

$n\le 10^5,D=20$。

摘要：点分树上递归查询。把舍弃的部分缩点，也就是做一个点权修改的操作。查完了撤消修改。

从特殊条件入手。既然它限定每个点的度数，说明可以枚举儿子。

从某个点$u$开始，我们尝试找到最小化答案的点$ans$。容易发现，这个寻找的过程类似带权重心。每次我们选择相邻连通块中权值和大于总和一半的连通块并前进。如果没有权值和大于总和一半的连通块，说明当前点就是$ans$。

考虑在点分树上做类似的过程。那么就要求我们支持：

1. 快速查询某个连通块的权值和
2. 快速统计其他连通块的答案贡献和。

这个可以直接用变量维护。

当你选择了一个连通块后，其他连通块的权值和也得考虑进来。即，我们把其他连通块缩点，然后连接到这个连通块上。所谓的缩点，实际上就是把其他连通块的权值和加到这个连通块的（与当前重心相邻的）某个叶子结点上。这样就是一个递归子问题，可以继续做了。查询完了撤消修改即可。

因此我们发现，查询也依赖修改。

而修改也是容易做的，点分树上暴力跳父亲即可。

要预处理一下做到$O(1)$查询两点距离。

修改的复杂度是$O(\log n)$，查询的复杂度是$O(\log^2 n+\log nD)$。

总复杂度$O(n\log_2^2n+q(\log^2n+\log nD))$。

代码

数颜色

给你一个$n$阶序列，支持$m$个操作：

1. 单点修改；
2. 查询区间里出现的值的个数（多少个不同的数字）

$n,m\le 13333,a_i\le 10^6$。

摘要：带修莫队：加一维时间，块大小$O((nt)^{\frac{1}{3}})$（如果$O(n)=O(t)$就是$O(n^{\frac{2}{3}})$）。复杂度$O(n^{\frac{4}{3}}t^{\frac{1}{3}})$。

如果不带修改可以莫队。

带修改就加一维时间，排序的时候按照左端点块编号升序、右端点块编号升序、时间升序这样依次排序即可。

记得要卡一下常，比如块大小乘 2 什么的。

代码

Logistical Questions

给一棵点边带权树$T$，点权为$w_u$，边权为$w(u,v)$。求

$$\min_{u\in T}\left\{ \sum_{v\in T}w(u,v)^{\frac{3}{2}}w_v \right\}$$

并输出使得最小化的结点。

$n\le 2\times 10^5$。

摘要：凸函数，点分治。树高不超过$O(\log n)$，因此复杂度保证。

这道题展示了有关树上凸函数的一些性质。

第一部分

如果树是一条链，那么每个点的代价一定是先递减后递增。假设我们允许在边上选择点（实数范围），假设选择的点记作$v$，那么$f(u,v)=w(u,v)^{\frac{3}{2}}$在$v$变化的过程中是一个凸函数（实际上是一个类似绝对值和凸函数的混合物）。

众所周知，凸函数的和仍是凸函数（因为凸函数的导数是单调的，而两个单调函数的和仍是单调的）。

于是我们就证明了如果树是一条链，那么每个点的代价一定是凸函数。

那么如果不是一条链呢？

容易发现，当点$v$在路径$(x,y)$上从$x$移动到$y$的过程中，对于任意结点$u$（不论$u$在不在$(x,y)$上），$f(u,v)$都是凸函数。因此对于每条路径而言，从一端到另一端的每个点的代价一定是凸函数。

而这些路径的凸函数的顶点一定是同一个点（可能在某条边上）。如果存在两个顶点的话，我把这两个连起来就不是凸函数了，与上文矛盾。

如果顶点在边上，那么答案就是这条边的两个端点之一。

第二部分

因此说了这么多，我们得到了一个有助于解题的重要信息：从一个点$u$出发，至多存在一条邻边$(u,v)$，满足你沿着$(u,v)$走时代价会减小（导数为负）。如果不存在这样的邻边，那么$u$就是最优解。

因此我们就每次找到这个邻边并移动即可。这样的算法复杂度是$O(n^2)$的。

容易发现，这个过程就是在点分树上查询的过程。点分树树高不超过$O(\log n)$。因此使用点分治即可。在寻找邻边的时候，我们可以想办法在$O(n)$的总时间内求出，从$u$往$v$走一个单位后的代价和（对于所有$u$的邻居$v$）。这样就可以找出代价变小的邻边了。

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

代码

Chef and Churu

有一个长度为$n$的序列$A$和$n$个函数$(L_i,R_i):f(L_i,R_i)=\sum_{j=L_i}^{R_i}A_j$。有$Q$次操作：

1. 单点修改；
2. 询问第$l$个函数到第$r$个函数的值的和。

$n,q\le 10^5,A_i\le 10^9$。

摘要：分块，树状数组

对函数分块。假设分块大小为$T$，则有$O(\frac{n}{T})$块。

对于整块，预处理$f(i,j)$表示第$i$块里$A_j$出现的次数。维护$s_i$表示第$i$块的函数值的和。单点修改和询问的复杂度都是$O(\frac{n}{T})$。

对于零散部分，用树状数组维护$A$序列。修改是$O(\log_2n)$的，查询是$O(T\log_2n)$的。

取$T=\sqrt{\frac{n}{\log_2n}}$为最优时间复杂度，但空间复杂度过高。

把$T$调大一点，能过。

实测$T=\sqrt{n}$时能过。

代码

Yunna 的礼物

给一个长度为$n$的序列$A$。

设$f(S,v)=\sum_{x\in S}[x=v]$（出现次数）。

设$g(S,c)=\{v\in S | f(S,v)=c\}$（出现次数为$c$的数的集合）。

设$h(S)=\{f(S,v)| v\in S\}$。

有$Q$次询问形如$(l,r,x,y)$：设$h([l,r])$中第$x$小的数为$z$，求$g([l,r],z)$中第$y$小的数。说白话就是，询问区间中出现次数第$x$小的数中第$y$小的数。

$n,q,A_i\le 40000$。

摘要：莫队，线段树维护数集。

提示：维护$S_i$表示出现次数为$i$的数的集合。其他细节显而易见。

时间复杂度$O(n\sqrt{n}\log_2 n)$。

代码