Dylan's Blog

问题描述

给定一棵 $n$ 个点的有根树，其中 $1$ 号点是根节点。每个节点都被染上了某一种颜色，其中第 $i$ 个节点的颜色为 $c_i$。定义 $dep_i$ 为 $i$ 节点与根节点的距离，为了方便起见，你可以认为树上相邻的两个点之间的距离为 $1$。

站在这棵色彩斑斓的树前面，你将面临 $m$ 个问题。每个问题包含两个整数 $x$ 和 $d$，表示询问 $x$ 子树里且 $dep$ 不超过 $dep_x+d$ 的所有点中出现了多少种本质不同的颜色。

输入

第一行包含一个正整数 $T(1<=T<=500)$，表示测试数据的组数。
每组数据中，第一行包含两个正整数 $n$ 和 $m (1 \leq n,m \leq 100000)$，表示节点数和询问数。
第二行包含 $n$ 个正整数，其中第 $i$ 个数为 $ci (1 \leq c_i \leq n)$，分别表示每个节点的颜色。
第三行包含 $n-1$ 个正整数，其中第 $i$ 个数为 $f{i+1} (1 \leq f_i<i)$，表示节点 $i+1$ 的父亲节点的编号。
接下来 $m$ 行，每行两个整数 $x(1 \leq x \leq n)$ 和 $d(0 \leq d \leq n)$，依次表示每个询问。
输入数据经过了加密，对于每个询问，如果你读入了 $x$ 和 $d$，那么真实的 $x$ 和 $d$ 分别是 $x \oplus last$ 和 $d \oplus last$，其中 $last$ 上一次询问的答案。
输入数据保证 $n$ 和 $m$ 的总和不超过 $500000$。

输出

对于每个询问输出一行一个整数，即答案。

思路

方法一： 如果这个问题在序列上且离线的话，可以发现这就是「HH的项链」。其中一个比较好的思路就是先将询问排序，从左到右扫一遍，我们将每种颜色的贡献算在这种颜色最右边的点上，用树状数组维护区间和即可。强制在线怎么办？可持久化一下，每个右端点都建一个线段树即可。

把这个放在树上也是一样，按深度从大到小考虑，我们将每种颜色的贡献算在这种颜色最浅的点上，用一个以深度为下标的线段树计算子树的答案，然后从下到上线段树合并就好。同时再开一个以颜色为下标的线段树维护深度，同样从下向上合并，合并时把较深的一点贡献在计算答案的线段树上删去。强制在线怎么办？将线段树合并的过程可持久化一下就好。空间复杂度似乎是多一个 $\log n$ 的。

方法二： 类似的从序列上的问题考虑。还有一种想法就是，从左到右扫一遍，每当加入一个颜色的点时，加上这个点的贡献，并删去这个颜色上一个点的贡献，同样用树状数组维护区间和就好。

如果把这个放在树上，就是按深度从小到大考虑，每增加一个颜色的点时，就加上这个点的贡献，并在它和与它颜色相同且相邻的点的 LCA 上删去贡献（这里的相邻是指 dfs 序上两点之间没有其他相同颜色的点）。因为一棵子树的 DFS 是连续一段，这样就可以按深度从小到大扫，用线段树维护子树区间和即可。强制在线怎么办？可持久化，每个深度都建一个线段树就好。

代码

嘴巴选手，懒，不想写代码

第一类斯特林数

定义：

表示 $n$ 个不同元素形成 $m$ 个圆排列的方案数，记为 $\begin{bmatrix} n \ m \end{bmatrix}$。

性质：

首先考虑这个怎么求，可以枚举第 $n$ 个元素，它可以自己形成一个新的环，方案数为 $\begin{bmatrix} n-1 \ m-1 \end{bmatrix}$；它也可以放在已有的 $n-1$ 个元素中一个的后面，方案数为 $(n-1)\begin{bmatrix} n-1 \ m \end{bmatrix}$，从而得出递推式:

我们设 $f_n(x)$ 为 $\begin{bmatrix} n \ x \end{bmatrix}$ 的生成函数。根据上面式子可以写出它的生成函数

