LCT

前置知识: 树链剖分（轻重儿子，轻重链，批量维护）, Splay tree(伸展树, 二叉搜索，简单调整，势能评价)

Link/Cut Tree 是一种数据结构，我们用它来解决 动态树问题

维护一棵树，支持如下操作：

• 修改两点间路径权值。
• 查询两点间路径权值和。
• 修改某点子树权值。
• 查询某点子树权值和。

这是一道树剖模版题。

但是再加一个操作：

• 断开并连接一些边，保证仍是一棵树。

要求在线求出上面的答案。

这就成了动态树问题，可以使用 LCT 求解。

https://github.com/PotatoHashing/kactl/blob/LCT/content/graph/LCT.h

splay

1. 性质: 二叉查找树: 左子树小于根节点，右子树大于根节点
2. 均摊O(log n)时间复杂度
3. 伸展树: 每次访问节点后，将该节点旋转到根节点位置

m次splay 大小n的代价为 (n+m) log n

https://www.cs.usfca.edu/~galles/visualization/SplayTree.html

https://codeforces.com/contest/2101

D Mani and Segments

给定1~n排列，问有多少子串满足

LIS+LDS=len+1

3s

我的思路

排列保证了两两不同

lis: dp[i] = idx_lower_bound(a[i])-1

显然 lis 和 lds如果两两不同，那么它们的共有元素最多有一个

有一个共有元素时: lis-1 + lds-1 + 1 <= size(所有元素) = len

             (len+1) - 1 <= size(所有元素) = len

没有有元素时: lis + lds <= size(所有元素) = len

             (len+1) <= size(所有元素) = len

说明了 恰好有一个共有元素，且两个序列占满整个数组

钦定这个共有元素

它向左延伸，要么链接更小要么链接更大, 必须要满足匹配，向右同理

1
2
3
4
5
6
7
8
9
10

fix i
   min = a[i]
   max = a[i]
   for j = i+1 ... n:
       if a[j] > max:
           max=a[j]
       elif a[j] < min:
           min = a[j]
       else:
           break

当出现纯单调序列时，这个共有元素不是唯一的

   1  3 4 5 6 2, 这样共有也不是唯一的， 上面方案没有完成去重的问题

   1 4 3 2 5, 这样 共有的一定不是最大或者最小，

校验方案:

   dp[i][0] = i作为下降时, 上升侧的最小值

   dp[i][1] = i作为上升时, 下降侧的最大值

   dp[i][0] = min(dp[i-1][0] if a[i] < a[i-1], a[i-1] if a[i] < dp[i][1],  INF)

   dp[i][1] = max(dp[i-1][1] if a[i] > a[i-1], a[i-1] if a[i] > dp[i][0], -INF)

这个dp会受到 前面内容的影响, 感觉局部性还不如钦定共有

反面: 什么是不合法的

 a<b,c<d
   d   b
 c   a

a,b无法同时连bc，所以一个连b一个连c，显然不行, 其中a,d相邻

好像也不好搞

另一个角度 如果 a[l..r] 合法

那么 a[l..mid], a[mid…r] 也合法，因为从共有元素角度看，如果包含，那么就有包含的方案，如果不包含发生了分裂，也就是 切割的mid处 可以作为共有点

所以 合法的l..r 的任何切割 总有一半是切割点是共有点

还是单独来，就钦定共有点，但是保证共有点是可选区间最左点

https://codeforces.com/contest/2097

D Maximum Polygon

01字符串s, s=[left s][right s] 二分字符串长度

• f(s): left s xor= right s
• f(s): right s xor= left s
• f(left s)
• f(right s)

每次操作4选1

给定s, t 问能否使得 s经过若干次操作后变为t, 只需要yes/no

len <= 1e6

2s

基础

• 前置内容
  • 容斥原理
  • 全序

定理: 对于满足 全序 关系并且其中元素满足可加减性的序列 $\lbrace x_i \rbrace$，设其长度为 n，并设$S=\lbrace 1,2,3,\cdots,n \rbrace$，则有：

• $\max_{i\in S}{x_i}=\sum_{T\subseteq S}{(-1)^{|T|-1}\min_{j\in T}{x_j}}$
• $\min_{i\in S}{x_i}=\sum_{T\subseteq S}{(-1)^{|T|-1}\max_{j\in T}{x_j}}$

证明

• 我们需要集合满足
  • 全序: 任意两个基础元素可比较大小
  • 需要零元素
  • 然后每个元素有逆元，这里(-1)乘法表示取逆元
  • 不需要可加，这里的加号只是把不同的连在一起
• 例子 {🍟,🍔,🌭}
  • 全序 🍟 < 🍔 < 🌭
  • 零元 0+(🍟)=🍟
  • 逆元 (🍟)+(-🍟)=0

$🌭 =\max (\lbrace🍟,🍔,🌭 \rbrace)$

$= \sum_{T\subset S} (-1)^{|T|-1} \min(T)$

