这是一道好题。

首先对于 $x_i=y_i$ 的部分，这是一个经典的点分治问题，可以直接用点分治解决。

对于 $x_i\ne y_i$ 的部分，假设 $x_i$ 为 $y_i$ 祖先，可以把符合条件的点分为 $x_i$ 子树外的和 $x_i$ 子树内的。

令 $f_{i,j}$ 表示子树 $i$ 内距离 $i$ 不超过 $j$ 的节点个数，前者可以通过点分治和 $f_{x_i,d}$ 作差求得。

对于后者，首先链上的点一定符合条件，其次考虑枚举链上某个点 $u$，并枚举 $u$ 的一个不在链上的儿子 $v$，加上 $f_{v,d-1}$。即为答案。

对于 $x_i$ 不为 $y_i$ 祖先的情况，考虑先求出 LCA 然后拆成两条竖直的链来做。综上，现在有了一个不知道什么复杂度的暴力做法了，考虑优化。

注意到：对于链上的 $u$ 以及想要计算的 $v$，绝大部分 $v$ 是 $u$ 的轻儿子。换句话说，对树进行轻重链剖分，则一条路径上只有 $\log n$ 条轻边。

考虑设 $g_{i,j}$ 表示 $i$ 的所有轻儿子子树中，距离 $i$ 不超过 $j$ 的节点个数，先求出竖直链上的 $g_{u,d}$ 之和，对于一条位于查询路径上的轻边 $(u,v)$，其中 $u$ 为 $v$ 的父亲，只需要减去 $f_{v,d-1}$ 然后加上 $f_{son(u),d-1}$ 即可正确处理这条轻边的贡献。

链上的 $g_{i,j}$ 之和可以通过树上差分求出，令 $G_{i,j}$ 表示 $1\to i$ 路径上所有点 $u$ 的 $g_{u,j}$ 之和。

现在我们要做的是：
1. $O(n)$ 次查询距离点 $x$ 不超过 $k$ 的点的个数。

2. $O(n\log n)$ 次查询 $x$ 子树内距离点 $x$ 不超过 $k$ 的点个数。

3. $O(n)$ 次查询 $G_{i,j}$。

第一个可以点分治做到 $O(n\log^2 n)$，第二个可以用 dfs 序转化为二维数点做到 $O(n\log^2 n)$，第三者可以先离线询问，dfs 时暴力遍历轻子树做到 $O(n\log^2 n)$，所以整个题就可以做到 $O(n\log^2 n)$。

因为本题的边边权均为 $1$，可以做到 $O(n\log n)$ 完成第 $1,3$ 个部分（具体的，我们直接维护前缀和，加入一个子树可以用 $O(siz)$ 的复杂度求出对前缀和数组 $O(siz)$ 个位置的影响），第二个部分使用长链剖分应该也能做到 $O(n\log n)$。所以本题应该是可以 $O(n\log n) $ 的。

当然我比较懒，所以只实现了 $O(n\log^2 n)$ 的，不过感觉 1log 可能也挺好写的？

用 $n=rc$ 指代地图大小。

首先一个地方到另外一个地方一定是沿着路径最大值最小的那个路径去的，显然是最小生成树，边权设置为两个端点的权值较大值。

考虑 kruskal 重构树，这样从 $x$ 出发不经过路径权值超过 $v$ 能得到的原图的点一定是一个子树的叶子节点。

现在问题就是单点改颜色和子树数颜色，其实有一个非常经典的 trick 叫树链求并。

具体的，当所有叶子颜色都不相同时，让每个叶子 $x$ 都对 $root\to x$ 的路径上权值加 $1$，一个点子树内的颜色数就是这个权值。

注意到，当两个叶子颜色相同时，有一部分点会算重两次，所以需要减去。

推广到一般形式，把颜色相同的所有叶子按照 dfs 序排序，对任意相邻两个节点的 LCA $x$ 执行 $root\to x$ 的路径减 $1$，即可完成去重。

用 set 维护同一种颜色的叶子的 dfs 序，只需要 $O(n)$ 次树状数组修改，复杂度为 $O(n\log n)$。

考虑dp，用$f_i$表示$A$集合比$B$集合多$i$个饼干时$A$集合的最大饼干数(然后按状态定义转移)，因为$i$可能是负数所以加一个$5e5$:

    #include<bits/stdc++.h>
    #define int long long
    using namespace std;
     
    const int V = 1e6 + 5;
    const int base = 5e5;
    const int N = 55;
     
    int n;
    int f[V],g[V];
     
    signed main()
    {
        freopen("cookie.in","r",stdin);
        freopen("cookie.out","w",stdout);
        ios::sync_with_stdio(0);
        cin.tie(0);
        cin>>n;
        memset(f,-0x3f,sizeof(f));
        memset(g,-0x3f,sizeof(g));
        g[base] = 0;
        for(int i = 1;i <= n;i++){
            int x;cin>>x;
            for(int j = 0;j <= V - 5;j++) if(j + x <= V - 5) f[j + x] = max(f[j + x],g[j] + x);
            for(int j = 0;j <= V - 5;j++) if(j - x >= 0) f[j - x] = max(f[j - x],g[j]);
            for(int j = 0;j <= V - 5;j++) g[j] = f[j];
        }
        
        cout<<f[base]<<'\n';
        
        return 0;
     }

