CXY07's BLOG - 题解
type: channel
link: http://www.cxy07.blog/index.php/category/Solutions
items: 【题解】[AHOI2022] 山河重整
items: 【题解】[BJOI2018] 双人猜数游戏
items: 【题解】CF1621G Weighted Increasing Subsequences
items: 【题解】CF1540C Converging Array
items: 【题解】CF1336E Chiori and Doll Picking
items: 【题解】[Ynoi2009] rprmq
items: 【题解】[HNOI2019] JOJO
items: 【题解】CF1466H Finding satisfactory solutions
items: 【题解】[Ynoi2008] stcm
items: 【题解】重返现世

【题解】[AHOI2022] 山河重整
type: item
date: 2022-05-16T21:03:00+08:00
description: 题目链接：[AHOI2022] 山河重整题意：计数有多少个元素在 $[1,n]$ 的集合，其 $01$ 背包能表示 $[1,n]$ 中的所有数。$1\le n\le 5\times 10^5$，时间限制 $\text{3s}$。首先考虑从小到大加入数字，那么加入数字中途的每一个时刻，所能表示的都应是值域的一个前缀（因为加的数字越来越大）。若目前能组合出 $[1,p]$，加入的新数是 $x$，那么能表示出的集合就变成了 $[1,p]\cup[x,p+x]$。若 $p+1<x$，由于加入的数字越来越大，所以以后再也组合不出 $p+1$ 了。因此，$x$ 需满足 $x\le p+1$，能拼出的新集合变成了 $[1,p+x]$。于是容易得到一个 $\mathcal{O}(n^2)$ 的算法：设 $\text{dp}(i,p)$ 表示考虑前 $i$ 个数，已经能拼出 $[1,p]$ 的方案数。每次只需要决策是否将 $i$ 加入集合，将 $\text{dp}(i-1,p)$ 转移到 $\text{dp}(i,p+i)$ 即可。我们需要一个更好的方式来描述上述过程。直接计数所有满足条件的序列看起来不那么容易，尝试钦定不满足条件的位置，然后进行容斥。确切来说，即找到一组不合法方案的，最小的 $i$，满足 $[1,i]$ 均可拼出但 $i+1$ 无法拼出，对这样的位置进行容斥。若值域 $[1,i]$ 中每个数均可拼出，且值域在 $[1,i]$ 中所有元素的和 $> i$，那么 $i+1$ 一定可以拼出。又需要能拼出 $i$，所以可知：若 $i$ 是这样一个位置，那么值域在 $[1,i]$ 中的所有元素的和恰好为 $i$。我们设 $f_i$ 表示，只考虑值域在 $[1,i]$ 中的元素，能拼出 $[1,i]$ 中每个数字，且总和恰好为 $i$ 的方案数。其计算可以通过 “所有方案” 减去 “$[1,i]$ 中存在元素无法拼出的方案”。前者是 $i$ 的互异拆分数，而后者可以通过之前的 $f$ 求得。更具体些，枚举第一个无法拼出的数字，在计算 $f_i$ 的时候，一个可以贡献的 $f_j$ 大概形如：$[1,j]$ 均可拼出，跳过 $j+1$（无法拼出），$[j+2,i]$ 中的元素加上 $[1,j]$ 中的元素总和恰好为 $i$（由 $f_j$ 定义可知，$[1,j]$ 中的元素之和恰好为 $j$，因此 $[j+2,i]$ 中的元素和应恰好为 $i-j$）。考虑求解互异拆分数的具体做法。拆分出的数字个数是 $\mathcal{O}(\sqrt{n})$ 级别，于是我们将 “计数 $\mathcal{O}(\sqrt{n})$ 个不同数字和为 $n$ 的方案数” 转变为 “对 $i\in[1,\sqrt{n}]$，考虑有多少个数 $\ge i$”。例如，上图可以看作 $12$ 的一组互异拆分 $\{1,2,4,5\}$（每行看作一个数字），也可以看作 $\ge 1$ 的有 $4$ 个，$\ge 2$ 的有 $3$ 个，$\ge 4$ 的有 $2$，$\ge 5$ 的有 $1$ 个（考虑每列）。由于 $\ge i+1$ 的数字个数一定不多于 $\ge i$ 的数字个数，所以可以从 $\sqrt{n}$ 到 $1$ 倒序枚举 $i$，类似完全背包加入一个体积为 $i$ 的元素（表示有 $i$ 个元素 $\ge$ 某一个值）。而 $f_j$ 向 $f_i$ 的贡献中，也存在 $[j+2,i]$ 中数字的背包状物。暴力做法可以从 $i$ 倒序枚举，在背包中逐步加入元素，在适当的时刻加入 $f_j$ 对 $f_i$ 的贡献。考虑用上述方法类似地优化。$f_j$ 贡献的时候，其他所有元素应 $\ge j+2$。所以，我们可以在确定 $[j+2,i]$ 的集合中有多少个数的时候（设其为 $c$，即上图第一列有多少点），将 $f_j$ 贡献到背包的 $j+(j+2)\times c$ 处作为初值（可以结合代码理解）。最后只剩下一个问题。在计算 $f_i$ 的时候，需要 $f_j$ 已经计算好了。但是上述做法中，我们需要先做一次完整的背包，才可以得到 $f_i$ 的系数。注意到，若 $f_j$ 能贡献到 $f_i$，则 $i\ge j+(j+2)$（$i$ 要在 $j$ 的两倍以上）。因此，只需要先计算 $\dfrac{n}{2}$ 以下部分的 $f_i$，便可以得到所有 $f_i$ 的答案（类似一个倍增的过程）。其复杂度为 $T(n)=\mathcal{O}(n\sqrt{n})+T\Big(\dfrac{n}{2}\Big)=\mathcal{O}(n\sqrt{n})$。//Code By CXY07 - It's My Fiesta. #include<bi…