而这个可以直接套用分治 FFT 在 $O ( n \log^2 n )$ 内求出，但我们还可以在它的基础上优化。考虑你目前分治到区间 $(l,r)$，在这之前已经计算出了区间 $(l, mid)$ 的卷积，这个时候应该要递归的计算 $(mid+1, r)$ 的卷积，但其实发现如果你设 $(l, mid)$ 的卷积为 $g(x)$，那么 $(mid+1,r)$ 的卷积就是 $g(x+mid)$。将式子如下化简：

你发现后面的那一块有点像卷积的形式，将其中一项反转后就可以卷起来了，这样我们做到 $O(n \log n)$ 的复杂度

3 月 8 日 Codeforces Round #545 比赛链接：https://codeforces.com/contest/1138

E - Museums Tour

思路：

首先考虑将每一个 museum 按天数分为 $d$ 个点，然后对应的向相邻的连边。接着就很自然的想到用 tarjan 缩点，然后考虑如何统计答案。有一个性质就是如果一个 museum 对应不同天的点之间有边，那么这些点一定是在同一个强联通分量里面的，因此你缩点后直接找一个包含 museum 数最多的链就是对的。

代码链接

F - Cooperative Game

思路： 如果你知道 pollard-rho 中的 floyd 判环的话，这题的思路就应该不难想到。如果你直接模拟这个过程：让一个人每次走一步另一个人每次走两步，就能够在 $2*(t+c)$ 次交互内让两个人在环上相遇。那么问题就在于如何不知道终点位置的情况下让所有人走到终点。这里有个非常巧妙的性质就是在相遇点走 $t$ 步后一定能到达终点，如果我们设两个人分别走了 $t+x$，$2t+2x$ 步后相遇，那么 $t+x$ 一定是环长的倍数，如果再走 $t$ 步就意味着在环上总共走了 $t+x$ 步（一开始在链上走了 $t$ 步），那么就一定走到了终点。因此只要让一些人留在起点，两个人在环上相遇后所有一起走若干步，如果大家全部相遇，就意味着已经到终点了。

代码链接

问题描述

给定长度为 $n$ 的序列：$a_1,a_2,…,a_n$，记为 $a[1:n]$。有 $q$ 个询问，每个询问给定两个数 $l,r$，求 $a[l:r]$ 中所有子序列的最小值之和。

输入

第一行包含两个整数 $n$ 和 $q$，分别代表序列长度和询问数。

接下来一行，包含 $n$ 个整数，第 $i$ 个整数为 $a_i$。

接下来 $q$ 行，每行包含两个整数 $l$ 和 $r$，代表一次询问。

输出

对于每次询问，输出一行，代表询问的答案。

思路

有一种比较直观的方法就是使用莫队，队中维护一个单调栈，并且记录栈中元素到前一个元素这段区间的答案。当插入元素时，更新单调栈，通过记录的信息可以比较容易的求出答案。

这题还有一个很妙的 Idea。考虑类似于上面莫队的方法，先处理出右端点为 $i$ 的所有 $a[l,i]$ 的最小值的和，记为 $pre_i$，再处理一个 $pre_i$ 的前缀和 $spre_i$，这样 $spre_i$ 即是 $a[1,i]$ 的答案。类似的再处理出 $suf_i$，表示所有左端点为 $i$ 的序列的最小值之和，以及 $ssuf_i$ 表示 $suf_i$ 的后缀和。

预处理完这些东西后，考虑如何回答区间 $a[l,r]$ 的答案，我们设 $a[l,r]$ 中最小值位于 $pos$，这个可以利用 ST 表求出。经过 $pos$ 这一点的所有区间对答案的贡献可以直接计算出来，考虑剩下 $a[l,pos-1]$ 及 $a[pos+1,r]$ 这两段的贡献如何计算。我们发现 $spre[r]-spre[pos]$ 就包含了 $a[pos+1,r]$ 这一段的答案和右端点在 $[pos+1,r]$ 左端点在 $[1,pos-1]$ 的区间最小值之和。而后面一部分由于跨过了 $pos$，它的贡献可以等价为 $(r-pos)*pre[pos]$，将它们相减就可以计算出 $a[pos+1,r]$ 的贡献，类似的可以同样计算出 $a[l,pos-1]$ 的贡献。

