用 $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 |$

【PA 2020】Miny

P9100 [PA 2020] Miny - 洛谷

给出每一个炸弹 $i$ 的位置 $a_i$ 和爆炸半径 $r_i$，每次爆炸都会使得 $[a_i - r_i, a_i + r_i]$ 范围内的炸弹爆炸，发生连锁反应。起爆的炸弹集合不定，问你最终的局面的方案数。

$1 \le n \le 3 \times 10 ^ 5, 0 \le a_i, r_i \le 10 ^ {18}$。

我们考虑 dp 的转移。

发现其实我们并不能得到一个很好的没有后效性的东西。

我们不妨发挥人类智慧，设计一个好的的 dp 状态。

我们设 $dp_i$ 表示，前 $i$ 个炸弹，以 $i$ 结尾，且钦定 $i$ 不爆炸的方案数。那么我们枚举 $j < i$ 进行转移，当且仅当 $[j + 1, i -1]$ 这部分的炸弹爆炸不会波及到 $i$ 和 $j$ 这样才能满足我们设定的不爆炸的钦定。 为了更好的判断是否波及，我们设 $L_i$ 表示左边能引爆 $i$ 的最大的炸弹，$R_i$ 表示右边能引爆 $i$ 的最小的炸弹。换言之就是最近且能引爆 $i$ 的。 这个过程我们可以用单调栈维护，我们可以通过单调栈，扫描两次，第一次求 $L$，第二次求 $R$，那么由于随着下标的增长，$a_i$ 是不断增加的，我们要想知道 $i$ 左边的第一个能引爆 $i$ 的，我们需要在单调栈中维护能覆盖 $a_i$ 的，最大的下标。若是当前的栈顶无法满足，就弹出，找前面的是否有能满足的。 对于这样的操作，我们再从后往前扫一次即可得到 $R$。

那么我们的 dp 可以转化为：

$$ dp_i = \min_{j < i \text{ and } (L_i \le j) \text{ and } (R_j \ge i)}(dp_i = dp_j + dp_i) $$

对于这个操作实际上是 $n ^ 2$ 的，我们考虑优化。

我们不难发现，满足条件 $L_i \le j$ 的序列，实际上下标直接就可以从 $L_i$ 开始一直到 $i$。

换言之，我们答案就是 $j \in [L_i, i - 1] \text{ and } R_j \ge i$ 的 $\sum dp_j$。

对于这样的询问，我们难免会想到在处理完当前的 $i$ 之后，把 $dp_i$ 插入到树状数组中，然后问 $[L_i, i - 1]$ 的时候，直接用树状数组做前缀和差分即可。

但是问题就在于，我们在询问 $L$ 的时候，插入的 $dp_i$ 实际上是只有 $[0, L]$ 的部分的 $R_j \ge i$ 的部分，可是留到最后算是会出问题的。

这个时候就可以用两种方式解决这个问题。

第一种方式是主席树，我们考虑把不同版本存下来，问 dp 的时候，只需要找到 $L_i - 1$ 的版本和 $i - 1$ 的版本即可。

第二种方式，我们把需要用到的询问离线下来，每次做完当前 $i$ 的操作之后，把挂在 $i$ 上的询问的答案都计算出来。

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