【题解】[BJOI2018] 双人猜数游戏
type: item
date: 2022-03-23T16:00:00+08:00
description: 题目链接：[BJOI2018] 双人猜数游戏题意：提交答案题。现有 $\text{Alice},\text{Bob}$ 两人，要猜出两个数字 $m,n\ (m\le n)$。一开始 $\text{Alice}$ 知道 $m\times n$，$\text{Bob}$ 知道 $m+n$，两人同时知道一个下界 $s$，即 $s\le m\le n$。从 $\text{Alice}$ 或 $\text{Bob}$，交替回答现在自己是否已经知道了 $m,n$。要求是两人在说了总共 $t$ 次“不知道”之后，同时知道了 $m,n$。给出 $s,t$ 和从谁开始，构造一组合法的 $m,n$，使得 $m+n$ 最小的情况下，$m$ 的值最小。对于 $100\%$ 的数据，满足 $1\le s\le 200,\ 2\le t\le 15$，数据保证有解。挺有意思的题。首先需要意识到，之所以在说了若干次“不知道”之后，知道了 $m,n$ 的取值，是因为之前另一人所说的“不知道”能够减少可能的 $(m,n)$。以 $\text{Alice}$ 开头为例，考虑一些简单的情形。以下不考虑两数之间的大小关系。如果第一轮 $\text{Alice}$ 就知道了呢？说明满足 $a\times b=m\times n$ 且 $a,b\ge s$ 的方案是唯一的。如果第二轮 $\text{Bob}$ 就知道了呢？$\text{Bob}$ 知道的是 $m+n$，在所有 $a+b=m+n$ 且 $a,b\ge s$ 的 $(a,b)$ 中，“合法”的数对方案唯一。这里的合法，意思是这对数在这轮之前还不能被另一个人猜到。例如在第二局中，数对 $(a,b)$ “合法”就指“满足 $c\times d=a\times b$ 且 $c,d\ge s$ 的方案不唯一”。如果我们简单地称 $\{(a,b)|a+b=m+n,\ a,b\ge s\}$ 为“和拆分”，$\{(a,b)|a\times b=m\times n,\ a,b\ge s\}$ 为“积拆分”，那么：第 $1$ 轮 $\text{Alice}$ 没猜到 $\to$ 积拆分不唯一。第 $2$ 轮 $\text{Bob}$ 没猜到 $\to$ 和拆分中“积拆分不唯一”的元素不唯一。第 $3$ 轮 $\text{Alice}$ 没猜到 $\to$ 积拆分中“和拆分中‘积拆分不唯一’的元素不唯一”的元素不唯一。以此类推。虽然这样写下去非常绕，但是我们容易从中观察出类似递归的形式。于是，尝试使用递归函数的形式描述上面的文字。我们称“已经完成 $t$ 轮后，下一个回答”的人称为 $p$，另一人称为 $q$。设 $f(t,a,b)$ 表示说了 $\le t$ 轮“不知道”后，$p$ 是否已经能猜到 $a,b$。注意到一个人只有在另外一个人说完话之后才会得到新信息。先判掉边界情况，$f(0,a,b)$ 就意味着和拆分 / 积拆分中元素唯一。然后，如果当前这个人在 $t-2$ 局后就已经能猜出了，那么这一轮肯定也行。接着，枚举积拆分 / 和拆分，判断有多少个元素在当前这轮“合法”。如果这样的元素唯一，那么 $p$ 就猜到了，否则就是暂时还猜不到。于是，我们就可以使用 $f(t,a,b)$ 来初步判断在 $t$ 次“不知道”后，当前 $p$ 能否猜出 $a,b$ 了。怎么判断 $(a,b)$ 满足“在恰好 $t$ 次‘不知道’后，两个人同时猜到了”呢？首先，$f(t,a,b)$ 应为真：这能保证在第 $t$ 轮的时候 $p$ 能够猜到。其次，$f(t-2,a,b),f(t-1,a,b)$ 均应为假：这保证要恰好第 $t$ 轮之后两人才可能猜到。我们使用 $g(a,b)$ 表示上述三个条件是否同时满足。容易想到还有一个条件：在 $p$ 说完“我知道了”之后，$q$ 应该立即也知道了。但是这不代表 $f(t+1,a,b)$ 为真，因为此时有人说出“我知道了”，与 $f$ 的定义情形不符。于是需要特殊判断，这相当于和拆分 / 积拆分中，“$g(a,b)$ 为真”的元素唯一。套上记忆化，暴力从小到大枚举 $m+n$，并从小到大枚举 $m$ 即可通过。跑的很快，所以这题是提交答案题是不是因为出题人没法证明答案上界啊。//Code By CXY07 - It's My Fiesta. #include<bits/stdc++.h> using namespace std; //#define FILE //#define int long long #define randint(l, r) (rand() % ((r) - (l) + 1) + (l)) #define abs(x) ((x) < 0 ? (-(x)) : (x)) #d…