这样我们可以在 $O(1)$ 的时间内回答每一个询问，而算法复杂度的瓶颈在 $O(n \log n)$ 的 ST 表预处理上，而如果使用笛卡尔树或者用一些 $O(n)$ RMQ 的高级姿势，就可以在线性复杂度内完成这个操作。

代码

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
67
68
69

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 100005
#define P 998244353
#define INF 0x3f3f3f3f
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int n, q, top, a[MAXN], f[MAXN][20], sta[MAXN], Log[MAXN];
LL pre[MAXN], spre[MAXN], suf[MAXN], ssuf[MAXN];

int query(int x, int y)
{
    int k=Log[y-x+1];
    if(a[f[x][k]]<a[f[y-(1<<k)+1][k]]) return f[x][k];
    else return f[y-(1<<k)+1][k];
}

int main()
{
    scanf("%d%d", &n, &q);
    for(rint i=1; i<=n; ++i)
    {
        scanf("%d", &a[i]);
        f[i][0]=i;
    }
    for(rint i=1; i<20; ++i)
        for(rint j=1; j+(1<<i)-1<=n; ++j)
        {
            if(a[f[j][i-1]]<a[f[j+(1<<i-1)][i-1]]) f[j][i]=f[j][i-1];
            else f[j][i]=f[j+(1<<i-1)][i-1];
        }
    for(rint i=2; i<=n; ++i) Log[i]=Log[i/2]+1;
    sta[top=0]=0;
    for(rint i=1; i<=n; ++i)
    {
        while(top && a[sta[top]]>=a[i]) top--;
        pre[i]=pre[sta[top]]+1LL*a[i]*(i-sta[top]);
        sta[++top]=i;
        spre[i]=spre[i-1]+pre[i];
    }
    sta[top=0]=n+1;
    for(rint i=n; i>=1; --i)
    {
        while(top && a[sta[top]]>=a[i]) top--;
        suf[i]=suf[sta[top]]+1LL*(sta[top]-i)*a[i];
        sta[++top]=i;
        ssuf[i]=ssuf[i+1]+suf[i];
    }
    for(rint i=1, l, r; i<=q; ++i)
    {
        LL ans=0;
        scanf("%d%d", &l, &r);
        int pos=query(l, r);
        ans+=1LL*(pos-l+1)*(r-pos+1)*a[pos];
        ans+=ssuf[l]-ssuf[pos]-1LL*(pos-l)*suf[pos];
        ans+=spre[r]-spre[pos]-1LL*(r-pos)*pre[pos];
        printf("%lld\n", ans);
    }
    return 0;
}

分治FFT 1

已知函数 $g(x)$，且 $f(x),g(x)$ 存在如下关系，求 $f(x)$

可以利用 CDQ 分治的思想，将一段区间分为两半递归处理，并统计左半部分对右部分的贡献。具体地说，当我们要计算 $f(l \sim r)$ 时，先计算出 $f(l \sim mid)$ 的值，然后将这部分和 $g(1 \sim r-l)$ 卷积起来，就可以得到这部分对后半贡献。递归的边界应该是 $f(0)=1$，然后向上合并就可以计算出 $f(x)$ 的每一项，这样的复杂度是 $O(n \log^2 n)$ 的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

void divide(int l, int r)
{
    if(l==r) return;
    int mid=(l+r)>>1, bit=0;
    divide(l, mid);
    while((1<<bit)<=((r-l+1)<<1)) bit++;
    for(rint i=0; i<(1<<bit); ++i)
    {
        pos[i]=(pos[i>>1]>>1)|((i&1)<<(bit-1));
        a[i]=b[i]=0;
    }
    for(rint i=l; i<=mid; ++i) a[i-l]=f[i];
    for(rint i=0; i<=r-l; ++i) b[i]=g[i];
    ntt(a, 1<<bit, 1), ntt(b, 1<<bit, 1);
    for(rint i=0; i<(1<<bit); ++i) a[i]=1LL*a[i]*b[i]%P;
    ntt(a, 1<<bit, -1);
    for(rint i=mid+1; i<=r; ++i) f[i]=add(f[i], a[i-l]);
    divide(mid+1, r);
}

