头像

ytczy666




离线:1天前



博客食用更佳~
https://www.cnblogs.com/czyty114/p/14766344.html

$\;$
题意: https://www.luogu.com.cn/problem/P7519

Solution

暴力

$\;$
暴力枚举每种排列,显然排名是按照$b_i$不降的顺序也单调升高
所以只需让当前队伍排第一的前提下让$b_i$的尽可能的小即可。
如果发现$\sum b_i <=m$,一定是存在一种方案的(让最后一个队伍过题数更多就行了)
$\;$

状压dp

$\;$
考虑设计状态。
首先目前已选队伍的集合S一定得有,然后是目前总过题数$k$
显然,你还关心上个队伍的编号和$b_j$
因为按照暴力的贪心思路,我们要让当前的$b_i$尽可能的小。假设上个队伍为$j$
即:$a_i+b_i\geq a_j+b_j,\;b_i\geq a_j+b_j-a_i$
但这样的时间复杂度是
$O(2^n \times n^2 \times m^2)$的
考虑简化状态。
再次考虑$b_i$的不降性,得到:$b_i=max(b_j, b_j+a_j-a_i)$,即:$b_i=b_j+max(0,a_j-a_i)$
最终我们一定选了$n$支队伍,那么$\sum b_i$一定是
$\sum max(0,a_j - a_i) \times (n- p_i +1)$
$p_i$代表$i$队伍是第几个选的。
换句话来说,第$i$支队伍对答案的贡献可以简化为$max(0,a_j -a_i)\times (n-p_i+1)$
所以我们没有必要知道$b_i$具体的值是多少,而是只需要知道他对最终答案的贡献是多少就可以了。
这实质是一个提前算贡献的思想(不关心过程,只关心它对最终结果造成的影响)
所以就可以把上个队伍$b_j$给删去。
而现在的$k$就不是目前选题总个数了(而是最终对答案影响的贡献)
最终复杂度:$O(2^n \times n^2 \times m)$

Code

#include <bits/stdc++.h>

const int N = 13, M = 505;

#define ll long long
int n, m, a[N];

ll f[1 << N][N + 1][M];
int main() {
    scanf("%d%d", &n, &m);
    int t = n;
    for (int i = 0; i < n; i ++) {
        scanf("%d", &a[i]);
        if (a[i] > a[t]) t = i;
    }
    for (int i = 0; i < n; i ++) {
        int add = n * (a[t] - a[i] + (i > t));
        if (add <= m) f[1 << i][i][add] = 1;
    }
    for (int i = 1; i < (1 << n); i ++) {
        int cnt = 0;
        for (int j = 0; j < n; j ++) if (i >> j & 1) cnt ++;
        for (int j = 0; j < n; j ++) if (i >> j & 1)
            for (int k = 0; k <= m; k ++) 
                for (int l = 0; l < n; l ++) if ((i | (1 << l)) != i) {
                    int add = (n - cnt) * std::max(0, a[j] - a[l] + (l > j));
                    if (k + add <= m) f[i | (1 << l)][l][k + add] += f[i][j][k];
                }
    }   
    ll ans = 0;
    for (int i = 0; i < n; i ++) 
        for (int j = 0; j <= m; j ++)
        ans += f[(1 << n) - 1][i][j];
    printf("%lld", ans);
    return 0;           
}



博客使用更佳:

https://www.cnblogs.com/czyty114/p/14742702.html
考试的时候已经尽我可能想到一半了,没想到最后我推的柿子竟然就是第一类斯特林数

题意

$\;$
初始时有一个$1$到$n$的排列,一次操作可以交换两个数的位置。
现在,对于所有的$i\;(1\leq i\leq k)$,求你恰好进行了$i$次操作,能得到的不同排列有多少种
$n\leq 10^9, k\leq 200$
$\;$
input
3 2
output
3 3
$\;$

$\;$

Solution

$\;$
不妨去想,如果初始的排列$1,2,\cdots,n$,其最少能通过$x$次变成一个排列$A$
那么一定也可以通过$x+2,x+4,\cdots$次操作变成$A$
反过来,通过$x+1,x+3,\cdots$这样次数的操作一定不可以变成$A$