【题解】CF1621G Weighted Increasing Subsequences
type: item
date: 2022-01-07T21:34:59+08:00
description: 题目链接：CF1621G Weighted Increasing Subsequences题意：给定长度为 $n$ 的序列 $\{a_n\}$，对于其一个长度为 $k$ 的上升子序列 $a_{i_1},a_{i_2}\cdots a_{i_k}$ 定义其权值为满足 $j\in[1,k]$，存在一个 $x\in(i_k,n]$ 使得 $a_x>a_{i_j}$ 的 $j$ 的个数。计算所有上升子序列的权值和。$1\le n\le 2\times 10^5, 1\le a_i\le 10^9$。首先将序列离散化，计算每个上升子序列的权值是困难的，我们考虑每个位置 $a_p$ 的贡献。对于一个 $a_p$，$i_k$ 最远可以到哪里，使得存在一个 $x\in(i_k,n]$ 满足 $a_x>a_i$？容易发现，若设 $r_p$ 表示最靠右的满足 $a_{r_p}>a_p$ 的下标，则 $i_k<r_p$。注意到 $a_{r_p}$ 必然在后缀单调栈上。于是，对于每一个 $p$，我们需要计算 “经过 $p$，且最后一个元素在 $r_p$ 之前” 的上升子序列个数。容斥成 “经过 $p$，且最后一个元素下标 $\in[r_p,n]$” 的上升子序列个数。本人做到这里的时候被卡住了，“经过定点，结尾在一段后缀的上升子序列个数” 看起来不是很可做。继续观察性质，注意到我们设 $r_p$ 是最靠右的满足 $a_{r_p}>a_p$ 的位置，这意味着 $\forall i\in(r_p, n],\ a_i\le a_p$。说明，任意经过 $p$ 的上升子序列，都不可能在 $(r_p, n]$ 结束。于是 “经过 $p$，且最后一个元素下标 $\in[r_p,n]$” 的限制就转变成了 “经过 $p$，且最后一个元素下标 $=r_p$”，相当于钦定了一个定点，钦定了结尾元素。如何计算这样的子序列个数？首先肯定要把子序列拆成 $p$ 之前、之后。前面是好算的，$p$ 之后的部分，就相当于：“第一个元素下标是 $p$，最后一个元素下标是 $r_p$” 的上升子序列个数。接下来我的处理和官方的题解有一些区别：由于 $r_p$ 是最靠右的满足条件的下标，所以任意从 $p$ 开始延申的上升子序列，其结尾下标必然 $\le r_p$。于是，我们只需要维护 “从 $p$ 开始，以最远的可行位置结尾” 的方案数即可，容易使用树状数组维护。时间复杂度 $\mathcal{O}(n\log n)$。//Code By CXY07 - It's My Fiesta. #include<bits/stdc++.h> using namespace std; //#define FILE //#define int long long #define randint(l, r) (rand() % ((r) - (l) + 1) + (l)) #define abs(x) ((x) < 0 ? (-(x)) : (x)) #define popc(x) __builtin_popcount(x) #define inv(x) qpow((x), mod - 2) #define lowbit(x) ((x) & (-(x))) #define ull unsigned long long #define pii pair<int, int> #define LL long long #define mp make_pair #define pb push_back #define scd second #define vec vector #define fst first #define endl '\n' #define y1 _y1 const int MAXN = 2e5 + 10; const int INF = 2e9; const double eps = 1e-6; const double PI = acos(-1); const int mod = 1e9 + 7; //const int mod = 998244353; //const int G = 3; //const int base = 131; int T, n, m; int a[MAXN], FT[MAXN], pre[MAXN], suf[MAXN]; int mx[MAXN], mxv[MAXN]; LL Ans; vec<int> v; template<typename T> inline bool read(T &a) { a = 0; char c = getchar(); int f = 1; while(c < '0' || c > '9') { if(c == '-'…

【题解】CF1540C Converging Array
type: item
date: 2021-11-12T20:37:00+08:00
description: 题目链接：CF1540C Converging Array题意：现在有长度为 $n$ 的数组 $a$ 和长度为 $n - 1$ 的数组 $b$，进行无穷次如下过程直至 $a$ 数组值收敛。选择一个数字 $i$。同时使 $a_i = \min(a_i, \frac{a_i + a_{i + 1} - b_i}{2})$，$a_{i + 1} = \max(a_{i + 1}, \frac{a_i + a_{i + 1} + b_i}{2})$（没有取整）。定义 $F(a, b)$ 为操作完成后 $a_1$ 的值。现在你知道数组 $b$ 和长度为 $n$ 的数组 $c$，保证 $\forall i \in [1, n],\ 0 \le a_i \le c_i$。有 $q$ 组询问，每次问使 $F(a, b) \ge x$ 的数组 $a$ 有多少个。$2\le n\le 100,0\le b_i,c_i\le 100,1\le q\le 10^5,-10^5\le x\le 10^5$。首先，对于上述操作，有几个比较基本的观察：两个操作要么同时成功，要么同时失败。第一个操作成功当且仅当 $2a_i>a_i+a_{i+2}-b_i$，第二个操作成功当且仅当 $2a_{i+1}<a_i+a_{i+1}+b_i$，这两个不等式显然等价。进行任意次操作，$\sum_{i=0}^n a_i$ 保持不变。因为 $\dfrac{a_i+a_{i+1}-b_i}{2}+\dfrac{a_i+a_{i+1}+b_i}{2}=a_i+a_{i+1}$。一次操作成功，当且仅当 $|a_{i+1}-a_i|<b_i$，操作过后 $a_{i+1}-a_i=b_i$。因为上述操作实际上可以描述为先取平均数，然后左右各走 $\dfrac{b_i}{2}$ 步。于是，假设 $\{a_n\}$ “收敛”后变成 $\{f_n\}$，则 $\{f_n\}$ 需要满足以下条件：$\sum_{i=1}^n a_i=\sum_{i=1}^n f_i$。$\forall 1\le i<n, f_{i+1}\ge f_{i}+b_i$。注意到，若对于任意 $1\le i<n$，$f_{i+1}=f_i+b_i$，又有 $\sum_{i=1}^n f_i$ 的限制，于是我们实际上可以解出 $\{f_n\}$。具体来说：$$ f_i=f_1+\sum_{j=1}^{i-1} b_j $$$$ \sum_{i=1}^n a_i=\sum_{i=1}^n f=\sum_{i=1}^n(f_1+\sum_{j=1}^{i-1} b_j) $$$$ =f_1 \times n+\sum_{i=1}^{n-1}(n-i)\times b_i $$于是可以得到：$$ f_1=\dfrac{\sum_{i=1}^n a_i-\sum_{i=1}^{n-1}(n-i)\times b_i}{n} $$但是，我们知道并不一定所有 $f_{i+1}=f_i+b_i$。不过，对于 $f_{i+1}>f_{i}+b_i$ 的情况，我们可以得知：在 $i$ 与 $i+1$ 之间没有进行过操作。这是因为我们一次操作一定会使得 $f_{i+1}=f_i+b_i$，但最后 $f_{i+1}>f_i+b_i$，只能说明一开始 $a_i$ 与 $a_{i+1}$ 的差就已经 $>b_i$ 了。于是，总存在一个前缀 $[1,p]$，满足 $\forall 1\le i<p,f_{i+1}=f_i+b_i$，且 $[p+1,n]$ 与 $[1,p]$ 是互不影响的。因此，如果我们已经得知了 $p$ 的确切值，那么 $f_1$ 的值就得到了确定，他应该是：$$ \dfrac{\text{suma}_p-\text{sumb}_p}{p} $$其中：$$ \text{suma}_p=\sum_{i=1}^p a_i,\ \text{sumb}_p=\sum_{i=1}^{p-1}(p-i)\times b_i $$不过实际上，$p$ 的取值是未知的。那应该怎么确定 $f_1$ 呢？首先，由于一定存在一个合法的 $p$，所以：$$ f_1\in\Big\{\dfrac{\text{suma}_p-\text{sumb}_p}{p}\ |\ p\in[1,n]\Big\} $$同时，假设对于一个前缀 $p$，他不满足 $\forall 1\le i<p,f_{i+1}=f_i+b_i$，那么一定有：$$ f_1<\dfrac{\text{suma}_p-\text{sumb}_p}{p} $$这是因为，前缀 $p$ 不满足一定是因为存在一个位置满足 $f_{i+1}>f_i+b_i$，则 $f_{i+1}$ 的大小超出了我们的预计…