分治FFT 2

对于给定数组 $a,b$，且 $f(x)$ 有如下形式，求 $f(x)$

可以利用分治的思想，将这个 $n+1$ 个多项式每次分为两部分，递归处理完后再将两部分合并。具体地说，当计算 $\prod_{i=l}^{r} (a_ix+b_i)$ 时，可以分别递归计算 $l \sim mid$ 和 $mid+1 \sim r$ 这两部分多项式的积，然后再用一遍 FFT 合并，这样复杂度也是 $O(n \log^2 n)$ 的。在一些情况下可以利用倍增的思想将复杂度优化至 $O(n \log n)$。

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

void divide(int a[], int l, int r)
{
    if(l==r) {a[0]=l, a[1]=1; return;}
    int mid=(l+r)>>1, bit=0;
    while((1<<bit)<=(r-l+1)) bit++;
    int b[(1<<bit)+5], c[(1<<bit)+5];
    for(rint i=0; i<1<<bit; ++i) b[i]=c[i]=0;
    divide(b, l, mid), divide(c, mid+1, r);
    for(rint i=0; i<1<<bit; ++i) pos[i]=(pos[i>>1]>>1)|((i&1)<<(bit-1));
    ntt(b, 1<<bit, 1), ntt(c, 1<<bit, 1);
    for(rint i=0; i<1<<bit; ++i) a[i]=1LL*b[i]*c[i]%P;
    ntt(a, 1<<bit, -1);
}

多项式求逆

如果多项式 $f(x),g(x)$ 满足如下关系，我们就记 $g(x)$ 为 $f(x)$ 的逆元。

我们可以递归地求解这个问题，首先考虑 $n=1$ 时，不妨设 $f(x) \equiv c \pmod x$，此时显然有 $f^{-1}(x)=c^{-1}$；

当 $n>1$ 时，我们假设 $f(x)$ 在 $\mod x^{\lceil \frac{n}{2} \rceil}$ 意义下的逆元 $g’(x)$ 已经求出，那么就有

根据定义可以知道

两式相减得到：

将左边的多项式平方后放在模 $x^n$ 意义下，这个多项式每一项可以写成原多项式的卷积，这个卷积的每一项一定包含一个原多项式的 $0 \sim \lceil \frac{n}{2} \rceil$ 次项，并且原多项式的 $0 \sim \lceil \frac{n}{2} \rceil$ 次项均为 $0$，所以这个 $n$ 次的多项式每一项也一定都为 $0$。即：

将两边同时乘上 $f(x)$ 后可以得到：

这样以来，我们就可以用 $O(n \log n)$ 的时间从 $g’(x)$ 推到 $g(x)$，根据主定理可以知道总时间复杂度依然为 $O(n \log n)$。

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

void inv(int a[], int b[], int n)
{
    if(n==1) {b[0]=ksm(a[0], P-2); return;}
    inv(a, b, (n+1)>>1);
    int bit=0;
    while((1<<bit)<(n<<1)) bit++;
    for(rint i=0; i<(1<<bit); ++i) pos[i]=(pos[i>>1]>>1)|((i&1)<<(bit-1));
    for(rint i=0; i<n; ++i) c[i]=a[i];
    for(rint i=n; i<(1<<bit); ++i) c[i]=0;
    ntt(c, 1<<bit, 1), ntt(b, 1<<bit, 1);
    for(rint i=0; i<(1<<bit); ++i) b[i]=1LL*sub(2, 1LL*c[i]*b[i]%P)*b[i]%P;
    ntt(b, 1<<bit, -1);
    for(rint i=n; i<(1<<bit); ++i) b[i]=0;
}