如何求$x$?
我们倒过来想,把$A$变成$1,2,\cdots,n$
首先一个排列一定可以被划分成若干个圆(我习惯称其为轨道)
轨道是什么?
对于这个排列$2 \;5 \;4 \;3 \;1$,2占了1的位置,1占了5的位置,5占了2的位置,那么就构成了一个轨道${2,1,5}$
同理,还有${4,3}$这个轨道。
显然,每次操作,我们交换轨道的内的数是更优的。
而对于每个轨道,假如其长度为$r$,我们最少需要$r-1$次操作,把这个轨道内的数都恢复到原位。
所以假如说一个排列有$c$个轨道,我们最少只用进行$n-c$次操作,就可以把所有数回归原位
$\;$
考试的时候想到这里不会了。
考完,上网一查。
!第一类斯特林数(当场自闭
$\;$

第一类斯特林数

$\;$
$S1(n,m)$代表一个长度为$n$的排列被划分成$m$个轨道的方案数
显然
$S1(n,m)=S1(n-1,m-1)+(n-1)S1(n-1,m)$
但如果只是这样递推是$O(n^2)$的
而$n\leq 10^9$
$\;$

处理n很大的情况

$\;$
第一类斯特林数还有一个比较好的柿子:
$$S1(n,m)=(-1)^{n-m}\sum_{i=0}^{n-m} (-1)^i \times C(n-1+i,n-m+i) \times C(2n-m,n-m-i) \times S(n-m+i,i)$$
$\;$
但这玩意我不会证明,目前先知道就行
而我们现在要求的是$S1(n,n-i) (0\leq i\leq k)$
所以预处理出组合数和第二类斯特林数$O(k^3)$求解
$\;$

Code

#include <bits/stdc++.h>

const int N = 410, mod = 1000000007;

int n, k, fac[N], inv[N], S[N][N], dp[N];

int C(int n, int m) {
    int ans = 1;
    for (int i = n; i >= n - m + 1; i --) ans = 1ll * ans * i % mod;
    return 1ll * ans * inv[m] % mod;
}

int power(int a, int b) {
    int ans = 1;
    while(b) {
        if (b & 1) ans = 1ll * ans * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1; 
    }
    return ans;
}
int main() {
    scanf("%d%d", &n, &k);
    fac[0] = inv[0] = 1;
    for (int i = 1; i <= 400; i ++) {
        fac[i] = 1ll * fac[i - 1] * i % mod;
        inv[i] = power(fac[i], mod - 2);
    }
    S[0][0] = 1;
    for (int i = 1; i <= 400; i ++) 
        for (int j = 1; j <= i; j ++)
            S[i][j] = (S[i - 1][j - 1] + 1ll * j * S[i - 1][j] % mod) % mod;
    for (int i = 0; i <= k; i ++) // 求s(n,n-i)
        for (int j = 0; j <= i; j ++) {
            if (j & 1)
                dp[i] = (dp[i] - 1ll * C(n - 1 + j, i + j) * C(n + i, i - j) % mod * S[i + j][j] % mod + mod) % mod;
            else
                dp[i] = (dp[i] + 1ll * C(n - 1 + j, i + j) * C(n + i, i - j) % mod * S[i + j][j] % mod) % mod;
        } 
    for (int i = 1; i <= k; i ++) {
        int ans = 0;
        for (int j = 0; j <= i; j += 2)
            ans = (ans + dp[i - j]) % mod;
        if (i % 2 == 0) printf("%d ", ans);
        else printf("%d ", mod - ans);
    }
    return 0;
}



ytczy666
22天前

博客食用更佳 https://www.cnblogs.com/czyty114/p/14691097.html

个人感觉atcoder上的题质量确实很高,比较偏向于竞赛的题型。

A

$\;$
$n$个人,$m$道题,每道题有两个选项。现在给出了这$n$个人的作答,用$n$个长度为$m$的01串来表示。
问:有多少个$(i,j)$,满足第$i$个人和第$j$个人做对的题目数量不可能相同。
$n\leq 10^5,m\leq 20$
$\;$
显然,如果两个人有奇数道题的答案不一样,他们做对的题目数量不可能相同。
把每个人的答案看成二进制数,问题转化为:异或后有奇数个1的数对有多少个
然后我们发现,如果两个数满足一个有偶数个1,另一个有奇数个1,则一定是满足条件的。
否则一定不行。
简单试试就看出来了。
$\;$

B

$\;$
给定$n \times n$的矩阵$C$
问:能否构造出两个数组$A,B$,满足:$C_{i,j}=A_i+B_j$
$n \leq 500$
$\;$
显然$A$是每一行的最小值,$B$就是这行每一列的数与这行最小值的差
$O(n^2)$简单判断一下是否是无解情况就行了
$\;$

C

$\;$
要求构造出长度为$n$的序列,使得对于任意$i|j$的情况,$a_i\neq a_j$
要求序列的最大值最小。
$n\leq 10^5$
$\;$
考虑一个位置的数,限制条件就是它的因数们。
考虑dp,那么一个位置应填的数,一定要比它所有因数下标中,填的数最大的那个+1
即:$dp_i=max {dp_j } +1$,这里$j$是$i$的因数
所以我们也可以直接枚举倍数去dp,复杂度为调和级数:$O(n log n)$
$\;$

D

$\;$
给定$n$个点,$m$条边的无向图(不保证联通)。
从$m$条边中选出一些边,与$n$个点所构成的图叫做生成子图
问:对于$k=0,1\cdots ,n$
有$k$个点的度数为奇数的生成子图有多少个。
$n\leq 5000$
$\;$
对于$k$为奇数的情况,答案就是0
然后考虑的情况:
我们发现$ans_k=C_n^k$
为什么?
我们从这$n$个点中选出$k$个点,然后一定保证有且只有一种构造(选边)方案,使得这$k$个点度数都为奇数。
下面我们把那$k$个点称作关键点
证明:因为是$k$是偶数,所以我们进行两两配对。这样路径的两个端点奇偶性一定会发生变化,且路径中间的点奇偶性不会变。
而且我们必须从下往上逐渐进行配对,每次找到深度最深的点$x$,满足它至少有两个子树中都有1个关键点
然后两两配对。又发现,配对的过程,必须是选这些关键点与$x$之间的路径上的边。
感性理解一下就好。
$\;$
然后考虑非树(即)的情况
我们一定可以从中找到一颗生成树,剩下$m-n+1$条边不是树上的边。
这$m-n+1$条边可以随便选。然后剩下的边又变成了树的情况
虽然选非树边会改变某些点的奇偶性,但是由于变成奇点的数量也一定是偶数个,而$k$也是偶数。
你会发现这两个玩意合并起来,只考虑树边使要变为奇点的(这里的奇点是只考虑树边贡献的度数)数量也一定是偶数。
这其实与$A$的思路有些类似。
因此,图的情况即是$C_n^k \times 2^{m-n+1}$
$\;$
若有多个连通图,那么只需进行一次简单的dp。
怎么dp就比较显然了。
看起来dp的复杂度是$O(n^3)$的(也有可能是我自己sb了),实际上是$O(n^2)$




ytczy666
22天前

博客食用更佳 https://www.cnblogs.com/czyty114/p/14678032.html

B

$\;$

题意

$\;$
给定一个长度为$n$的初始序列$A$
可以进行任意多次操作,每次操作可以选定一个正整数$x$,将所有值$\geq x$的数减一
问最终可以得到的序列有多少种
$n\leq 10^5,a_i\leq 10^9$
input
2
1 2
output
4
$\;$

Solution

$\;$
将初始序列不降排序之后,显然每次操作会将一段后缀的值减去1
你会发现一个很重要的性质:相邻两个数的差只会变小或不变,一定不会变大。
所以,如果我们如果得到了一个序列$B$,满足$\forall 1 \leq i \leq n, B_i-B_{i-1} \leq A_i - A_{i-1}$
一定可以构造出一种操作方案,使得$A$变成$B$
令$A_0=0$
因此:
$$Ans = \prod_{i=1}^n (a_i-a_{i-1}+1)$$
$\;$

C

题意

$\;$
给定一个长度为$n$的字符串s,只有W,R,B三种字符,分别代表白、红、蓝。
初始时,一排$n$个方格按照字符串涂好颜色,然后按照金字塔的形状不断向上摞方格。
规则是这样的:
如果相邻的两个颜色都为x,会摞上一个颜色为x的方格。
否则会摞上一个和这两个方格颜色都不同的方格。
问最顶端的方格颜色
$n\leq 4 \times 10^5$
input
RRBB
output
W
$\;$

Solution

$\;$
思维好题。
不妨将三种颜色分别设为0,1,2
假设相邻两个方格颜色为$a, b$,那么摞上的方格的颜色将为:
$$-(a+b)\;(mod \;3)$$
$\;$
所以和杨辉三角一样不断往上加,可以手推一下。
发现顶端的值为
$$(-1)^{n-1} \times \sum_{i=0}^{n-1} C_{n-1}^i s_i\; (mod \; 3)$$
$\;$
因为阶乘可能是3的倍数,所以不大好处理逆元。
可以使用Lucas定理轻松解决
Lucas: 若$p$是质数,$C(n,m) = C(n/p,m/p) \times C(n\%p,m\%p)$
时间复杂度:$O(n\;log\;n)$
$\;$

E

$\;$

题意

$\;$
问有多少个长度为$2n$的序列$A$满足以下条件:
1.恰好有$n$个1和$n$个-1
2.恰好有$k$个$(l,r)$,满足$a_l+a_{l+1}+\cdots +a_r = 0$
$n\leq 30, k\leq n^2$
input
3 7
output
6
$\;$

Solution

$\;$
又是计数dp题
前缀和转化一下比较显然。
如果只是简单的从前往后做,考虑是+1还是-1的话是不行的。
不妨先考虑$s_i$全部非负的情况。
$dp_{i,j,k}$表示当前填了$i$个数,且有$j$个$(l,r)$满足条件,目前填的数中$hole$的数量为$k$的方案数。
$hole$表示序列中相邻两个元素值相同之间的空隙。
由于我们最终的$s$序列一定是波浪的形状。
所以一次转移会加入一些相同数值的元素$val$,插入到这些空隙中(包括序列最左最右)
且这$k+2$个位置必须都要有$val$这个数
这样转移的好处是既方便去统计$(l,r)$的个数,还能保证这个序列这个序列是合法的。
假设填了$x$个数
那么转移就是$dp_{i+x,j+\frac{x(x+1)}{2},x-(k+2)}=dp_{i,j,k} \times C_{x-1}^{k+1}$
这个组合数可以用插板的思想去想。
最终统计答案时,我们把序列分为两部分:非负和负的。
而上下两部分都是满足刚刚dp的东西的。
所以直接乘法原理。
即:枚举$(x,y,z)$ 答案加上$dp_{x,y,z}\times dp_{2n+1-x,k-y,z-1}$
时间复杂度:$O(n^5)$



新鲜事 原文

ytczy666
1个月前
明天月考,自闭啊



ytczy666
1个月前

个人感觉atcoder上的题质量确实很高,比较偏向于竞赛的题型。

A

$\;$
$n$个人,$m$道题,每道题有两个选项。现在给出了这$n$个人的作答,用$n$个长度为$m$的01串来表示。
问:有多少个$(i,j)$,满足第$i$个人和第$j$个人做对的题目数量不可能相同。
$n\leq 10^5,m\leq 20$
$\;$
显然,如果两个人有奇数道题的答案不一样,他们做对的题目数量不可能相同。
把每个人的答案看成二进制数,问题转化为:异或后有奇数个1的数对有多少个
然后我们发现,如果两个数满足一个有偶数个1,另一个有奇数个1,则一定是满足条件的。
否则一定不行。
简单试试就看出来了。
$\;$

B

$\;$
给定$n \times n$的矩阵$C$
问:能否构造出两个数组$A,B$,满足:$C_{i,j}=A_i+B_j$
$n \leq 500$
$\;$
显然$A$是每一行的最小值,$B$就是这行每一列的数与这行最小值的差
$O(n^2)$简单判断一下是否是无解情况就行了
$\;$

C

$\;$
要求构造出长度为$n$的序列,使得对于任意$i|j$的情况,$a_i\neq a_j$
要求序列的最大值最小。
$n\leq 10^5$
$\;$
考虑一个位置的数,限制条件就是它的因数们。
考虑dp,那么一个位置应填的数,一定要比它所有因数下标中,填的数最大的那个+1
即:$dp_i=max {dp_j } +1$,这里$j$是$i$的因数
所以我们也可以直接枚举倍数去dp,复杂度为调和级数:$O(n log n)$
$\;$

D

$\;$
给定$n$个点,$m$条边的无向图(不保证联通)。
从$m$条边中选出一些边,与$n$个点所构成的图叫做生成子图
问:对于$k=0,1\cdots ,n$
有$k$个点的度数为奇数的生成子图有多少个。
$n\leq 5000$
$\;$
对于$k$为奇数的情况,答案就是0
然后考虑的情况:
我们发现$ans_k=C_n^k$
为什么?
我们从这$n$个点中选出$k$个点,然后一定保证有且只有一种构造(选边)方案,使得这$k$个点度数都为奇数。
下面我们把那$k$个点称作关键点
证明:因为是$k$是偶数,所以我们进行两两配对。这样路径的两个端点奇偶性一定会发生变化,且路径中间的点奇偶性不会变。
而且我们必须从下往上逐渐进行配对,每次找到深度最深的点$x$,满足它至少有两个子树中都有1个关键点
然后两两配对。又发现,配对的过程,必须是选这些关键点与$x$之间的路径上的边。
感性理解一下就好。
$\;$
然后考虑非树(即)的情况
我们一定可以从中找到一颗生成树,剩下$m-n+1$条边不是树上的边。
这$m-n+1$条边可以随便选。然后剩下的边又变成了树的情况
虽然选非树边会改变某些点的奇偶性,但是由于变成奇点的数量也一定是偶数个,而$k$也是偶数。
你会发现这两个玩意合并起来,只考虑树边使要变为奇点的(这里的奇点是只考虑树边贡献的度数)数量也一定是偶数。
这其实与$A$的思路有些类似。
因此,图的情况即是$C_n^k \times 2^{m-n+1}$
$\;$
若有多个连通图,那么只需进行一次简单的dp。
怎么dp就比较显然了。
看起来dp的复杂度是$O(n^3)$的(也有可能是我自己sb了),实际上是$O(n^2)$




ytczy666
2个月前

博客食用更佳~ https://www.cnblogs.com/czyty114/p/14432462.html

$\;$
莫队是一类离线区间询问问题,经常应用于需要维护的信息无法合并时(如线段树等)
其核心思想是:维护两个指针$l,r$。在已知$[l,r]$这段区间的信息的前提下,两个指针分别移动到$l’,r’$的过程中,实时地维护答案。从而算出区间$[l,r]的信息$
$\;$

引入

$\;$
因为题目没有强制在线,所以莫队算法是将所有的询问按一定顺序排好序,并且一次询问是以上一次询问为基础。
我们可以把一次询问$l,r$看作二维平面上的一个点$(l,r)$,那我们在两次询问间$l,r$指针一共移动的距离,实质上是$(l_1,r_1)$,$(l_2,r_2)$间的曼哈顿距离
但求最小哈密尔顿路径又是无法做到的。所以我们需要找到一个合适的顺序,使得两指针移动的距离尽可能的小。
$\;$

普通莫队

$\;$

核心

$\;$
假设现在给定你一个长为$n$的序列,$m$次询问,每次询问求$[l,r]$这段区间不同数的数量。
$n,m\leq 10^5$
对于这个问题来说,用线段树是很难去维护的。因为区间不同数的数量并不能很轻松地由左右子区间转移而来。
考虑将整个序列分块,每段长度为$\sqrt n$
这样每段询问区间的左右端点必定位于某个块中。
我们把区间左端点所属的块的编号作为第一关键字,右端点的位置作为第二关键字,将询问区间排序。
按照莫队的思想,我们按此顺序依次处理每一个区间,在两个指针的移动的过程中维护一个数组cnt,表示每一个数出现的次数。
若发现某个数cnt为由1减为0了,将答案减1,反之则加1
$\;$

时间复杂度

$\;$
我们发现算法中时间的瓶颈就在于,左右指针总共会移动多少次。我们分开来看:
(注意:这里我们假设m与n同阶)
$\;$
左端点
$\;$
因为第一关键字是按左端点所在块排序的,所以左端点所在块是单调不降的。
对于目前左端点与上一个左端点同属一个块的情况:最多出现$n$次,但每一次两个点之间移动的距离不超过$\sqrt n$
因此:$O(n\sqrt n)$
对于目前左端点与上一个左端点不同属一个块的情况:最多出现$\sqrt n$次,但每一次两个点之间移动的距离不超过$n$
因此:$O(n\sqrt n)$
$\;$
右端点
$\;$
其位置作为第二关键字。因此若左端点有若干个位于同一个块中,此时右端点应该是单调不降的。
因此对于同一个块的左端点,右端点至多移动$n$次,而总共有$\sqrt n$个块
因此:$O(n\sqrt n)$
否则,若左端点不在同一个块中,右端点的位置就无法确定了。这样一次右端点至多移动$n$次
但这种情况至多出现$\sqrt n$次
因此:$O(n\sqrt n)$
$\;$
综上所述,莫队算法的时间复杂度为$O(n\sqrt n)$

Code

#include <bits/stdc++.h>

const int N = 50010, M = 200010;
int n, m, a[N], b[N], ans[M], id[N], sq, nn, cnt[N];
struct node {
    int pos, l, r;
}ask[M];
bool cmp(node a, node b) {
    if(id[a.l] != id[b.l]) return id[a.l] < id[b.l]; // 左端点所属块 
    return a.r < b.r; // 右端点所属位置 
}
int main() {
    scanf("%d", &n);
    sq = (int)sqrt(n);
    for(int i=1;i<=n;i++) id[i] = (int)ceil(i / sq); // 预处理每个点所属块的编号 
    for(int i=1;i<=n;i++) scanf("%d", &a[i]), b[i] = a[i];
    std::sort(b + 1, b + n + 1);
    nn = std::unique(b + 1, b + n + 1) - b - 1;
    for(int i=1;i<=n;i++) a[i] = std::lower_bound(b + 1, b + nn + 1, a[i]) - b;
    //----------------- 上面是离散化部分,不多赘述 
    scanf("%d", &m);
    for(int i=1;i<=m;i++) scanf("%d%d", &ask[i].l, &ask[i].r), ask[i].pos = i;
    std::sort(ask + 1, ask + m + 1, cmp);
    int x = 0, y = 0, res = 0; //x,y维护的是一直在移动两个指针 
    for(int i=1;i<=m;i++) {
        int l = ask[i].l, r = ask[i].r; // l,r是当前询问的两个左右端点 
        while(x < l) { // 左端点向右移,区间缩小 
            cnt[a[x]] --; if(!cnt[a[x]]) -- res;
            x ++;
        }

        while(x > l) { // 左端点向左移,区间变大 
            cnt[a[x - 1]] ++; if(cnt[a[x - 1]] == 1) ++ res;
            x --;
        }

        while(y < r) { // 右端点向右移,区间变大 
            cnt[a[y + 1]] ++; if(cnt[a[y + 1]] == 1) ++ res;
            y ++;
        }

        while(y > r) { // 右端点向左移,区间缩小 
            cnt[a[y]] --; if(!cnt[a[y]]) -- res;
            y --;
        }

        ans[ask[i].pos] = res; // 注意:i是排序后区间的编号,但并不是输入时询问的编号 
    }
    for(int i=1;i<=m;i++) printf("%d\n", ans[i]);
    return 0;
}

带修莫队

$\;$
一般的莫队实质上是不支持修改操作的,但如果这个修改操作很简单,比较容易维护,我们还是可以实现的。
而带修莫队的分块方式与普通莫队不同。
现在我们把序列分为$n^{\frac{1}{3}}$个块,每个块的长度为$n^{\frac{2}{3}}$
对于操作来说,我们把修改和询问分开。
对于询问:左端点所在块为第一关键字,右端点所在块为第二关键字,时间(输入的时候排第几行)为第三关键字进行排序。
那么,与普通莫队类似。只需多维护一个修改的操作。
即:假设两个询问的时间分别为$t_1,t_2$,我们只需把$[t_1,t_2]$这段时间内的修改操作执行一遍(时光正流或倒流)
$\;$

时间复杂度

$\;$
时间指针
当左右端点所在块不变时。对于每种两个块组合的方案,因为时间是递增的,所以最多执行$O(n)$次,一共有$n^{\frac{2}{3}}$种方案,故为$O(n^{\frac{5}{3}})$
当左端点所在块不变,右端点递增时,也只会出现$n^{\frac{2}{3}}$次,每次$O(n)$,故为$O(n^{\frac{5}{3}})$
当左端点所在块变化时,只会出现$n^{\frac{1}{3}}$次,每次$O(n)$,故为$O(n^{\frac{4}{3}})$
综上:为$O(n^{\frac{5}{3}})$
$\;$
右端点
当左右端点所在块不变时。$n$次询问,每次最多移动$n^{\frac{2}{3}}$,故为$O(n^{\frac{5}{3}})$
当左端点所在块不变,右端点递增时,会出现$n^{\frac{1}{3}}$次,每次$O(n)$,故为$O(n^{\frac{4}{3}})$
当左端点所在块变化时,与上面类似,也为$O(n^{\frac{4}{3}})$
综上:为$O(n^{\frac{5}{3}})$
$\;$
左端点
当左端点所在块不变时,与上面的情况一样。为$O(n^{\frac{5}{3}})$
而最多会变$n^{\frac{1}{3}}$次,因为是按左端点所在块为第一关键字排序的。所以变化这一部分是$O(n)$的
综上:为$O(n^{\frac{5}{3}})$
$\;$

Code

$\;$
例题:P1903 数颜色
https://www.luogu.com.cn/problem/P1903

#include <bits/stdc++.h>

#define fi first
#define se second
const int N = 143333;
int n, m, k, a[N], cnt[N * 10], ans[N], id[N], sq, T, b[N], res, x, y;
std::pair<int,int> cur[N], fur[N];
struct node {
    int l, r, t, pos;
}ask[N];

bool cmp(node a, node b) {
    if(id[a.l] != id[b.l]) return id[a.l] < id[b.l];
    if(id[a.r] != id[b.r]) return id[a.r] < id[b.r];
    return a.t < b.t;
}

bool g(int d) {
    return (x <= d && d <= y);
}
void gg(int x, int y) {
    cnt[x] --; cnt[y] ++;
    if(!cnt[x]) -- res; if(cnt[y] == 1) ++ res;
}
int main() {
    scanf("%d%d", &n, &m);
    sq = pow(n, 3.0 / 4);
    for(int i=1;i<=n;i++) id[i] = (int)ceil(i / sq);
    for(int i=1;i<=n;i++) scanf("%d", &a[i]), b[i] = a[i];
    for(int i=1;i<=m;i++) {
        char op[5]; int l, r;
        scanf("%s", op);
        scanf("%d%d", &l, &r);
        if(op[0] == 'Q') {
            ++ k; ask[k].l = l; ask[k].r = r; ask[k].t = i; ask[k].pos = k;
        }
        else {
            cur[i].fi = l; cur[i].se = r;
            fur[i].fi = l; fur[i].se = b[l]; b[l] = r;
        }
    }
    std::sort(ask + 1, ask + k + 1, cmp);
    int ti = 0;
    for(int i=1;i<=k;i++) {
        int t = ask[i].t, l = ask[i].l, r = ask[i].r;
        while(ti < t) {
            if(!cur[ti + 1].fi) {
                ti ++; continue;
            }
            if(g(cur[ti + 1].fi)) gg(a[cur[ti + 1].fi], cur[ti + 1].se);
            a[cur[ti + 1].fi] = cur[ti + 1].se;
            ti ++;
        } 
        while(ti > t) {
            if(!fur[ti].fi) {
                ti --; continue;
            }
            if(g(fur[ti].fi)) gg(a[fur[ti].fi], fur[ti].se);
            a[fur[ti].fi] = fur[ti].se; 
            ti --; 
        }
        while(x < l) {
            cnt[a[x]] --; if(!cnt[a[x]]) -- res;
            x ++;
        }
        while(x > l) {
            cnt[a[x - 1]] ++; if(cnt[a[x - 1]] == 1) ++ res;
            x --;
        } 
        while(y < r) {
            cnt[a[y + 1]] ++; if(cnt[a[y + 1]] == 1) ++ res;
            y ++;
        }
        while(y > r) {
            cnt[a[y]] --; if(!cnt[a[y]]) -- res;
            y --;
        }
        ans[ask[i].pos] = res;
    }
    for(int i=1;i<=k;i++) printf("%d\n", ans[i]);
    return 0;
}

$\;$

树上莫队

$\;$

核心

$\;$
只不过把序列的问题搬到了树上,区间也就变成了一条链。
我们将树分块。
具体实现方法是:维护一个栈,代表目前待选的点的集合S。dfs到某个点u的时候,遍历它的所有子树并统计目前集合S的大小,在遍历的过程中,如果发现集合S的大小已超过规定的块大小,将这些点分为一块。
可以注意到,因为我们是按dfs的顺序进行编号的。所以相邻编号的块在树上也一定是相邻的,这样就会满足莫队的复杂度。
而因为不是在序列上,所以我们不能简单的对左右指针+1或-1
假如上一次询问的链是$(x,y)$,这次是$(u,v)$,那么只需对$(x,u)$和$(y,v)$这两条链上的点的标记进行取反操作。
最终$(u,v)$上的所有点会被标为1。这个可以通过画图理解。
不过在实现的时候,还要注意一些细节:比如说LCA可能要特殊处理,可以参考代码理解。
那么剩余的就和普通、带修莫队一样了。
$\;$

Code

$\;$
例题:P4074 糖果公园
https://www.luogu.com.cn/problem/P4074
$\;$

#include <bits/stdc++.h>

const int N = 100010;

int n, m, k, q, top, val[N], w[N], tim[N], stk[N], idx, dfn[N], dep[N], S, lst[N], id[N], scc, c[N], bc[N];
int upd[N], pre[N], d[N], x, y, vis[N], f[N][20];
long long ans, res[N];
std::vector<int> G[N];
int read() {
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
        x = x * 10 + c - '0', c = getchar();
    return f * x;
}
int dfs(int u, int fa) {
    int re = 0; 
    dfn[u] = ++idx; 
    f[u][0] = lst[u] = fa; 
    dep[u] = dep[fa] + 1;
    for(int i=1;i<=19;i++) f[u][i] = f[f[u][i - 1]][i - 1];
    for(int i=0;i<G[u].size();i++) {
        int v = G[u][i];
        if(v == fa) continue;
        re += dfs(v, u);
        if(re >= S) {
            scc ++;
            while(re) 
                id[stk[top --]] = scc, re --;
        }
    }
    stk[++top] = u;
    return re + 1;
}
struct node {
    int l, r, pos, t;
}ask[N];
bool cmp(node a, node b) {
    if(id[a.l] != id[b.l]) return id[a.l] < id[b.l];
    if(id[a.r] != id[b.r]) {
        if(id[a.l] & 1) return id[a.r] < id[b.r];
        return id[a.r] > id[b.r];
    }
    return a.pos < b.pos;
}
int lca(int x, int y) {
    if(x == y) return x;
    if(dep[x] < dep[y]) std::swap(x, y);
    int ch = dep[x] - dep[y], er = 0;
    while(ch) {
        if(ch & 1) x = f[x][er];
        ch >>= 1; er ++; 
    }
    if(x == y) return x;
    for(int i=19;~i;i--) {
        if(f[x][i] == f[y][i]) continue;
        x = f[x][i]; y = f[y][i];
    }
    return f[x][0];
}
void change(int d, int v) {
    if(vis[d]) {
        ans = ans - 1ll * w[tim[c[d]] --] * val[c[d]];
        ans = ans + 1ll * w[++ tim[v]] * val[v];
        c[d] = v;
    }
    else c[d] = v;
}
void modify(int x) {
    if(vis[x]) {
        vis[x] = 0;
        ans = ans - 1ll * val[c[x]] * w[tim[c[x]] --]; 
    }
    else {
        vis[x] = 1;
        ans = ans + 1ll * val[c[x]] * w[++tim[c[x]]];
    }
}
void make_tag(int u, int v) {
    while(u != v) {
        if(dep[u] > dep[v]) modify(u), u = f[u][0];
        else modify(v), v = f[v][0];
        //printf("%d %d\n", u, v);
    }
} 
int main() {
    n = read(); m = read(); q = read();
    S = pow(n, 0.666); 
    for(int i=1;i<=m;i++) val[i] = read();
    for(int i=1;i<=n;i++) w[i] = read();
    for(int i=1;i<n;i++) {
        int u, v;
        u = read(); v = read();
        G[u].push_back(v); G[v].push_back(u);
    }
    dfs(1, 0);
    scc ++;
    for(int i=1;i<=n;i++) if(!id[i]) id[i] = scc;
    for(int i=1;i<=n;i++) c[i] = read(), bc[i] = c[i];
    for(int i=1;i<=q;i++) { 
        int op, l, r;
        op = read(); l = read(); r = read();
        if(!op) {
            upd[i] = r; d[i] = l; pre[i] = bc[l]; bc[l] = r;
        }
        else {
            if(dfn[l] > dfn[r]) std::swap(l, r);
            ask[++k].l = l; ask[k].r = r; ask[k].t = i; ask[k].pos = k;
        }
    }
    std::sort(ask + 1, ask + k + 1, cmp);
    for(int i=1;i<ask[1].t;i++) {
        if(!upd[i]) continue;
        change(d[i], upd[i]); 
    }
    x = ask[1].l; y = ask[1].r; 
    make_tag(x, y); modify(lca(x, y));
    res[ask[1].pos] = ans;
    modify(lca(x, y));
    for(int i=2;i<=k;i++) {
        int l = ask[i].l, r = ask[i].r;
        // time
        int t = ask[i].t, p = ask[i - 1].t;
        while(p < t) {
            p ++;
            if(upd[p]) change(d[p], upd[p]); 
        }
        while(p > t) {
            if(upd[p]) change(d[p], pre[p]);
            p --;
        }
        make_tag(x, l);
        make_tag(y, r); 
        modify(lca(l, r));
        res[ask[i].pos] = ans;
        modify(lca(l, r));
        x = l; y = r;
    }
    for(int i=1;i<=k;i++) printf("%lld\n", res[i]);
    return 0;
}



ytczy666
2个月前

博客食用更佳~ https://www.cnblogs.com/czyty114/p/14432462.html

$\;$
莫队是一类离线区间询问问题,经常应用于需要维护的信息无法合并时(如线段树等)
其核心思想是:维护两个指针$l,r$。在已知$[l,r]$这段区间的信息的前提下,两个指针分别移动到$l’,r’$的过程中,实时地维护答案。从而算出区间$[l,r]的信息$
$\;$

引入

$\;$
因为题目没有强制在线,所以莫队算法是将所有的询问按一定顺序排好序,并且一次询问是以上一次询问为基础。
我们可以把一次询问$l,r$看作二维平面上的一个点$(l,r)$,那我们在两次询问间$l,r$指针一共移动的距离,实质上是$(l_1,r_1)$,$(l_2,r_2)$间的曼哈顿距离
但求最小哈密尔顿路径又是无法做到的。所以我们需要找到一个合适的顺序,使得两指针移动的距离尽可能的小。
$\;$

普通莫队

$\;$

核心

$\;$
假设现在给定你一个长为$n$的序列,$m$次询问,每次询问求$[l,r]$这段区间不同数的数量。
$n,m\leq 10^5$
对于这个问题来说,用线段树是很难去维护的。因为区间不同数的数量并不能很轻松地由左右子区间转移而来。
考虑将整个序列分块,每段长度为$\sqrt n$
这样每段询问区间的左右端点必定位于某个块中。
我们把区间左端点所属的块的编号作为第一关键字,右端点的位置作为第二关键字,将询问区间排序。
按照莫队的思想,我们按此顺序依次处理每一个区间,在两个指针的移动的过程中维护一个数组cnt,表示每一个数出现的次数。
若发现某个数cnt为由1减为0了,将答案减1,反之则加1
$\;$

时间复杂度

$\;$
我们发现算法中时间的瓶颈就在于,左右指针总共会移动多少次。我们分开来看:
(注意:这里我们假设m与n同阶)
$\;$
左端点
$\;$
因为第一关键字是按左端点所在块排序的,所以左端点所在块是单调不降的。
对于目前左端点与上一个左端点同属一个块的情况:最多出现$n$次,但每一次两个点之间移动的距离不超过$\sqrt n$
因此:$O(n\sqrt n)$
对于目前左端点与上一个左端点不同属一个块的情况:最多出现$\sqrt n$次,但每一次两个点之间移动的距离不超过$n$
因此:$O(n\sqrt n)$
$\;$
右端点
$\;$
其位置作为第二关键字。因此若左端点有若干个位于同一个块中,此时右端点应该是单调不降的。
因此对于同一个块的左端点,右端点至多移动$n$次,而总共有$\sqrt n$个块
因此:$O(n\sqrt n)$
否则,若左端点不在同一个块中,右端点的位置就无法确定了。这样一次右端点至多移动$n$次
但这种情况至多出现$\sqrt n$次
因此:$O(n\sqrt n)$
$\;$
综上所述,莫队算法的时间复杂度为$O(n\sqrt n)$

Code

#include <bits/stdc++.h>

const int N = 50010, M = 200010;
int n, m, a[N], b[N], ans[M], id[N], sq, nn, cnt[N];
struct node {
    int pos, l, r;
}ask[M];
bool cmp(node a, node b) {
    if(id[a.l] != id[b.l]) return id[a.l] < id[b.l]; // 左端点所属块 
    return a.r < b.r; // 右端点所属位置 
}
int main() {
    scanf("%d", &n);
    sq = (int)sqrt(n);
    for(int i=1;i<=n;i++) id[i] = (int)ceil(i / sq); // 预处理每个点所属块的编号 
    for(int i=1;i<=n;i++) scanf("%d", &a[i]), b[i] = a[i];
    std::sort(b + 1, b + n + 1);
    nn = std::unique(b + 1, b + n + 1) - b - 1;
    for(int i=1;i<=n;i++) a[i] = std::lower_bound(b + 1, b + nn + 1, a[i]) - b;
    //----------------- 上面是离散化部分,不多赘述 
    scanf("%d", &m);
    for(int i=1;i<=m;i++) scanf("%d%d", &ask[i].l, &ask[i].r), ask[i].pos = i;
    std::sort(ask + 1, ask + m + 1, cmp);
    int x = 0, y = 0, res = 0; //x,y维护的是一直在移动两个指针 
    for(int i=1;i<=m;i++) {
        int l = ask[i].l, r = ask[i].r; // l,r是当前询问的两个左右端点 
        while(x < l) { // 左端点向右移,区间缩小 
            cnt[a[x]] --; if(!cnt[a[x]]) -- res;
            x ++;
        }

        while(x > l) { // 左端点向左移,区间变大 
            cnt[a[x - 1]] ++; if(cnt[a[x - 1]] == 1) ++ res;
            x --;
        }

        while(y < r) { // 右端点向右移,区间变大 
            cnt[a[y + 1]] ++; if(cnt[a[y + 1]] == 1) ++ res;
            y ++;
        }

        while(y > r) { // 右端点向左移,区间缩小 
            cnt[a[y]] --; if(!cnt[a[y]]) -- res;
            y --;
        }

        ans[ask[i].pos] = res; // 注意:i是排序后区间的编号,但并不是输入时询问的编号 
    }
    for(int i=1;i<=m;i++) printf("%d\n", ans[i]);
    return 0;
}

带修莫队

$\;$
一般的莫队实质上是不支持修改操作的,但如果这个修改操作很简单,比较容易维护,我们还是可以实现的。
而带修莫队的分块方式与普通莫队不同。
现在我们把序列分为$n^{\frac{1}{3}}$个块,每个块的长度为$n^{\frac{2}{3}}$
对于操作来说,我们把修改和询问分开。
对于询问:左端点所在块为第一关键字,右端点所在块为第二关键字,时间(输入的时候排第几行)为第三关键字进行排序。
那么,与普通莫队类似。只需多维护一个修改的操作。
即:假设两个询问的时间分别为$t_1,t_2$,我们只需把$[t_1,t_2]$这段时间内的修改操作执行一遍(时光正流或倒流)
$\;$

时间复杂度

$\;$
时间指针
当左右端点所在块不变时。对于每种两个块组合的方案,因为时间是递增的,所以最多执行$O(n)$次,一共有$n^{\frac{2}{3}}$种方案,故为$O(n^{\frac{5}{3}})$
当左端点所在块不变,右端点递增时,也只会出现$n^{\frac{2}{3}}$次,每次$O(n)$,故为$O(n^{\frac{5}{3}})$
当左端点所在块变化时,只会出现$n^{\frac{1}{3}}$次,每次$O(n)$,故为$O(n^{\frac{4}{3}})$
综上:为$O(n^{\frac{5}{3}})$
$\;$
右端点
当左右端点所在块不变时。$n$次询问,每次最多移动$n^{\frac{2}{3}}$,故为$O(n^{\frac{5}{3}})$
当左端点所在块不变,右端点递增时,会出现$n^{\frac{1}{3}}$次,每次$O(n)$,故为$O(n^{\frac{4}{3}})$
当左端点所在块变化时,与上面类似,也为$O(n^{\frac{4}{3}})$
综上:为$O(n^{\frac{5}{3}})$
$\;$
左端点
当左端点所在块不变时,与上面的情况一样。为$O(n^{\frac{5}{3}})$
而最多会变$n^{\frac{1}{3}}$次,因为是按左端点所在块为第一关键字排序的。所以变化这一部分是$O(n)$的
综上:为$O(n^{\frac{5}{3}})$
$\;$

Code

$\;$
例题:P1903 数颜色
https://www.luogu.com.cn/problem/P1903

#include <bits/stdc++.h>

#define fi first
#define se second
const int N = 143333;
int n, m, k, a[N], cnt[N * 10], ans[N], id[N], sq, T, b[N], res, x, y;
std::pair<int,int> cur[N], fur[N];
struct node {
    int l, r, t, pos;
}ask[N];

bool cmp(node a, node b) {
    if(id[a.l] != id[b.l]) return id[a.l] < id[b.l];
    if(id[a.r] != id[b.r]) return id[a.r] < id[b.r];
    return a.t < b.t;
}

bool g(int d) {
    return (x <= d && d <= y);
}
void gg(int x, int y) {
    cnt[x] --; cnt[y] ++;
    if(!cnt[x]) -- res; if(cnt[y] == 1) ++ res;
}
int main() {
    scanf("%d%d", &n, &m);
    sq = pow(n, 3.0 / 4);
    for(int i=1;i<=n;i++) id[i] = (int)ceil(i / sq);
    for(int i=1;i<=n;i++) scanf("%d", &a[i]), b[i] = a[i];
    for(int i=1;i<=m;i++) {
        char op[5]; int l, r;
        scanf("%s", op);
        scanf("%d%d", &l, &r);
        if(op[0] == 'Q') {
            ++ k; ask[k].l = l; ask[k].r = r; ask[k].t = i; ask[k].pos = k;
        }
        else {
            cur[i].fi = l; cur[i].se = r;
            fur[i].fi = l; fur[i].se = b[l]; b[l] = r;
        }
    }
    std::sort(ask + 1, ask + k + 1, cmp);
    int ti = 0;
    for(int i=1;i<=k;i++) {
        int t = ask[i].t, l = ask[i].l, r = ask[i].r;
        while(ti < t) {
            if(!cur[ti + 1].fi) {
                ti ++; continue;
            }
            if(g(cur[ti + 1].fi)) gg(a[cur[ti + 1].fi], cur[ti + 1].se);
            a[cur[ti + 1].fi] = cur[ti + 1].se;
            ti ++;
        } 
        while(ti > t) {
            if(!fur[ti].fi) {
                ti --; continue;
            }
            if(g(fur[ti].fi)) gg(a[fur[ti].fi], fur[ti].se);
            a[fur[ti].fi] = fur[ti].se; 
            ti --; 
        }
        while(x < l) {
            cnt[a[x]] --; if(!cnt[a[x]]) -- res;
            x ++;
        }
        while(x > l) {
            cnt[a[x - 1]] ++; if(cnt[a[x - 1]] == 1) ++ res;
            x --;
        } 
        while(y < r) {
            cnt[a[y + 1]] ++; if(cnt[a[y + 1]] == 1) ++ res;
            y ++;
        }
        while(y > r) {
            cnt[a[y]] --; if(!cnt[a[y]]) -- res;
            y --;
        }
        ans[ask[i].pos] = res;
    }
    for(int i=1;i<=k;i++) printf("%d\n", ans[i]);
    return 0;
}

$\;$

树上莫队

$\;$

核心

$\;$
只不过把序列的问题搬到了树上,区间也就变成了一条链。
我们将树分块。
具体实现方法是:维护一个栈,代表目前待选的点的集合S。dfs到某个点u的时候,遍历它的所有子树并统计目前集合S的大小,在遍历的过程中,如果发现集合S的大小已超过规定的块大小,将这些点分为一块。
可以注意到,因为我们是按dfs的顺序进行编号的。所以相邻编号的块在树上也一定是相邻的,这样就会满足莫队的复杂度。
而因为不是在序列上,所以我们不能简单的对左右指针+1或-1
假如上一次询问的链是$(x,y)$,这次是$(u,v)$,那么只需对$(x,u)$和$(y,v)$这两条链上的点的标记进行取反操作。
最终$(u,v)$上的所有点会被标为1。这个可以通过画图理解。
不过在实现的时候,还要注意一些细节:比如说LCA可能要特殊处理,可以参考代码理解。
那么剩余的就和普通、带修莫队一样了。
$\;$

Code

$\;$
例题:P4074 糖果公园
https://www.luogu.com.cn/problem/P4074
$\;$

#include <bits/stdc++.h>

const int N = 100010;

int n, m, k, q, top, val[N], w[N], tim[N], stk[N], idx, dfn[N], dep[N], S, lst[N], id[N], scc, c[N], bc[N];
int upd[N], pre[N], d[N], x, y, vis[N], f[N][20];
long long ans, res[N];
std::vector<int> G[N];
int read() {
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
        x = x * 10 + c - '0', c = getchar();
    return f * x;
}
int dfs(int u, int fa) {
    int re = 0; 
    dfn[u] = ++idx; 
    f[u][0] = lst[u] = fa; 
    dep[u] = dep[fa] + 1;
    for(int i=1;i<=19;i++) f[u][i] = f[f[u][i - 1]][i - 1];
    for(int i=0;i<G[u].size();i++) {
        int v = G[u][i];
        if(v == fa) continue;
        re += dfs(v, u);
        if(re >= S) {
            scc ++;
            while(re) 
                id[stk[top --]] = scc, re --;
        }
    }
    stk[++top] = u;
    return re + 1;
}
struct node {
    int l, r, pos, t;
}ask[N];
bool cmp(node a, node b) {
    if(id[a.l] != id[b.l]) return id[a.l] < id[b.l];
    if(id[a.r] != id[b.r]) {
        if(id[a.l] & 1) return id[a.r] < id[b.r];
        return id[a.r] > id[b.r];
    }
    return a.pos < b.pos;
}
int lca(int x, int y) {
    if(x == y) return x;
    if(dep[x] < dep[y]) std::swap(x, y);
    int ch = dep[x] - dep[y], er = 0;
    while(ch) {
        if(ch & 1) x = f[x][er];
        ch >>= 1; er ++; 
    }
    if(x == y) return x;
    for(int i=19;~i;i--) {
        if(f[x][i] == f[y][i]) continue;
        x = f[x][i]; y = f[y][i];
    }
    return f[x][0];
}
void change(int d, int v) {
    if(vis[d]) {
        ans = ans - 1ll * w[tim[c[d]] --] * val[c[d]];
        ans = ans + 1ll * w[++ tim[v]] * val[v];
        c[d] = v;
    }
    else c[d] = v;
}
void modify(int x) {
    if(vis[x]) {
        vis[x] = 0;
        ans = ans - 1ll * val[c[x]] * w[tim[c[x]] --]; 
    }
    else {
        vis[x] = 1;
        ans = ans + 1ll * val[c[x]] * w[++tim[c[x]]];
    }
}
void make_tag(int u, int v) {
    while(u != v) {
        if(dep[u] > dep[v]) modify(u), u = f[u][0];
        else modify(v), v = f[v][0];
        //printf("%d %d\n", u, v);
    }
} 
int main() {
    n = read(); m = read(); q = read();
    S = pow(n, 0.666); 
    for(int i=1;i<=m;i++) val[i] = read();
    for(int i=1;i<=n;i++) w[i] = read();
    for(int i=1;i<n;i++) {
        int u, v;
        u = read(); v = read();
        G[u].push_back(v); G[v].push_back(u);
    }
    dfs(1, 0);
    scc ++;
    for(int i=1;i<=n;i++) if(!id[i]) id[i] = scc;
    for(int i=1;i<=n;i++) c[i] = read(), bc[i] = c[i];
    for(int i=1;i<=q;i++) { 
        int op, l, r;
        op = read(); l = read(); r = read();
        if(!op) {
            upd[i] = r; d[i] = l; pre[i] = bc[l]; bc[l] = r;
        }
        else {
            if(dfn[l] > dfn[r]) std::swap(l, r);
            ask[++k].l = l; ask[k].r = r; ask[k].t = i; ask[k].pos = k;
        }
    }
    std::sort(ask + 1, ask + k + 1, cmp);
    for(int i=1;i<ask[1].t;i++) {
        if(!upd[i]) continue;
        change(d[i], upd[i]); 
    }
    x = ask[1].l; y = ask[1].r; 
    make_tag(x, y); modify(lca(x, y));
    res[ask[1].pos] = ans;
    modify(lca(x, y));
    for(int i=2;i<=k;i++) {
        int l = ask[i].l, r = ask[i].r;
        // time
        int t = ask[i].t, p = ask[i - 1].t;
        while(p < t) {
            p ++;
            if(upd[p]) change(d[p], upd[p]); 
        }
        while(p > t) {
            if(upd[p]) change(d[p], pre[p]);
            p --;
        }
        make_tag(x, l);
        make_tag(y, r); 
        modify(lca(l, r));
        res[ask[i].pos] = ans;
        modify(lca(l, r));
        x = l; y = r;
    }
    for(int i=1;i<=k;i++) printf("%lld\n", res[i]);
    return 0;
}



ytczy666
2个月前

博客食用更佳 https://www.cnblogs.com/czyty114/p/14449737.html

引入

$\;$
假如现在我们得到了一棵$n$个节点的树,每条边都有长度。
现在我们要求这棵树中两个点之间距离小于$k$的点对个数。
$n\leq 4×10^4$

朴素做法

$\;$
先预处理好距离,再$O(n^2)$枚举点对。

重心

$\;$
我们找到这棵树的重心G,把这棵树分为若干个子树,那么发现满足条件的点对只有3种情况:
1.点对在某个子树中(直接递归求解)
2.两个点所构成的路径经过了重心G,但你会发现这两个点一定不能在同一个子树中。
所以我们处理出当前这棵树中每个点的d值,$d_i$表示点$i$到重心G的距离。
那么只需要用$d_i+d_j\leq k$这样$(i,j)$的数量减去$d_i+d_j\leq k$且满足$i,j$在同一个子树中的数量
而你会发现,后者可以在递归子树中处理。
3.这条路经的一个端点是G,那么实质上和2.是一种情况,再加入一个$d_G=0$即可
$\;$

时间复杂度

$\;$
选重心来分割整棵树的目的:
你会发现,这若干棵子树中不会有子树的大小超过原树的一半(否则就与重心的定义不符)
所以最多只会递归$log(n)$层,每一层也是$n$个点。但在递归中还要将处理好的d排序。
总复杂度$O(n log^2 n)$

Code

$\;$
一定要注意:如果在函数里单独开变量而是开全局变量,一定要注意随时清空,防止上一层的答案对下面有影响。

#include <bits/stdc++.h>

const int N = 40010;
int n, k, head[N], tot, f[N], mn, W, vis[N], d[N], ans, q[N], cnt, sz[N];
struct node {
    int to, nxt, val;
}E[N << 1];
void add(int u, int v, int w) {
    E[++tot].to = v; E[tot].nxt = head[u]; E[tot].val = w; head[u] = tot;
}
void dfs(int total, int u, int fa) {
    f[u] = 0; // 一定注意初始化 
    for(int i=head[u];i;i=E[i].nxt) {
        int v = E[i].to;
        if(v == fa || vis[v]) continue;
        dfs(total, v, u);
        f[u] = std::max(f[u], sz[v]);
    }
    f[u] = std::max(f[u], total - sz[u]);
    if(f[u] < mn) {
        mn = f[u]; W = u;
    }
}
void dfs0(int u, int fa) {
    sz[u] = 1; q[++cnt] = d[u]; // 这是在减去2那一部分的时候的d值 
    for(int i=head[u];i;i=E[i].nxt) {
        int v = E[i].to;
        if(v == fa || vis[v]) continue;
        dfs0(v, u); 
        sz[u] += sz[v];
    }
} 
void getG(int rt) {     
    cnt = 0; // 随时清空 
    dfs0(rt, 0); // 预处理好每个点的子树大小(因为随着划分重心,树的形态会变化) 
    mn = 1e9; // 注意初始化 
    dfs(sz[rt], rt, 0); // DP计算重心 
    vis[W] = 1; // 这个点作为重心,将其打上标记(相当于一个边界条件) 
}
void getd(int u, int fa) {
    q[++cnt] = d[u]; // 在求d值的过程中将其存入q数组中,这里是以这棵树为重心是的d值,与上面的d不一样 
    for(int i=head[u];i;i=E[i].nxt) {
        int v = E[i].to;
        if(vis[v] || v == fa) continue;
        d[v] = d[u] + E[i].val; 
        getd(v, u);
    }
}
void solve(int rt) {
    getG(rt);  // 得到重心 
    if(sz[rt] != n) { 
    // 对于2.情况,要减去在相同子树内(i,j)<=k的个数。这个过程是在递归到这个子树中时进行的 
    //但对于一开始整棵树的情况就没必要减了 
        std::sort(q + 1, q + cnt + 1); 
        // q里存储的是这棵子树内的d值
        // 因为树内点的编号不一定是连续的,所以需要开q这个数组存它 
        int e1 = 1, e2 = cnt;
        for(int e1=1;e1<=cnt;e1++) {
            while(e2 > e1 && q[e1] + q[e2] > k) e2 --; // 双指针枚举,复杂度是线性的 
            if(e2 <= e1) break;
            ans -= (e2 - e1);
        }
    }
    d[W] = 0; // 重心的d当然是0 
    cnt = 0; // 一定注意要随时清空 
    getd(W, 0);
    std::sort(q + 1, q + cnt + 1);
    int e1 = 1, e2 = cnt;
    for(int e1=1;e1<=cnt;e1++) {
        while(e2 > e1 && q[e1] + q[e2] > k) e2 --;
        if(e2 <= e1) break;
        ans += (e2 - e1);
    } 
    for(int i=head[W];i;i=E[i].nxt) {
        int v = E[i].to;
        if(!vis[v]) solve(v); // 如果这个点没被打上标记,一定要向下递归 
    }
}
int main() {
    scanf("%d", &n);
    for(int i=1;i<n;i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w); add(v, u, w);
    }
    scanf("%d", &k);
    solve(1);
    printf("%d", ans);
    return 0;
}