【题解】CF1336E Chiori and Doll Picking
type: item
date: 2021-11-02T16:15:00+08:00
description: 题目链接：CF1336E Chiori and Doll Picking题意：给定长度为 $n$ 的序列 $\{a_n\}$，$\forall i\in [1,n],\ a_i\in[0,2^m)$。对 $c\in[0,m]$，计算有多少子序列的异或和的 $\text{popcount}=c$。$1\le n\le 2\times 10^5,0\le m\le 53$。看了一年 终于看懂了首先，对于子序列的异或和这种操作，让我们联想到线性基。将一个整数看作 $\mathbb{F}_2$ 上的 $m$ 维向量，设 $V=\text{span}(a_1,a_2,\cdots,a_n)$，即序列中元素张出的向量空间，$k=\dim V$，即线性基的大小。我们知道，对于任意 $x\in V$，都有恰好 $2^{n-k}$ 种方式通过序列中的元素异或来得到他。于是我们可以将问题转变为在线性基上计算答案，最后将答案 $\times 2^{n-k}$。对线性基大小进行讨论。当 $k\le 26$ 的时候，我们可以 $\mathcal{O}(2^{k})$ 枚举线性基中每个元素是否被选择。而在 $k>26$ 的时候，我们希望得到一个 $\mathcal{O}(2^{m-k})$ 的算法，将两个算法结合得到一个 $\mathcal{O}(2^{\frac{m}{2}})$ 的算法。设：$$ A_i=[i\in V] $$$$ F^{(c)}_i=[\text{popcount}(i)=c] $$则我们需要的应该是：$$ \text{Ans}_c=\sum_{i=0}^{2^m-1} A_i F^{(c)}_i $$即我既要能被张出，又要满足 $\text{popcount}$ 为定值 $c$。可以写作：$$ \sum_{i=0}^{2^m-1} A_i\sum_{j=0}^{2^m-1} F^{(c)}_j [i=j] $$将其写成异或卷积的形式，$i=j\iff i\oplus j=0$，于是所求即为：$$ (A*F^{(c)})_0 $$其中 $*$ 表示异或卷积。我们令 $\langle i,j\rangle=\text{popcount}(i \text{ and }j)\bmod 2$，即 $i,j$ 按位与的二进制位下 $1$ 的个数奇偶性。由于已经转化为异或卷积的形式，所以不妨考虑 $\text{FWT}(A)$ 与 $\text{FWT}(F^{(c)})$。首先考虑 $\hat F^{(c)} =\text{FWT}(F^{(c)})$，他可以表示为：$$ \hat F^{(c)}_i=\sum_{\text{popcount(j)=c}} (-1)^{\langle i, j\rangle} $$令 $\text{popcount}(i)=a$，枚举 $b=\text{popcount}(i \text{ and }j)$，可以表示为：$$ \hat F^{(c)}_i=\sum_{\text{popcount(j)=c}} (-1)^{\langle i, j\rangle}=\sum_{b=0}^m (-1)^b \binom{m-a}{c-b}\binom{a}{b} $$注意到其值只与 $a,c$ 相关，设其为 $f(a,c)$。接下来考虑 $\hat A=\text{FWT}(A)$，可以表示为：$$ \hat A_i=\sum_{j\in V}(-1)^{\langle i,j\rangle} $$给出如下结论：对于任意 $i\in[0,2^m)$，有 $\hat A_i\in\{0, 2^k\}$。证明：首先，一个事实是：$\langle a,c\rangle\oplus \langle b,c\rangle=\langle a\oplus b, c\rangle$。对于 $\forall x\in V$，在枚举的元素 $j$ 在遍历 $V$ 中所有元素的时候，$j\oplus x$ 也在遍历 $V$ 中所有元素。因此如果 $\exists j\in V$，$\langle i, j\rangle=1$，则 $\langle i,j\oplus x\rangle=0$，于是上述 $\hat A_i$ 中 $\pm 1$ 贡献抵消，和为 $0$。如果 $\forall j\in V, \langle i,j\rangle=0$，则 $\hat A_i = 2^k$。注意到这是一个齐次线性方程组，因此我们只需要找到一组基础解系，这些向量张出的向量空间中每个元素都满足 $\hat A_i=2^k$。设原线性基消元之后为 $M$，则 $M$ 可以表示为：$$ M=\begin{bmatrix} E_k & X \end…