$= (-1)^{1-1}\min(\lbrace🍟 \rbrace)+(-1)^{1-1}\min(\lbrace 🍔 \rbrace)+(-1)^{1-1}\min(\lbrace 🌭 \rbrace) + (-1)^{2-1}\min(\lbrace 🍟,🍔 \rbrace)+(-1)^{2-1}\min(\lbrace 🍔, 🌭 \rbrace)+(-1)^{2-1}\min(\lbrace 🌭,🍟 \rbrace)+(-1)^{3-1}\min(\lbrace 🍟,🍔,🌭 \rbrace)$

$=🍟+🍔+🌭+(-🍟)+(-🍔)+(-🍟)+🍟$

$=🌭$

简单的逻辑证明，含有最大元和未含有最小元的产生1-1 对应的关系，其中(空集)和(只含有最大元)的1-1对应

• 那么 这个1-1对应导致了一个他们的min相同，而(-1)幂次一个奇一个偶，所以都抵消了
• 所以只剩下 只含有最大元的

用例

首先这个玩意很直接，几乎不会直接使用

然而 在概率论中计算期望会用到，

$E(\max_{i\in S}x_i)=\sum_{T\subset S}(-1)^{|T|-1} E(\min_{j\in T} x_j)$

$E(\min_{i\in S}x_i)=\sum_{T\subset S}(-1)^{|T|-1} E(\max_{j\in T} x_j)$

不同的是，这里$x_i$更多是其中一个自由变量，有时写作$X_i$

• 证明: 其实一句话，E是 线性函数

进一步的 k-th min/max

$\text{k-th} \max_{i\in S} x_i =\sum_{T\subset S,|T|\ge k} (-1)^{|T|-k} \binom{|T|-1}{k-1}\min_{j\in T} x_j$

• 证明: 其实类似的, 记结果为😺, 我们固定$\min$ 来看抵消
  • $\min =$😺 时，那么只能选最大k个, 那么就是$(-1)^{k-k}\binom{k-1}{k-1} 😺=😺$
  • $\min < 😺$ 时 希望证明 $\sum_{t=k}^{n+1} \binom{n}{t-1} (-1)^{t-k}\binom{t-1}{k-1} =0, n \ge t-1 \ge k-1 \ge 0$
    • n表示 比😺 大的个数
    • 在其中选了t-1个（加上😺就是t个）
    • 这种情况下的贡献 就是后一半
    • 为了简洁，用$t_{new}=t-1,k_{new}=k-1$替换
    • 希望证明 $\sum_{t=k}^n \binom{n}{t} (-1)^{t-k}\binom{t}{k} =0,n \ge t \ge k \ge 0, n > k$
    • $=\sum_t (-1)^{t-k}\frac{n!}{(t)!(n-t)!}\frac{(t)!}{(k)!(t-k)!}$
    • $=\sum_t (-1)^{t-k}\frac{n!}{(k)!(n-k)!}\frac{(n-k)!}{(n-t)!(t-k)!}$
    • $=\sum_t (-1)^{t-k} \binom{n}{k} \binom{n-k}{t-k}$
    • $=\binom{n}{k} \sum_t (-1)^{t-k} \binom{n-k}{t-k}$
    • $=\binom{n}{k} \sum_{s=t-k=0}^{n-k} (-1)^{s} \binom{n-k}{s}$
    • $=\binom{n}{k} (1-1)^{n-k}$
    • $=0$

类似的，根据E的线性的性质，有期望的形式

例题

2022-03 2835分 abc242H

• 区间$[1,n]$,$n\le 400$
• m个子区间$[l_i,r_i]$,$m \le 400$
• 每次 1/m 概率选择一个区间 涂黑
• 问全部区间都涂黑的 期望时间
• $t_i=$第i个首次被涂黑的时间
• $E(\min T)=$ 集合T中,任何一个首次被涂黑的时间
• $E(\max T)=$ 集合T中,全部被涂黑的期望时间
• 配合$dp[i][j]=$前i个,第i个被选中,j个覆盖了已选集合的 加权和 可做

2022-06 3500分 cf(1687/R796)E

2023-12 2668分 abc331G

• 盒子里有 写着i的卡片有$C_i$张, $1\le i \le n \le 2e5$
• 每次 抽出一张 记录数字, 放回盒子
• 问 期望次数 1~n全至少出现一次
• $t_i=$数字i首次抽到的时间
• $E(\min T)=$ 集合T中,任何一个首次抽到
• $E(\max T)=$ 集合T中,全部被抽过一次的期望时间
• $\displaystyle \mathrm{ans}=\sum_{T\subset S} (-1)^{|T|+1} \frac{N}{\sum_{i\in T}C_i}$
  • 同样 分类讨论$\min$也就是右侧，然后去想办法算左侧-1幂次的加权和
  • 而左侧 把T展开，就是 生成函数系数
  • $\displaystyle -(1-x^{sz_1})(1-x^{sz_2})\cdots(1-x^{sz_m})$的系数，就是要求的内容, 一点poly技巧即可

ref

oiwiki 容斥原理 min_max

algo/反演 里面有提到 min_max 容斥