分享 点分治

ytczy666
2个月前

博客食用更佳 https://www.cnblogs.com/czyty114/p/14449737.html

引入

$\;$
假如现在我们得到了一棵$n$个节点的树,每条边都有长度。
现在我们要求这棵树中两个点之间距离小于$k$的点对个数。
$n\leq 4×10^4$

朴素做法

$\;$
先预处理好距离,再$O(n^2)$枚举点对。

重心

$\;$
我们找到这棵树的重心G,把这棵树分为若干个子树,那么发现满足条件的点对只有3种情况:
1.点对在某个子树中(直接递归求解)
2.两个点所构成的路径经过了重心G,但你会发现这两个点一定不能在同一个子树中。
所以我们处理出当前这棵树中每个点的d值,$d_i$表示点$i$到重心G的距离。
那么只需要用$d_i+d_j\leq k$这样$(i,j)$的数量减去$d_i+d_j\leq k$且满足$i,j$在同一个子树中的数量
而你会发现,后者可以在递归子树中处理。
3.这条路经的一个端点是G,那么实质上和2.是一种情况,再加入一个$d_G=0$即可
$\;$

时间复杂度

$\;$
选重心来分割整棵树的目的:
你会发现,这若干棵子树中不会有子树的大小超过原树的一半(否则就与重心的定义不符)
所以最多只会递归$log(n)$层,每一层也是$n$个点。但在递归中还要将处理好的d排序。
总复杂度$O(n log^2 n)$