【题解】[Ynoi2009] rprmq
type: item
date: 2021-11-01T11:18:00+08:00
description: 题目链接：[Ynoi2009] rprmq题意：有一个 $n \times n$ 的矩阵 $A$，初始全是 $0$，有 $m$ 次修改操作和 $q$ 次查询操作，先进行所有修改操作，然后进行所有查询操作。一次修改操作会给出 $l_1,l_2,r_1,r_2,x$，代表把所有满足 $l_1 \le i \le r_1$ 且 $l_2 \le j \le r_2$ 的 $A_{i,j}$ 元素加上一个值 $x$。一次查询操作会给出 $l_1,l_2,r_1,r_2$，代表查询所有满足 $l_1 \le i \le r_1$ 且 $l_2 \le j \le r_2$ 的 $A_{i,j}$ 元素的最大值。$1\le n,m\le 5\times 10^4,1\le q \le 5\times 10^5$。或许是一个实现方式有一些小差别的做法。首先考虑离线分治，每次考虑跨过分治中心的查询与修改。将第二维放在线段树上，第一维做扫描线，每次从分治中心 $\text{mid}$ 向左、右进行拓展，如果遇到一个矩阵的开始，或一个矩阵的结束，就在线段树上进行区间修改。由于我们需要的是“矩形 $\max$”，而在分治的时候，第一维变成了时间，所以这个问题在这里就是线段树历史 $\max$。于是对于一个跨过 $\text{mid}$ 的询问，我们只需要在扫描线到了左端点处，或到了右端点处的时候，查询区间历史最大值即可。这一部分中，一个实现的细节是当扫描完 $\text{mid}$ 左侧时，需要将整棵线段树的状态 $\text{roll back}$ 回到还没有扫描左侧时的状态，然后再进行右侧的扫描线。这个可以通过直接对线段树 $\text{DFS}$，将每一个遍历过的节点的权值进行回滚来做到。另一个容易错的点是，如果一个位置上同时有矩形的结束与矩形的开始（即有区间加与区间减操作），那么应该先进行区间减操作，这样才能使历史 $\max$ 保持正确。这样单次查询的复杂度就是 $\mathcal{O}(\log n)$ 的，$\mathcal{O}(q\log n)$ 的总复杂度可以接受。但是修改的复杂度实际上是不太对的。在一般的分治中，其时间复杂度的保证基于每一个操作在进入分治树下一层的时候，都只会进入一边（一个分治树节点）。然而在这里，一个跨越了 $\text{mid}$ 的操作，可以同时向 $[\text{L},\text{mid}]$ 与 $[\text{mid+1},\text{R}]$ 进行递归。也就是说，任意一个修改实际上是在分治的时间维度的一个区间上存在的，而分治的结构本身就类似一棵线段树，所以可以认为一个操作是存在在分治树的一个区间上的。由于分治树是线段树结构，而操作存在在分治树的区间上，这让我们想到“线段树分治”。线段树分治的思想就是将一个存在在某个时间段的修改划分为 $\log$ 个部分，通过在 $\text{DFS}$ 整棵线段树的时候，维护当前线段树节点的祖先的所有修改操作，来保证复杂度。于是，把这个思想套到本题上，就变成了：如果一个操作完全覆盖了当前的分治区间，则把他看作一个类似“初值”的部分。因为在这个区间中这次操作永远存在，所以只需要在进入区间的时候将该操作执行，则分治树的子树中这个操作就一直存在了。从而一个操作被拆分成了 $\mathcal{O}(\log n)$ 次操作，总复杂度是 $\mathcal{O}(m\log^2n+q\log n)$。一个细节：由于进行分治的过程中可能需要进行状态的回滚，而状态的修改次数是 $\mathcal{O}(m\log^2 n)$ 的，直接记录的话空间将与时间同阶。不过实际上，即使修改次数是 $\mathcal{O}(n\log^2 n)$，其修改的元素个数却是 $\mathcal{O}(n\log n)$，可以通过把可回退的部分较为精细地实现来保证空间复杂度。//Code By CXY07 - It's My Fiesta. #include<bits/stdc++.h> using namespace std; //#define FILE //#define int long long #define randint(l, r) (rand() % ((r) - (l) + 1) + (l)) #define abs(x) ((x) < 0 ? (-(x)) : (x)) #define popc(x) __builtin_popcount(x) #define inv(x) qpow((x), mod - 2) #define lowbit(x) ((x) & (-(x))) #define ull unsigned long long #define pii pair<i…