by hl666:

奇思妙想题

首先考虑如果区间内存在某个质数$P$，则对于两个数 $x$ ,$y$ ，除非 $w(x)=w(LCM(x,y))$（即 $x$ 对应的质因子集合为 $y$ 对应的质因子集合的子集），否则不如用 $w(x)+1$ 的代价直接把 $x$ 和 $P$ 连起来

因此现在的做法就很显然了，先把所有质因子集合有包含关系的点连起来，最后把每个连通块和P

连起来即可

有一种比较好的处理方法是，对于某个数 $x$，我们令 $g(x)$ 为它的质因数集合中所有数的乘积（由于有去重，因此 $g(12)=2×3=6;g(27)=3$ ）

此时 $x$ 对应的质因子集合为 $y$ 对应的质因子集合的子集等价于 $g(x)$ 是 $g(y)$ 的约数，那么直接在上面跑一个调和级数的枚举即可

令 $M = \sum r_i$ ，总复杂度 $O(MlogM)$

但如果区间内没有质数怎么办呢，不难发现这样的区间长度一定不会很长，我们可以直接暴力跑生成树

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<vector>

#include<utility>

#define RI register int

#define CI const int&

using namespace std;

typedef pair <int,int> pi;

const int N=1e6+5;

struct edge

{

int x,y,w;

inline edge(CI X=0,CI Y=0,CI W=0)

{

x=X; y=Y; w=W;

}

friend inline bool operator < (const edge& A,const edge& B)

{

return A.w<B.w;

}

}; int t,l,r,w[N],g[N],vis[N],sz[N],is_prime[N],fa[N];

inline void init(CI n)

{

RI i,j; for (i=1;i<=n;++i) g[i]=1;

for (i=2;i<=n;++i) if (!w[i])

{

is_prime[i]=1; g[i]=i; w[i]=1;

for (j=i*2;j<=n;j+=i) ++w[j],g[j]=g[j]*i;

}

}

inline int getfa(CI x)

{

return fa[x]!=x?fa[x]=getfa(fa[x]):x;

}

int main()

{

for (scanf("%d",&t),init(1e6);t;--t)

{

RI i,j; scanf("%d%d",&l,&r); int ans=0;

if (l==1)

{

for (i=2;i<=r;++i) ans+=w[i];

printf("%d\n",ans); continue;

}

bool has_prime=0;

for (i=l;i<=r;++i) if (is_prime[i]) has_prime=1;

if (has_prime)

{

for (i=1;i<=r;++i) sz[i]=vis[i]=0;

for (i=l;i<=r;++i) ++sz[g[i]];

for (i=2;i<=r;++i) if (!vis[i]&&sz[i])

{

ans+=w[i]*(sz[i]-1)+(w[i]+1); vis[i]=1;

for (j=i*2;j<=r;j+=i) if (!vis[j]&&sz[j])

vis[j]=1,ans+=w[j]*sz[j];

}

printf("%d\n",ans-2);

} else

{

vector <edge> E; for (i=l;i<=r;++i) fa[i]=i;

for (i=l;i<=r;++i) for (j=l;j<=r;++j)

E.push_back(edge(i,j,w[i]+w[j]-w[__gcd(i,j)]));

sort(E.begin(),E.end());

for (auto [x,y,w]:E)

{

if (getfa(x)==getfa(y)) continue;

ans+=w; fa[getfa(x)]=getfa(y);

}

printf("%d\n",ans);

}

}

return 0;

}

出征

P16689 出征 - 洛谷

给出一个序列 $a_i$，和常数 $p$，你可以进行若干次操作，每次操作可以选择一个 $j$，使得 $i \in [j, n]$ 的后缀中，统一增加或减少 $\binom{i - j + p}{p}$。问至少多少次操作之后才能将序列全化为 $k$。

$1 \le n \le 10 ^ 5, 0 \le p \le 80, 0 \le k, a_i \le 10 ^ 6$。

对于这个题，还是很神奇的，实际上不是计数题。

我们可以先观察特殊性质，发现 $p = 0$ 的时候，就是选一个后缀，使得这个后缀统一增加或者减少 $1$，那这个我们是怎么做的呢，我们显然是可以从前往后判断，逐个满足每一个的要求，我们写暴力的时候发现，其实如果你在 $j$ 点进行了一次操作，其实不是很影响这个序列，不需要修改，只需要打上一个标记，后面的标记推下去计算即可。

于是我们就想到，是否操作只和单点有关，我们发现对于 $p = 0$ 的时候，我们将这个增加的贡献表达出来就是 $f(j) = [0, 0, 0, \dots, 1 ,1 ,1 , \dots]$，对于这个增加的贡献，我们可以对其做一次差分，得到的差分序列 $\Delta ^1 f(j) = [0, 0 ,0 ,\dots 1, 0, 0, \dots]$，发现进行一次差分之后，就变成与 $j$ 点相关的单点修改操作了。