Code

$\;$
一定要注意:如果在函数里单独开变量而是开全局变量,一定要注意随时清空,防止上一层的答案对下面有影响。

#include <bits/stdc++.h>

const int N = 40010;
int n, k, head[N], tot, f[N], mn, W, vis[N], d[N], ans, q[N], cnt, sz[N];
struct node {
    int to, nxt, val;
}E[N << 1];
void add(int u, int v, int w) {
    E[++tot].to = v; E[tot].nxt = head[u]; E[tot].val = w; head[u] = tot;
}
void dfs(int total, int u, int fa) {
    f[u] = 0; // 一定注意初始化 
    for(int i=head[u];i;i=E[i].nxt) {
        int v = E[i].to;
        if(v == fa || vis[v]) continue;
        dfs(total, v, u);
        f[u] = std::max(f[u], sz[v]);
    }
    f[u] = std::max(f[u], total - sz[u]);
    if(f[u] < mn) {
        mn = f[u]; W = u;
    }
}
void dfs0(int u, int fa) {
    sz[u] = 1; q[++cnt] = d[u]; // 这是在减去2那一部分的时候的d值 
    for(int i=head[u];i;i=E[i].nxt) {
        int v = E[i].to;
        if(v == fa || vis[v]) continue;
        dfs0(v, u); 
        sz[u] += sz[v];
    }
} 
void getG(int rt) {     
    cnt = 0; // 随时清空 
    dfs0(rt, 0); // 预处理好每个点的子树大小(因为随着划分重心,树的形态会变化) 
    mn = 1e9; // 注意初始化 
    dfs(sz[rt], rt, 0); // DP计算重心 
    vis[W] = 1; // 这个点作为重心,将其打上标记(相当于一个边界条件) 
}
void getd(int u, int fa) {
    q[++cnt] = d[u]; // 在求d值的过程中将其存入q数组中,这里是以这棵树为重心是的d值,与上面的d不一样 
    for(int i=head[u];i;i=E[i].nxt) {
        int v = E[i].to;
        if(vis[v] || v == fa) continue;
        d[v] = d[u] + E[i].val; 
        getd(v, u);
    }
}
void solve(int rt) {
    getG(rt);  // 得到重心 
    if(sz[rt] != n) { 
    // 对于2.情况,要减去在相同子树内(i,j)<=k的个数。这个过程是在递归到这个子树中时进行的 
    //但对于一开始整棵树的情况就没必要减了 
        std::sort(q + 1, q + cnt + 1); 
        // q里存储的是这棵子树内的d值
        // 因为树内点的编号不一定是连续的,所以需要开q这个数组存它 
        int e1 = 1, e2 = cnt;
        for(int e1=1;e1<=cnt;e1++) {
            while(e2 > e1 && q[e1] + q[e2] > k) e2 --; // 双指针枚举,复杂度是线性的 
            if(e2 <= e1) break;
            ans -= (e2 - e1);
        }
    }
    d[W] = 0; // 重心的d当然是0 
    cnt = 0; // 一定注意要随时清空 
    getd(W, 0);
    std::sort(q + 1, q + cnt + 1);
    int e1 = 1, e2 = cnt;
    for(int e1=1;e1<=cnt;e1++) {
        while(e2 > e1 && q[e1] + q[e2] > k) e2 --;
        if(e2 <= e1) break;
        ans += (e2 - e1);
    } 
    for(int i=head[W];i;i=E[i].nxt) {
        int v = E[i].to;
        if(!vis[v]) solve(v); // 如果这个点没被打上标记,一定要向下递归 
    }
}
int main() {
    scanf("%d", &n);
    for(int i=1;i<n;i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w); add(v, u, w);
    }
    scanf("%d", &k);
    solve(1);
    printf("%d", ans);
    return 0;
}