2024.7.11

T1

题面

\(1\le n\le 10^6\)

题解

排序后贪心选择后缀

T2

题面

给定序列 \(a_{1\sim n},b_{1\sim n}\)

对 \(b\) 区间加，维护 \(\sum_{l=1}^n\sum_{r=l}^n(\sum_{i=l}^ra_i)\times (\sum_{i=l}^rb_i)\mod (10^9+7)\)

题解

可以看出原式一定可以化为 \(\sum_{i=1}^n\sum_{j=1}^na_ib_jp_{i,j}\) 的形式，根据含义可知，\(p_{i,j}\) 为包含区间 \([\min(i,j),\max(i,j)]\) 的区间数。

最后可以推出一个线段树维护的式子，由于我们只关注全局信息，所以没必要建立线段树，而是用一个值代表答案就行了。

因为是对 \(b\) 区间加，所以可以考虑将 \(b\) 从式子中提出来，即形为 \(\sum_{i=1}^nb_iq_i\)，每次区间加 \(k\) 相当于给答案加上 \(k\sum_{i=l}^rq_i\) ，推导可得：\(q_i=\sum_{j=1}^ij(n-i+1)a_j+\sum_{j=i+1}^ni(n-j+1)a_j\)。将两端分开维护，令 \(x_i=\sum_{j=1}^ij(n-i+1)a_j,y_i=\sum_{j=i+1}^ni(n-j+1)a_j\)，可以找到递推式 \(x_{i+1}=x_i+(n-i)ia_i-\sum_{j=1}^{i-1}ja_j,y_{i+1}=y_i-i(n-i+1)a_i+\sum_{j=i+1}^n(n-j+1)a_j\)

维护相应的前后缀和，可以做到 \(\mathcal O(n)\)，总复杂度 \(\mathcal O(n+m)\)

方法

• 全局信息，直接维护

• 考虑形式，待定系数

• 相邻关系，递推求解

T3

给定一颗 \(n\) 个节点的树，与一个序列 \(a_{1\sim m}\) ，令 \(d(x,y)\) 表示 \(x,y\) 节点的树上距离，支持两种操作。

• 将与节点 \(x\) 相连的所有边的权值加上 \(k\)。

• 将 \(a\) 随机打乱，求 \(\sum_{i=1}^{n-1}d(a_i,a_{i+1})\) 的期望，对 \(998244353\) 取模。

\(m\le n\le 5\times 10^5,q\le 5\times 10^5,a_i\in [1,n]\)

题解

因为两个点出现在一起的概率相同，所以该题等价于求解 \(\sum_{i,j}d(a_i,a_j)\) 的平均值，即 \(\frac{\sum_{i,j}d(a_i,a_j)}{m!}\)。

因为链是由边构成的，所以关注于每条边的贡献。如果一条边两侧分别有 \(L,R\) 个关键点（\(a\) 中的点），则可知在 \(2\times L\times R\times (m-1)!\) 个方案中都会出现这条边，所以原式等于 \(\sum_{e\in \mathbb E}\frac{2L_eR_ew_e}m\)，直接一次树形 DP 得到 \(L,R\) 可解。

考虑如何维护，因为本题只关心全局的答案，所以只需要考虑答案的变化，修改操作本质是对答案加上 \(k\sum_{e\in \mathbb {E_x}}\frac{2L_eR_e}m\) ,然而 \(L,R\) 是不会变化的，所以只需要对每个点存 \(\sum_{e\in \mathbb {E_x}}L_eR_e\)即可。

方法

• 期望：转化为概率，期望DP（高斯消元），求平均值。

  转化为概率：利用线性转化期望式子，找到 \(0/1\) 变量。

  期望DP：状态之间可以互相到达

  求平均值：每种情况出现概率相同。

• 考虑操作对答案造成的影响

  当关心全局信息的时候，不用将修改操作具体到某个位置的变化，只需要考虑对全局答案的贡献即可。

T4

给定序列 \(a_{1\sim n}\)，有 \(m\) 次操作，格式如下：
1 x y k \(\forall i\in\{i|i\bmod x\le y\},a_i\leftarrow a_i+k\)
2 l r 求 \(\sum_{i=l}^ra_i\)。

题解

可以发现，当 \(x\) 较小时，块较多，块长小，当 \(x\) 较大时，快较少，块长大，于是可以考虑根号分治。并且将答案转为 \(\sum_{i=1}^ra_i-\sum_{i=1}^{l-1}a_i=ans(r)-ans(l)\)。

\(x\le \sqrt n\)

对于每种 \(x\) 维护块内前缀和，由于所有块是等价的，所以事实上只需要维护一个块的信息，对于答案来说，分为完全在其前方与端点身处其中的，前者就是全局信息，后者就是前缀和。修改复杂度 \(\mathcal O n\sqrt n\)，查询复杂度 \(\mathcal O n\sqrt n\)。

\(x>\sqrt n\)

采用操作分治。因为虽然一次操作可以被转化为 \(\mathcal O\sqrt n\) 个差分，但从差分转为前缀和仍需要 \(\mathcal On\) 的复杂度，所以采用根号分治，在操作序列里面存储最多 \(\sqrt n\) 个操作，超过上限时，序列中可以转化为 \(\mathcal O n\) 个差分， \(\mathcal O n\) 处理于序列。对于未处理至序列的操作，遍历并计算对答案的影响。修改复杂度 \(\mathcal O n\sqrt n\)，查询复杂度 \(\mathcal O n\sqrt n\)。

总复杂度 \(\mathcal On\sqrt n\)。

方法

• 根号分治，对于不同的情况选择不同的方法。

• 操作分治，存储操作不使其作用于结构中，达到上限时一起作用，利用均摊平衡复杂度。

• 等价结构，当几个结构对答案等价时，只需要维护其中一个即可。