具体的来说，我们每一次对选择的 $j$，后缀的增加或减少都是呈现 $f(j) = [0, 0, 0, \dots, \binom{p}{p}, \binom{p + 1}{p} , \binom{p + 2}{p} , \dots]$，这样的增加贡献，我们再考虑刚刚的差分操作，也就是，第一个位置不变，为 $\binom{p}{p}$，第二个位置是 $\binom{p + 1}{p} - \binom{p}{p} = p = \binom{p}{p - 1}$。这个部分实际上还可以用帕斯卡三角直接转化，因为 $\binom{p + 1}{p} = \binom{p}{p} + \binom{p}{p - 1}$，因此，移项就能得到。后面的同理，我们发现实际上一次差分会使得上下指标减 $1$，对于第一项，我们就可以把 $\binom{p}{p}$ 写成 $\binom{p - 1}{p - 1}$。我们可以写出通用式子的一阶差分 $\Delta^1 f(j) = [0, 0, 0, \dots, \binom{p - 1}{p - 1}, \binom{p}{p - 1}, \binom{p + 1}{p - 1}, \dots]$。很明显这个式子还能继续做差分，我们想要的是把这个变成单点的修改操作，这样就和 $p = 0$ 做一阶差分时的统计方式是一样的。

我们考虑只有经过 $p$ 轮，这样组合数选的就是 $0$，也就是又变回了我们的最初的 $p = 0$ 的情况，我们只需要再做一轮差分，就能得到最终我们想要的单点的修改贡献，即：

$$ \Delta ^ {p + 1} f(j) = [0, 0, 0, \dots, 1, 0, 0, \dots] $$

这样的式子，我们就可以清晰的看到具体哪个地方进行了操作。

因此我们的最终做法是，先把原数组 $a_i \gets k - a_i$，这样只需要判断到 $0$ 即可，对 $a_i$ 做 $p + 1$ 次差分，最后答案就是 $\sum |a_i|$。

为什么要开 int128 ？

我们考虑差分操作，对于 $\Delta ^ 1 a_i = 1\times a_i - 1\times a_{i - 1}$，对于 $\Delta ^ 2 a_i = 1 \times a_i - 1 \times a_{i - 1} - (1 \times a_{i - 1} - 1 \times a_{i - 2}) = 1 \times a_i - 2\times a_{i - 1} + 1\times a_{i - 2}$。

重复这个过程，我们发现其形态类似于二叉结构，每一个 $a_i$ 在做贡献时，都会在自己和前面的位置做一次贡献，这实际上就是帕斯卡三角的系数问题。

因此对于连续的 $p + 1$ 次，我们 $a_{i - j}$ 的贡献系数就是 $(-1) ^ j \binom{p + 1}{j}$，对于最坏的情况，我们把所有绝对值加起来，即 $\sum \binom{p + 1}{j} = 2 ^ {p + 1}$，因此对于 $2 ^ {81}$ 可以证明 int128 是可以存下的。

题目大意

就是说现在有序列 $a_1,a_2,a_3,...,a_n$ ，我们每一次操作可以选择一个位置 $i$ ，将 $i$ 这个后缀加或减一些数（如题）。然后我们要求出将序列变成 $k,k,k,k...$的最小操作数。

解题思路

我们先将给出的数组都减去 $k$ 得到一个“需求数组” $c_1,c_2,c_3,..,c_n$，我们的任务就是通过加减填满所有“需求”。但是我们暴力加的话是 $O(n^2)$ 的。

（我原本试图将 $ C_{i - j + p}^{p} $ 拆成 $i,j$ 独立的式子,但失败了。）

先说一个结论：

有两个序列 $A = a_1,a_2,a_3,...$ 和 $B = b_1,b_2,b_3,...$， $A + B$ 的差分序列 $= A$ 的差分序列 $+ B$ 的差分序列。即 $a_i + b_i - a_{i-1} - b_{i-1} = (a_i - a_{i-1}) + (b_i - b_{i-1})$

就是说我们将 ${c_1,c_2,c_3...}$ 和 $C_{p}^{p},C_{p + 1}^{p},C_{p + 2}^{p}...$ 都差分再用后者将前者全补成 $0$ 等价于原问题。

有

$$C_{n}^{m} = C_{n - 1}^{m - 1} + C_{n - 1}^{m}$$

在 $C_{p}^{p},C_{p + 1}^{p},C_{p + 2}^{p}...$ 中 $C_{p}^{p} = C_{p - 1}^{p - 1} = 1$,$C_{p + i}^{p} - C_{p + i - 1}^{p} = C_{p + i - 1}^{p - 1}$。也就是说对序列的一次差分就是将上下标都减1。

于是我们只要进行 $p$ 次差分就能将原序列变为 $1,1,1,1...$。$p + 1$ 次差分即为 $1,0,0,0,...$

所以我们将 $c$ 数组也进行 $p + 1$ 次差分,随后答案就是 $ans = \sum_{i = 1}^{n} | c_i |$