【题解】[HNOI2019] JOJO
type: item
date: 2021-09-18T16:47:00+08:00
description: 题目链接：[HNOI2019] JOJO题意：维护一个字符串 $s$，支持以下两种操作：在 $s$ 末尾插入连续 $x$ 个字符 $c$。将 $s$ 撤回到第 $x$ 次操作之后的状态。在每次操作后，计算 $s$ 的每一个前缀的最长 $\text{border}$ 的长度和。$1\le n\le 10^5$。2019 年 4 月 6 日，HNOI2019 Day 1 赛场上，菜鸡 CXY07 打了这题的 50 分部分分做法，可是下午出成绩的时候发现本题 boom 0。2019 年 7 月，菜鸡 CXY07 看到了神仙们的题解，但是由于太菜，并没有看懂。2019 年 10 月，菜鸡 CXY07 深刻研究了 KMP，可是并没有学出什么所以然。2021 年 9 月 10 日，菜鸡 CXY07 准备回来补坑，结果被此题的可持久化线段树做法劝退。2021 年 9 月 18 日，菜鸡 CXY07 最终还是学习了此题另一种做法，并且在 1h 切掉此题。两年前我在 HNOI2019 的赛场上，折戟沉沙。两年后，我从倒下的地方爬起。我成功了。我不再是以前的那个我了。以上是整活环节，题解在下面计算每一个前缀的最长 $\text{border}$ 的长度和，实际上就是 $\sum\limits_{i=1}^n \text{fail}_i$。这让我们想到 $\text{KMP}$。对于撤回操作，自然可以将操作建成操作树，在上面 $\text{DFS}$ 来计算贡献。每次，我们将操作树上一个节点的答案分为：该节点父亲的答案 $+$ 当前点的贡献。当前点的贡献形如加入一段长度为 $x$ 的字符 $c$ 后，这个后缀的最长 $\text{border}$ 和。如果先不考虑 $\text{KMP}$ 的均摊性质，我们可以把 $(c,x)$ 看作一个新的元素，对这样一个元素的序列进行 $\text{KMP}$。那么加入一段长度为 $x$ 的字符 $c$ 就相当于在该序列末尾加入一个元素 $(c,x)$，我们希望在计算序列末尾元素的 $\text{fail}$ 的过程中，维护答案的增量。若在匹配元素 $(c,x)$ 的时候，前缀中匹配到了一个元素 $(c,x')$，那么至少我们可以匹配 $\min(x,x')$ 个字符 $c$ 了，这一部分的贡献便形如一个等差数列求和。当然，如果在匹配到当前的 $(c,x')$ 之前，有一个更长的前缀，可以匹配 $l$ 个字符 $c$，那么当前的 $(c,x')$ 便只能匹配 $l+1$ ~ $\min(x,x')$ 个 $c$（因为如果 $c$ 的个数 $\le l$，那么就存在一个更长的 $\text{border}$）还有一种特殊情况，若当前元素 $(c,x)$ 没有办法匹配一个长度 $>0$ 的前缀，但是序列的第一个元素 $(c',x')$ 满足 $c'=c,x'\le x$，则当前元素 $(c,x)$ 也是可以匹配序列的第一个元素的。这样，我们就在维护二元组序列的同时，维护了答案的增量。接下来来解决 $\text{KMP}$ 复杂度均摊，导致复杂度无保证的情况。实际上在原数据上，直接均摊也能过设当前正在考察的，长度为 $p$ 的前缀不是当前序列的 $\text{border}$，对于该前缀的形态进行讨论：若该前缀有一个 $>1$ 的周期，则可以直接跳过所有整周期（因为没必要对一模一样的部分检查多遍）。若该前缀没有 $>1$ 的周期，则直接暴力跳 $\text{fail}$ 指针。如果有 $>1$ 的周期，直接跳过串长至少减半；如果没有 $>1$ 的周期，说明 $\text{fail}<\dfrac{\text{len}}{2}$，串长仍然减半。因此，这样处理之后，跳 $\text{fail}$ 的复杂度就不再均摊，而是严格 $\mathcal{O}(\log n)$。于是我们就把该算法优化到 $\mathcal{O}(n\log n)$，可以通过本题。//Code By CXY07 - It's My Fiesta. #include<bits/stdc++.h> using namespace std; //#define FILE #define int long long #define randint(l, r) (rand() % ((r) - (l) + 1) + (l)) #define abs(x) ((x) < 0 ? (-(x)) : (x)) #define popc(x) __builtin_popcount(x) #define inv(x) qpow((x), mod - 2) #define lowbit(x) ((x) & (-(x))) #define ull unsigned lon…

【题解】CF1466H Finding satisfactory solutions
type: item
date: 2021-09-18T10:58:00+08:00
description: 题目链接：CF1466H Finding satisfactory solutions题意：由于洛谷目前的中文题面过于简洁，导致看完中文题面之后本题就已经解决了一半，所以我来简单翻译一下英文题面。有 $n$ 个人，第 $i$ 个人初始的时候手上有物品 $i$。他们之间可以交换物品，每个人恰好拿到一个物品。而每个人有对物品的偏好，第 $i$ 个人的偏好用排列 $\{s_{i,n}\}$ 来表示。第 $i$ 个人相较物品 $y$ 更喜欢物品 $x$，当且仅当在排列 $\{s_{i,n}\}$ 中 $x$ 在 $y$ 之前。对于一个物品交换的排列 $p$，表示第 $i$ 个物品最后到了 $p_i$ 的手上。对于一个非空的，人的子集 $S$，如果子集内部的人，使用子集内所有人初始手上的物品进行交换，可以达到以下结果：不存在一个人 $x\in S$，在子集内交换后得到物品 $y\in S$，且第 $x$ 个人比起 $y$ 更喜欢 $p_x$。至少存在一个人 $x\in S$，在子集内交换后得到物品 $y\in S$，且第 $x$ 个人比起 $p_x$ 更喜欢 $y$。则称这样一个子集 $S$ 是“不稳定”的。一个物品交换的排列 $p$ 是“稳定”的，当且仅当不存在一个“不稳定”的子集。现给出一个物品交换的排列 $p$，求有多少种 $\{\{s_{1,n}\},\{s_{2,n}\}\cdots,\{s_{n,n}\}\}$ 使得 $p$ 是“稳定”的。（可以证明，对于一组 $\{\{s_{1,n}\},\{s_{2,n}\}\cdots,\{s_{n,n}\}\}$，恰好存在一个 $p$ 是“稳定”的）$1\le n\le 40$。“不稳定”的定义可以认为是，如果一个子集内部的人，可以在内部进行交换之后，使得没有人拿到的物品变劣，且至少有一个人拿到的物品变优，则这个子集就不乐意了。首先不妨考虑一下，为什么对于一组 $\{\{s_{1,n}\},\{s_{2,n}\}\cdots,\{s_{n,n}\}\}$，其“稳定”的 $p$ 有且仅有一组。首先，我们不妨先让每一个人选择自己最喜欢的物品（在图上连边），则我们会得到一棵基环内向树森林。考虑有哪些人所得到的物品可能需要变化。如果环上的某一个人 $x$ 所得的物品变化了，则这个环就会变成一个“不稳定”的子集，因为其他人都没有变劣，而 $x$ 得到的物品变优了。因此，环上边是不能删除的。所以不妨直接把环上的点，和连到环上的边删除，递归进行问题。最后我们一定会得到若干环，这就是唯一合法的 $p$。那么从这个角度转化一下题意，可以把题意转化为：给定 n 和排列 $\{p_n\}$。对于 $1 \le i \le n$，有排列 $\{s_{i,n}\}$。考虑 $n$ 个点的有向图，有两类边：如果 $j$ 在排列 $\{s_{i,n}\}$ 中比 $p_i$ 靠前，存在黑边 $i \to j$。白边 $i \to p_i$。这张图是合法的，当且仅当所有环中都不存在黑边。求有多少种 $\{\{s_{1,n}\},\{s_{2,n}\}\cdots,\{s_{n,n}\}\}$ 使得这张图是合法的。这是因为，如果环上存在黑边，则这个环上的点按照这个环来交换物品之后，黑边上的人会变优，白色边上的点不变劣，这就出现了一个“不稳定”的子集。现在考虑从 $p$ 入手。显然 $p$ 由若干环构成，根据上述表述，我们知道最后如果把每个环看作一个点，会连出一张 $\text{DAG}$。对于一张 $\text{DAG}$，他自然对应很多种 $\{\{s_{1,n}\},\{s_{2,n}\}\cdots,\{s_{n,n}\}\}$。具体来说，如果设一个点 $i$ 连出的黑边条数为 $d_i$，则一张 $\text{DAG}$ 对应的排列集合个数应该是：$$ \prod_{i=1}^n d_i! \times (n-d_i-1)! $$这是因为黑边连向的元素在 $\{s_{i,n}\}$ 中一定在 $p_i$ 之前，但他们之间可以任意排列。没有出现的边所代表的元素也可以任意排列。于是，我们不难得到一个状压 $\text{dp}$。设 $\text{dp}_S$ 表示将 $S$ 的生成子图连成一个 $\text{DAG}$ 的权值之和。那么有：$$ \text{dp}_S=\sum_{T\subset S} (-1)^{|S-T|-1}\text{dp}_{T}\times f(T,S-T) $$其中 $f(A,B)$ 表示将集合 $B$ 连向集合 $A$ 所贡献的权值和。实际上就是枚举最后一层有哪些元素，然后前面往最后一层连边。前面的 $(-1)^{|S-T|-1}$ 是容斥系数，这是因为对于每一种方案，会枚举出最…

【题解】[Ynoi2008] stcm
type: item
date: 2021-09-11T15:11:00+08:00
description: 题目链接：[Ynoi2008] stcm题意：给定一棵树，可以维护一个集合，支持以下操作：当前集合中插入一个节点 $x$。撤回上一次插入操作。将当前点集标为第 $i$ 个点的子树补信息。一个点 $x$ 的子树补信息定义为：树的点集除去 $x$ 的子树（包括 $x$）内的点得到的集合。要求在 $4.5\times 10^6$ 次操作以内，标记所有点的子树补。$1\le T\le 3,1\le n\le 10^5$。操作次数是 $\mathcal{O}(n\log n)$ 级别，先无脑重链剖分一下。根据重链剖分相关结论，可知轻子树大小总和是 $\mathcal{O}(n\log n)$ 的。因此，对于一条重链上的所有节点，我们可以直接暴力加入所有轻子树，这样每一棵轻子树只被加入一次。具体来说，对于一条重链的顶端 $x$，假设当前状态已经是 $x$ 的子树补，则每次可以暴力将 $x$ 的轻儿子遍历一遍，加入所有节点，再加入 $x$，得到 $x$ 的重儿子的子树补。则现在的问题变成了，如何求出每一条重链顶端的子树补。对于一条重链的顶端 $x$，假设当前状态已经是 $x$ 的子树补，当我们进行一些操作之后，当前状态转变为 $x$ 这条重链上某一个节点 $y$ 的某一个轻儿子 $p$ 的子树补，则我们就可以递归处理 $p$ 子树内部的答案了。若要让当前 $x$ 的子树补，转变为 $p$ 的子树补，则 $x$ 这条重链上其他节点的所有轻儿子都要被标记，所需要的操作次数是：$$ \sum_{y\in \text{link}(x)}\sum_{k\in \text{lightson}(y),k\ne p}\text{siz}(k) $$的级别。我们希望这个式子的总和尽量小。考虑把所有轻子树 $k$ 看作一个二元组 $(k,\text{siz}(k))$，重链上的点 $y$ 看作 $(y,1)$。建立这样一个二元组的哈夫曼树，可知一棵权值和为 $s$ 的哈夫曼树，带权子树和是 $\mathcal{O}(s\log s)$ 级别的。于是，可以在哈夫曼树上 $\text{DFS}$，每次要往哈夫曼树的左子树进行处理，就暴力加入右子树内的所有节点；要往右子树走，就加入左子树节点。这样的时间复杂度看起来是 $\mathcal{O}(n\log^2 n)$ 的，但是好像可以通过将每次递归子问题所得到的哈夫曼树拼接起来，最后得到一个 $\mathcal{O}(n\log n)$ 的时间复杂度。//Code By CXY07 #include<bits/stdc++.h> using namespace std; //#define FILE //#define int long long #define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout) #define randint(l, r) (rand() % ((r) - (l) + 1) + (l)) #define LINE() cout << "LINE = " << __LINE__ << endl #define debug(x) cout << #x << " = " << x << endl #define abs(x) ((x) < 0 ? (-(x)) : (x)) #define popc(x) __builtin_popcount(x) #define inv(x) qpow((x), mod - 2) #define lowbit(x) ((x) & (-(x))) #define ull unsigned long long #define pii pair<int, int> #define LL long long #define mp make_pair #define pb push_back #define scd second #define vec vector #define fst first #define endl '\n' const int MAXN = 1e5 + 10; const int INF = 2e9; const double eps = 1e-6; const double PI = acos(-1); //const int mod = 1e9 + 7; //const int mod = 998244353; //const int G = 3; //const int base = 131; int T, n, m, cnt, opt_cnt; int fa[MAXN], siz[MAXN], son[M…

【题解】重返现世
type: item
date: 2021-09-10T19:24:00+08:00
description: 题目链接：重返现世题意：有 $n$ 个元素，每次抽取到第 $i$ 个的概率是 $\dfrac{p_i}{m}$，求抽到任意不同 $k$ 个的期望次数。$1\le n\le 1000,1\le m\le 10^4,0\le n-k\le 10,\sum p_i=m$。这题也太神秘了/bx/bx/bx首先考虑 $\text{min-max}$ 容斥，则这个东西是：$$ E(\text{kth-min}(S))=\sum_{T\subseteq S} \binom{|T|-1}{k-1}(-1)^{|T|-k} E(\max(T)) $$回忆一下 $E(\max(T))$ 的求法，这是一个经典的 $\text{min-max}$ 容斥问题，其做法需要把 $\max$ 反演成 $\min$。所以这样仍然是不好做的。但是我们知道，第 $k$ 小 $\iff$ 第 $n-k+1$ 大，所以我们令 $k\leftarrow n-k+1$。这样还有一个好处：当 $k\leftarrow n-k+1$，则 $k\le 11$，用上了题目的条件。于是有：$$ E(\text{kth-max}(S))=\sum_{T\subseteq S} \binom{|T|-1}{k-1}(-1)^{|T|-k} E(\min(T)) $$这时候 $E(\min(T))$ 就是一个经典问题了，这个问题问的是：第一次抽出集合 $T$ 中的元素所需要的期望次数。抽出集合中任意一个元素的概率是 $\dfrac{\sum_{x\in T} p_x}{m}$，所以期望次数就是其倒数 $\dfrac{m}{\sum_{x\in T}p_x}$。因此答案是：$$ E(\text{kth-max}(S))=\sum_{T\subseteq S} \binom{|T|-1}{k-1}(-1)^{|T|-k} \dfrac{m}{\sum_{x\in T}p_x} $$这个 $\sum_{x\in T}p_x$ 在分母上太神秘了，但是我们有 $m\le 10^4$，所以可以枚举这个和！答案变成：$$ =\sum_{s=1}^m \dfrac{m}{s}\sum_{T\subseteq S}\binom{|T|-1}{k-1}(-1)^{|T|-k}\Big[\sum_{x\in T} p_x=s\Big] $$考虑对每一种 $s$，算后面那个系数之和。考虑 $\text{dp}$，设 $\text{dp}_{i,j,x}$ 表示考虑前 $i$ 个元素，$\sum_{x\in T} p_x=j$，$$ \binom{|T|-1}{x-1}(-1)^{|T|-x} $$的和。考虑如何转移，首先如果第 $i$ 个元素不选，则有：$$ \text{dp}_{i,j,x}=\text{dp}_{i-1,j,x} $$如果选择第 $i$ 个元素，则 $j\leftarrow j+p_i$。考虑上面这个系数会怎样变化：$$ \binom{|T|-1}{x-1}(-1)^{|T|-x}=-\binom{|T|-2}{x-1}(-1)^{(|T|-1)-x}+\binom{|T|-2}{x-2}(-1)^{(|T|-1)-(x-1)} $$也就是把杨辉三角拆开，然后把 $-1$ 的系数修正一下。于是有转移：$$ \text{dp}_{i,j,x}=\text{dp}_{i-1,j,x}+\text{dp}_{i-1,j-p_i,x-1}-\text{dp}_{i-1,j-p_i,x} $$直接 $\text{dp}$ 即可做到 $\mathcal{O}(nm\times (n-k))$。空间开不下，记得滚动一下。彩蛋：推式子的时候，大力推了 kth-min 转化为 min 的系数，觉得自己巨大厉害，后来发现这和 kth-max 转变为 min 没有任何区别/tuu//Code By CXY07 #include<bits/stdc++.h> using namespace std; //#define FILE #define int long long #define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout) #define randint(l, r) (rand() % ((r) - (l) + 1) + (l)) #define LINE() cout << "LINE = " << __LINE__ << endl #define debug(x) cout << #x << " = " << x << endl #define abs(x) ((x) < …