Day1 contest of TYY

T1 小N的独立集

给一棵树, 每个点权 $a_i$ 在[0, m]间, 每次独立的钦定一个点 $a_x=y$ , 求此时有多少方案满足对所有 $v\in [1, m]$ , 满足 $a_i\le v$ 的点构成一个连通块.

考虑如果不钦定怎么做, 设f_{u, i, 0/1}表示 $u$ 的值为 $i$ , 且子树内是否有比 $i$ 大的时考虑 $u$ 子树的方案数, 对于1的情况容易转移

$$
f_{u, i, 1}=\prod_v \sum_j f_{v, j, 1} s. t. j\le i
$$

对于0的情况, 可以枚举哪一个儿子是比它大的:

$$
f_{u, i, 0}=\sum_k (\prod_v \sum_{j\ne k} f_{v, j, 0} s. t. j\le i) \times f_{k, j, 1} s. t. j\ge i
$$

用前缀和和后缀和处理空出k后其他儿子的信息再和k合并不然复杂度爆炸.

那么现在要支持单点修改, 于是ddp和整体dp拍上去, 然后你发现这玩意ddp用矩阵表示简直发疯, 整体dp赛场上也没写出来(这就是”命运”)

而这个可以使用换根dp: 处理它子树内的答案和子树外的答案, 然后修改时以修改的点为根合并.

T2 整数序列

首先有一个 $n^2$ dp, $f_{i, j}$ 表示和为 $i$ , 最后一个数为 $j$ , 如果记录了选的数个数, 那么你降智了.

这个是慢的, 然而发现比较浪费在于当 $j$ 很大时几个数直接结束了, 这种乘积一定的让人想到根号分治, 当 $a_1<B$ 时使用这种方案.

于是有另一种方式, 当 $a_1>B$ 时, 记 $f_{i, j, k}$ 表示长度为 $i$ , 最后一个数减去第一个数为 $j$ , 所有数减去第一个数的和为 $k$ , 这样做当值很大时 $i$ 和 $k$ 都很小, 复杂度是 ${\frac {n} {B}}^4$ , 调阈值可以有奇怪复杂度 $O(n^{\frac {8} {5}})$

优化后面这种方式, 常常可以考虑在前面加数, 那么因为第一个数可以始终当成0, 相当于给后面的整体抬升, 可以记 $f_{i, j}$ 表示选了 $i$ 个数, 所有数减去 $a_1$ 的和为 $j$ , 那么最后枚举 $a_1$ 即可.

T3 有处存储

一个结论

$$
\mu^2(x)=\sum_{d^2 \vert x}\mu(d)
$$

我的证明是

$$
\begin{aligned}
x&=\prod_i p_i^{a_i} \
令x’&=\prod p_i^{\lfloor \frac{a_i}{2} \rfloor}\
则\mu^2(x) &=[x’=1]\
&=\sum_{d \vert x’}\mu({d_i})\
&=\sum_{d^2 \vert x}\mu(d)
\end{aligned}
$$

TYY杂题选讲-%%tyy

UOJ67 新年的毒瘤

给一个简单无向图, 求删去哪个节点后变成一颗树

如果删完了图联通且边数为 $n-1$ 就行, 然后tarjan判割点

另外要判孤立点

UOJ575 光伏元件

给出一个 n×n 的 01 矩阵 A, 其中 A_i, j=1 表示开始时位置 (i, j) 有光伏元件, 而 0 表示没有元件.
你需要给出一组新的光伏元件的排布方案, 光伏元件的分布有下列要求:
设第 i 行的元件个数为 c_0, i, 第 i 列的元件个数为 c_1, i.
对于每个 i, 给出 dl_i, dr_i, k_i , 要求 \vert c_0, i−c_1, i \vert ≤k 且 c_0, i, c_1, i∈[dl_i, dr_i]. 即: 要求第 i 行和第 i 列的元件个数在 [dl_i, dr_i] 之间, 且相差不超过 k_i.
给出 n×n 的矩阵 C, 以 C_i, j 表示改变位置 (i, j) 上元件有/无状态的代价; 特别地, 若 C_i, j=−1, 则表示 (i, j) 位置的状态不可改变.
你需要找一组方案, 在满足要求的前提下, 使得总费用最小. 保证存在合法方案.
1≤n≤100, 0≤dl_i≤dr_i≤n, 0≤k_i≤n, C_i, j≥−1, ∑▒ \vert C_i, j \vert ≤2×10^9.

这种棋盘上要求行的个数和列的个数的长的很像网络流的套路

考虑建一排行点一行列点 $col_i$ 和 $row_i$ , 则 $(i, j)$ 有点则 $row_i\to col_j$ , 费用相应设置

然后要处理两列间的这个问题, 简单的想法是通过 $row_i\to col_i$ 有上下界的网络流, 接下来考虑给行和列补流来解决绝对值相差不超过 $k$ :

做法是建一个新点 w_i, 加入 $(col_i, w_i, [0, inf])$ , $(col_i, T, [0, k_i])$ , $(S, w_i, [0, k_i])$ 来允许 $k_i$ 的差距, 之后再对 $w_i$ 和 $row_i$ 连边即可.

可以使用强制流满的方法处理负环, 像上下界一样补流, ~~直接网络单纯形~~

UOJ577 打击复读

每个位置有一个 $wl$ 和 $wr$ , $vl(s[l, r])$ 为 $s[l, r]$ 出现位置的所有左端点的 $wl$ 之和, $vr(s[l, r])$ 为右端点之和. 每次修改一个位置的 $wl$ , 求

$$
\sum l\sum r vl(s[l, r])*vr(s[l, r])
$$

设 $s[l, r]$ 出现次数为 $c([i, j])$

如果直接维护 $s[l, r]$ 的值会比较麻烦, 还要考虑它的出现次数, 所以维护
$f_i=\sum_{i\le j\le n} c(s[i, j])\times vr(s[i, j])$
那么答案就是 $\sum f_i wl_i$

建出 $s$ 的后缀树(这个是反串后缀自动机parent tree), 和后缀自动机

考虑一个厉害结论, 后缀树上一个节点对应的是后缀自动机上的一条链, 且这一条链之外除了最后一个点外都只有一条出边, 由于后缀自动机上每个节点对应endpos相同, 所以每个节点对应的出现次数和 $wr$ 均相等, 对后缀树上每个叶子(叶子即一条后缀)到根路径累加路径上每个节点对应的

$$
\sum c(s[l, r])\times wr_r
$$

即为 $f$ , 这个东西要在后缀自动机的链上求, 刚才说明这条链中间都只有一条出边, 所以一条链的信息是容易维护的, 只要在后缀自动机上遍历一遍就能得到这些信息.

对于修改发现可以简单O(1).

UOJ152 汉诺塔

汉诺塔, 但不要求过程中大的在小的上面, 有1e4个圆盘, 1e6次操作把它排序

可以用操作把一个序列分成两个子序列或把两个子序列合并成一个.

于是按大于或小于mid分成两个子序列, 对每个子序列, 发现可以忽略另一个子序列, 因为操作都是在栈顶

于是递归下去归并即可

UOJ153 世界线

交互题
要求你进行两次实验猜出一个长为 $n$ 的排列 $a$ , 值域1-n, 你可以调用的函数包括

new_round() 新的一次实验, 只能调用两次, 会生成一个 $2n$ 点的无向图, 其中 $i\to n+a_i$ , 此时实验为第一阶段

next_step() 实验进入第二阶段

add_edge(u, v) 在第一阶段调用, 连接 $u, v$

query(u, v) 在第二阶段调用, 询问 $u+n, v+n$ 的连通性

我们可以在第一阶段把点连成若干连通块, 第二阶段来问每个点在哪个连通块, 我们无法通过add_edge的操作知道另一边的连通块是什么样的, 会形成什么样的结构, 题目相当于连通块和点是无标号的为点找到对应.

那么我们要想一种方式区分这些连通块和点, 发现可以使用连通块的大小, 即我们用大小分别为1, 2, 3. . . k的连通块来区分, 发现 $k$ 是 $O(\sqrt n)$ 的

把一个点记为 $(a, b)$ 表示它在左边连通块是a, 右边连通块是b, 把它画到一个平面上, 把它画成一个阶梯状, 第一次实验将行连成连通块, 第二次将列连成连通块, 然后构造一种方式使得我们可以通过连通块的大小来区分每一个元素.

设 $n=\frac {k\times (k+1)}{2}+c$

若 $c=0$ , 直接分成y=x下方三角形样子的阶梯状
若 $0<c\le k$ , 在上面基础上放上(k+1, k+1), 再把多出来的从上往下堆在最右边, 惊喜的发现由于可以区分出 $(k+1, k+1)$ (所在行大小为1), 那么仍然可以解决

再考虑次数限制, 连边是 $O(n)$ 的毫无问题, 而询问时我们从每个点询问前面的连通块看它属于哪个是 $O(n\sqrt n)$ 的. 卡常优化是从大的连通块开始尝试, 为了防hack再把加点顺序随机.

UOJ218 火车管理

有n个栈形成序列a, m次操作, 每次

给定 $l$ , $r$ 询问 $a_{l. . r}$ 的栈顶和

给定 $i$ , a_i弹栈

给定 $l$ , $r$ , $x$ , 把 $a_{l. . r}$ 每个push一个 $x$

如果不带弹栈就是显然的区间推平区间和, 线段树

那么现在带上修改, 考虑我们需要得到弹出后的栈顶进行修改, 此时有两种解决方案.

Sol1

开线段树套堆, 堆按时间为关键字, 对于一个操作按标记永久化的思想拆成线段树节点push进对应的堆中, 那么弹出时查到一条链上最新的就是栈顶, 把这个修改直接撤销了, 再拆成不包含push点的两个修改再修改回去, 发现每个修改的影响都是区间推平, 所以开另一个线段树维护区间推平区间和. 要用一些配对堆之类的牛逼堆.

Sol2

开可持久化线段树, 修改直接区间推平, pop可以在历史版本上查到pop完后应该是谁, 进行单点修改, 同时仍然要开另一棵树维护区间覆盖区间和.

复杂度都是2log

SDOI D1T3 子串统计

差不多得了 to do

UOJ727 团队竞技

一堆人选3个人结对编程(? ), 每个人有3个指标, 要求选出的三个人中每个人都有一个指标严格大于另外两个人, 最大化选出来的三个人(每个指标的最大值)的和

诈骗, 如果一个人在多于一个的指标上是最大值, 他就无法被选直接扔了.

剩下的选三个分别最大的

UOJ177 新年的腮雷

有n个雷排成一个序列, $i$ 的大小为 $a_i$ , 合并参数序列b, 每次可以把m个合并, 设合并的雷的大小序列为 $x$ , 合并成一个代价为 $\max {x_i+b_i}$ 的雷, 最小化合成一个的代价, 保证能成一个.

反向考虑, 二分最后的答案, 然后看能不能把一个大小为 $v$ 的最后拆成 $n$ 个, 使得每个大小都不小于对应 $a_i$

那么把a和b分别排序, 如果拆掉当前最大的大小为 $x$ 的雷后, 发现如果能拆一定会拆, 而如果这个最大的雷能拆, 发现拆了它一定比拆更小的优秀.

UOJ730 蚂蚁和方糖

数轴上有蚂蚁和方糖, 给定常数 $L$ , 每次有两个操作:

为位置 $i$ 增加若干蚂蚁

为位置 $i$ 增加若干方糖

并在每次操作后输出, 每个蚂蚁能吃它左右 $L$ 的位置的方糖, 可以多个蚂蚁吃一个方糖, 那么至少被一个蚂蚁吃的方糖有多少个.

hall定理表明我们只要求任选一个蚂蚁集合能吃到方糖减去它们数量的最小值即可.

如果一个方糖贡献一堆蚂蚁那么蚂蚁的重叠区间部分部分较为困难, 所以改为一个方糖贡献一个蚂蚁的区间, 蚂蚁的区间双向拓展 $L$ 是其方糖区间.

那么如果两个蚂蚁区间的方糖区间重叠了, 我们把它合并成一个是一定不劣的. 由于要求的是最优解所以可以假设它们不交.

接下来处理一个方糖贡献一个区间的问题, 为了让一个方糖只算一次, 在相邻两个位置增加虚点, 对每个方糖给它能贡献到的区间间隔加1和-1, 发现此时若蚂蚁的区间于方糖贡献到的区间的交集大小超过1, 仍然只会在容斥后算一次, 类似圆方树的容斥. 注意要钦定区间端点不在虚点上.

使用线段树维护, 每个节点记录左右端点和中间虚点的信息, 发现答案可以合并

UOJ732 鱼 2

鱼排成一个序列, 大小序列为 $A$ , 一个鱼可以吃掉相邻的大小不大于自己的鱼然后大小变为两者之和, 每次给出一个区间, 吃到最后只剩一个的鱼, 求可能成为幸存者的鱼的个数. 询问独立.

如果一个区间的和小于它左右端点的值, 那么其中的鱼都不能成为幸存者, 定义这样的区间为坏区间, 发现被坏区间包含是死掉的充要条件.

此外两个重要性质

坏区间不会相交, 只会包含和不交, 因为如果相交的话, 考虑长成这个样子:
1
2
3
4
-------------------------
\vert --------- \vert
\vert --------- \vert
a b c d
发现 $A_{b-1}>\sum A_{b. . d}, A_{c+1}>\sum A_{a. . c}$ , 显然直接矛盾
坏区间个数为 $O(n \log n)$ , 考虑对于一个点, 坏区间每次拓展至少翻一倍, 因为包含了原来两边的墙, 所以总个数是 $n \log n$ 的.

于是可以考虑求出包含每个点的坏区间, 考虑对每个点向左向右分别得到log个满足点权大于到这个点的区间和的端点, 坏区间的点一定在这些中产生, 由于求区间和是1log的, 我们要O(点数)的求出端点, 发现每个左边端点对应的右边端点必然是左边端点值的前驱后继之一, 可以主席树去维护.

然后询问时因为是单独拿出来一段, 所以要求出左右端点在区间内的坏区间, 直接进去倍增即可.

最后要维护未被覆盖的数量, 可以通过线段树维护区间加区间最小值个数, 因为可能会有被询问的区间整体包含的情况所以不是1的个数.

Day5 contest of LXL

T1

给一棵树, 时间 $t=0$ 时只有叶子有权值, 以后的每个时间, 记 $i$ 在时刻 $t$ 权值 $f_{i, t}$ 为 $f_{i, t}=\max_{j\in Son_i}{f_{j, t-1}}$ , 求一条链上的和, 最小值, 最大值.

发现直接维护每个时刻的信息过于困难, 很没前途, 先考虑链上的情况, 对于一个连续的值相等的段一起考虑, 全都插进平衡树, 那么若它上下两段的值都大于它它会缩小1, 都小于它它会扩大1, 否则向上移动一格, 它的移动状况不依赖于当前的时间, 那么可以通过一个全局标记表示所有区间实际经过了多长时间进行询问, 每次如果一个区间没了就把它删了. 标记的处理就是, 因为移动后虽然位置变化了, 但它的相对位置还是一样的(就是两个段的上下关系不变)可以二分出询问涵盖的范围算.

拓展到树上, 进行树剖, 那么对每个段如果它即将移动出这个重链, 因为是取max, 所以只要考虑其第一个元素的移动, 等它整体移动出下面那条链后把它再插到上面那条里.

复杂度计算就是, 一开始有 $O(n)$ 个段, 每个段最多有 $log$ 次跳出重链的过程, 复杂度就是 $n\log n$ 了.

T2

查询一个区间的子区间里出现次数超过一半的数的权值和, 定义它叫绝对众数, $n, q\le 1e6, 10s$

看数据范围先猜测复杂度根号或2log

显然这个绝对众数一个区间只有一个.

一个容易想到的转化是, 把等于 $c$ 的设为1, 不等于的设为-1, 那么这个数在这个区间是绝对众数等价于区间和大于0.

那么把区间和差分成两个前缀, 若 $[l, r]$ 的绝对众数是 $c$ , 即 $l\le r$ 且 $pre_r-pre_{l-1}>0$ , 这是区间逆序对, 可以二次离线莫队等解决.

颜色很少的时候这是对的, 但颜色多了不行, 考虑进行一个匹配: 每个1向前后第一个未匹配的-1匹配, 这个匹配实际上标记了区间和可能大于0的所有点, 那么此时只有匹配的点可能出现在绝对众数为 $c$ 的区间中, 而被标记的总点数显然是 $O(n)$ 的

那么我们可以对每个颜色抽出匹配了的位置跑一遍, 一次莫队的复杂度是 $n\sqrt q+q$ , 发现如果没有第二项是对的, 而有了遍历询问这一步又变成 $O(nq)$ 的了.

进行根号分治, 则对出现次数大于 $\sqrt n$ 的颜色每个跑一遍莫队, 复杂度是 $n\sqrt q+q\sqrt n$ .

对于次数小于 $\sqrt n$ 的颜色, 设颜色 $i$ 的次数为 $cnt_i\le \sqrt n$ , 总点对数就是 $O(\sum_i {cnt_i}^2)$ , 直接看似乎是 $O(n^2)$ 的, 但实际上只要提出一个 $\sqrt n$ 就是 $O(n\sqrt n)$ 的了.

那直接把点对放到平面上, $(l, r)$ 能贡献当且仅当询问的 $ql, qr$ 满足 $l\ge ql, r\le qr$ , 需要一个 $O(1)-(\sqrt n)$ 修改询问的二维数点. 离线用分块维护扫描线即可.

T3

给 $m$ 个半平面和 $n$ 个点, 设两个半平面 $i$ , $j$ 包含的点的集合的对称差大小为 $f(i, j)$ , 一个半平面的大小为 $size_i$ , 构造一个排列使得 $size_1+\sum_{i=1}^{n-1} f(i, i+1)\le 1. 8e8$

数据范围 $n, m\le 1e5$

相当于半平面莫队模板吧, 看下面的半平面莫队.

然后spj复杂度是平方的, 评测一个人需要一年.

lxl讲课-DS is good

半平面技巧

给定平面上的一些点, 查询一个半平面上的信息

六分树

通过三条斜线把点集均分成六份, 每次会递归进入6个儿子中的4个, 复杂度 $O(n+nm^0. 77)$

分块旋转扫描线

考虑我们连续的旋转一条线, 维护以这条线为y轴时点集的x轴顺序, 那么半平面里的点就是序列的一个前缀或后缀了. 由于对于任意两个点, 他们顺序(一个在另一个前面的关系)的翻转是 $O(1)$ 的, 所以复杂度是 $O(n^2)$ 的

那你直接把它分块, 每个块复杂度 $O({\sqrt n}^2)=O(n)$ , 它就成了 $n\sqrt n$

半平面莫队

超级厉害的技巧

如果这些半平面都交于一点, 那这个问题是简单的, 因为旋转一遍的过程中我们的半平面区域包含一个点/不包含一个点的切换次数是 $O(n)$ 的.

而如果把半平面都平移到一个点, 这个过程的切换次数是 $O(n^2)$ 的, 一定爆炸.

于是考虑平衡这两个做法, 在给定的 $O(n)$ 个点中随机选 $\sqrt n$ 个作为关键点, 把直线平移到这些点再对没给点一起旋转.

具体的, 对于每条线, 我们找到从它向下平移的过程中碰到的第一个点, 那么过程中期望经过 $\sqrt n$ 个点, 所以总复杂度是每条线经过 $\sqrt n$ 个点的 $m\sqrt n$ 加上每个关键点旋转的 $n$ , 为 $(n+m)\sqrt n$

等差数列位置区间加, 等差数列位置求和

用第十分块的方式时间分块

时间分治后问题变成三个子问题:

算一个修改对另一个询问的贡献
静态算一个询问, $O(\sqrt n)-O(n)$ 询问和重建
静态算一个修改, $O(\sqrt n)-O(n)$ 修改和查每一个位置.

对于第一个问题, 贡献就是修改和询问这两个等差数列位置的交集*修改的值, 交集要离线下来一起算, 不然在线做不到O(1)

对于第二第三个问题, 套用”初始化”的方法进行根号分治, 对于大于的暴力, 小于的维护前缀和, 平衡成 $O(n^\frac {5}{3})$

3dmq

长方体加, 长方体乘, 长方体求和, 长方体均为左下方的3face长方体

和上一个题一样时间分块, 则仍然考虑三个子问题:

修改对询问的贡献显然可以快速算吧
询问需要3side加和乘, 可以离线一维变成

给定一些点, 求半平面内相等点对个数

直接用上面半平面莫队做, 插入点和删除点都是平凡的.

半平面逆序对

求半平面有多少点构成逆序对

对于 $(x_i, y_i)$ , 预处理有多少 $j\ s. t. \ x_i<x_j, y_i>y_j$ , 那么半平面的直线斜率为正就是半平面内 $f_i$ 的和, 否则再处理与这个点构成顺序对的对数 $g_i$ , 然后拿总对数减去半平面的 $g_i$ 的和即可. 转化成了半平面数点.

P8283 「MCOI-08」Dantalion

给一个序列, 每次问区间里有多少个子区间里值构成的集合关于异或封闭

这个东西看起来很像线性基, 考虑若一个区间的线性基大小为 $k$ , 则这个区间的颜色数必然是 $2^k$ , 由于颜色是满足包含单调性的, 所以可以进行 $\log n$ 遍双指针, 求出一共 $n \log n$ 对 $(l1, l2, r, k)$ 表示 $\forall l\in [l1, l2], [l, r]$ 的颜色段数为 $2^k$ .

然后对于这些 $n \log n$ 个对, 我们需要知道它的线性基大小是否和颜色数匹配, 所以需要扫一遍得到每一个的线性基.

最后就是我们知道若干个 $(l1, l2, r)$ 是满足条件的, 直接二维数点即可.

考虑继续优化

线性基可以优化成1log的, 方法是我们添加数的时候维护线性基每个位置什么时候有值, 并维护1-r的线性基, 那么 $l, r$ 点线性基就是所有最早位置＞ $l$ 的, 那么此时只需要在每个位置扫一遍线性基上的位置扫一遍右端点在这里的对就可以完成1log统计

接下来是数点的优化, 可以按 $l$ 为横轴, $r$ 为纵轴做一个平面, 则 $(l1, l2, r)$ 就是平面上的一条横线, 而询问是问一个矩形内包含的线段总长度, 注意这里右端点在外面. 如果允许离线这个可以扫描线, 做成扫描 $r$ 轴, 区间加和区间历史和, 那么要求在线就把维护的数据结构可持久化即可. 复杂度2log.

把它优化成1log, 首先对于 $(l1, l2, r)$ 差分成 $(1, l2, r)-(1, l1, r)$ , 然后把加的和减的单独计算. 因为一开始我们说明过对于同一个 $k$ , 它是不会有包含的, 所以拆成 $1, l, r$ 后 $l$ 和 $r$ 分别单调递增, 那么我们把它排序后做前缀和, 询问区间包含的一定是连续的一段. 求出询问区间 $L, R$ 里第一个 $l>L$ 的和最后一个 $r<R$ 的, 最后直接减去多算的 $L \times len$ , $len$ 为包含的线段个数.

P4062 [Code+#1]Yazid 的新生舞会

给定一个序列, 求有多少子区间的众数的出现次数超过子区间长度的一半, 线性复杂度

首先它和T2长的很像, 可以考虑仍然使用那个对于每一个数看成1和-1, 然后1和-1匹配得到若干个连续段的做法, 那么需要找到一个 $O(1的个数)$ 跑匹配的方法, 具体的, 可以用一个并查集维护, 对每个集合额外记录一个最左边的端点, 每次匹配之后就把这次匹配行成的一个和为0的段合并, 那么找匹配的时候只要看前一个元素的集合的最左边元素的再左边一个.

然后现在要对每一个段求答案, 划分成若干个段的好处是原来的区间逆序对变成了现在相邻两数差为1的逆序对, 考虑以下标为 $x$ 轴值为 $y$ 轴会画出一个折线, 从前往后扫不断把数加入到一个值域桶里, 那么+1-1时, 比当前大的数的个数的变化量其实就是刚才那个桶里对应位置的值了.

P7889 「MCOI-06」Eert Tuc Knil

给一个 $n$ 个点的有根树, 点 $i$ 权值为 $a_i$ , 每次询问给出 $u$ , $x$ , 问如果给 $u$ 子树整体加上 $x$ , 那么它内部包含 $u$ 的连通块的权值和最大多少.

看到这个题发现这个最大连通块和其实和序列上的最大子段和是很像的, 可以写出一个简单dp: $f_i=\sum_{j\to i}{\max(f_j, 0)}$ .

现在加上了函数 $x$ , 可以设 $f_u(x)$ 表示给 $u$ 的子树整体加上 $x$ 后它的最大连通块和, 把它看成一个关于 $x$ 的分段函数, 则因为叶子分两段, 那么每个点的分段都是 $O(n)$ 的, 用启发式合并即可.

半平面数点数据随机做法:

把平面分成 $\sqrt n \times \sqrt n$ 块, 每块期望常数个, 半平面经过 $\sqrt n$ 个块, 那么完整包含的部分可以前缀和, 一个块内的可以暴力判定, 复杂度期望 $\sqrt n$ , 感觉相比那几个半平面莫队之类的很可写啊!

Day6 contest of LXL

T1

给一个由栈构成的序列和常数A, 每次给一个区间里一起加入一个数, 或者询问从这个栈开始连着几个的乘积大于A

把时间维和序列维换一下, 扫描序列维, 维护时间维, 若以序列为横轴, 时间维为纵轴, 则一个修改就是平面上一条横线, 一个询问则相当于询问一点的区间历史和(差分得到一段). 扫描线进入一个修改时, 一个修改会影响向上log个不是1的段, lxl说随便数据结构至少1log找一段, 每次进行一个区间修改, 所以数据结构支持区间修改和单点历史时刻和, 线段树即可

也可以1log找出所有的被影响的段, 把一堆插入的1缩成1个, 在平衡树上找log个后继相当于finger search.

修改也可以1 log finger search性质修改.

总结

这种扫描线是利用了一个维度的不对称性, 时间维的结构有时会比序列的更简单.

CF700D Huffman Coding on Segment

给定一个长度为 $n$ 的串, $q$ 次询问一个区间的最小二进制编码长度(给每个数找一个二进制对应, 总长度最小)

首先全局的是经典的, 可以按出现次数建huffman树, 那么每个点的编码就是根到叶子路径走过边形成的01串, 长度就是深度*权值, 所以相当于在这一段以次数为代价合并果子.

我们要维护区间每个数的次数, 这个东西常常莫队. 因为这类问题常常不弱于矩阵乘法, 如区间出现次数第 $k$ 大的这类的, 此时考虑莫队.

但显然不能暴力合并果子, 要进行优化, 对于出现次数小于 $\sqrt n$ 的, 可以 $O(1)$ 代价批量合并一个数, 剩下的数都是大于 $\sqrt n$ 的, 可以进行暴力(势能为剩下数的个数). 就能 $O(\sqrt n)$ 完成一次查询.

CF1476G Minimum Difference

有一个长为 $n$ 的数组, 进行 $m$ 次询问, 每次为以下两种中的一种:

1 l r k: 给定区间 $[l, r]$ , 你需要求出最小的 $\text{dif}$ , 使得能够选出 $k$ 个互不相同的数 $a_1, a_2, \cdots, a_k$ , 令这些数在区间中的出现次数分别为 $cnt_1, cnt_2, \cdots, cnt_k$ (任意 $cnt_i > 0$ ), 则 $\text{dif}$ 为这些 $cnt_i$ 的极差; 若无法选出 $k$ 个数, 则输出 $-1$ .

2 p x: 将位置 $p$ 赋值为 $x$ .

和上一个一样进行莫队, 求出每个出现次数, 和盼君勿忘一样有数的出现次数不同的只有 $\sqrt n$ 种, 因为有修改所以待修莫队.

lxl现场造题

三维空间有一堆长方体, 求他们的并的体积. 长方体个数 $10^5$ , 时限10s.

扫描线一维, 然后是动态的二维问题, 每次要矩形加一减一或查询0的个数, 那么就用上面的rprmq2把最大值变成最小值再维护最小值个数.

Day7 contest of CYX

T1

给一个树, 一开始都是蓝边, 每次删掉一条全是蓝色的链上的一条边, 然后再把链的两端点连一条红边, 问能不能把它变成另一棵全是红色的树.

法1

一条链可以进行操作当且仅当它上面只有一条要删的边, 然后树剖线段树求每个链覆盖了多少条要删的边每次找最小的即可.

法2

把操作反过来, 那么每次能操作的就是两个点间有一条红边有一条蓝边的情况, 操作后, 由于任何一个接下来的操作都不能再经过它了, 所以它相当于变成了一个点, 可以启发式合并的把原来这些点的边添加到一个上, 重复这个过程.

T2

todo

T3

todo

cyx讲课-只有dp不会, 不会就是不会

四边形不等式

这里是讨论的最小值

四边形不等式, 等价于二维差分后 $\le 0$ , 感觉一般写成 $w_{l, r}+w_{l-1, r+1}\ge w_{l-1, r}+w_{l, r+1}$ 的形式更容易看性质啊, 那么发现这个式子其实就是在矩阵上二维差分.

满足四边形不等式的矩阵, 称为蒙日矩阵, 在每一行最小值位置单调递增(决策单调性).

蒙日矩阵的行列没有关系, 转置后仍然满足条件

常见形式1DAG上最短路

$f_i=\min{f_j+w(j, i)}$ , 其中 $w$ 满足四边形不等式

结论: $f$ 满足决策单调性

因为一个 $j$ 贡献一个后缀的 $i$ , 那么可以使用二分栈维护. 二分栈的元素 $(l, r, j)$ 表示在区间 $[l, r]$ 中最优决策点为 $j$ .

常见形式2DAG上定长最短路

$f_{i, j}=\min f_{i-1, k}+w(k, j)$

$f$ 同时具有决策单调性和凸性, 可以wqs二分

常见形式3区间DP

$f_{l, r}=\min_{k\in[l, r]} {f_{i, k}+f_{k, j}}+w(l, r)$

要求 $w$ 还满足区间包含单调性

可以把 $n^3$ 优化成 $n^2$

基站选址

经典线段树优化dp了

然而这题状态是满足四边形不等式的!

证明: 考虑dp式子:

$$
f_{i, j}=\min k {f{i-1, k}+cost(j, k)}+c_j \
cost(l, r)=\sum _{i=l}^r{[d_i-s_i > d_l][d_i+s_i < d_r]w_i}
$$

那么考虑当 $cost$ 扩展一个时, 记两个条件为 $a_1$ , $a_2$ , 相比于 $cost_{l, r}$ , $cost_{l+1, r}$ 增加了原来一些 $a_1=0, a_2\ne 0$ 的部分, $cost_{l, r+1}$ 为原来一些 $a_2=0, a1\ne 0$ 的部分, 而 $cost_{l-1, r+1}$ 除了完整包含这两类外还有一些 $a_1=0, a_2=0$ 的部分, 所以证明了包含大于相交.

然后可以凸优化把原来的 $nk\log n$ 优化成 $n\log k\log n$

FJOI物流仓库选址

数轴上 $n$ 个点, 选择最少1个最多 $k$ 个仓库, 第 $i$ 点位置 $x_i$ , 在这里建立代价为 $c_i$ , 若 $i$ 到最近仓库距离为 $d$ , 代价为 $a_id$ , 最小化代价.

设第 $i$ 个仓库在 $j$ 时的费用为 $f_{i, j}$

$$
f_{i, j}=\min{f(i-1, k)+\sum_{p=k}^j\min({x_p-x_k, x_j-x_p}})*a_p+c_j
$$

转移函数满足四边形不等式, 可以凸优化去掉第一维

证明: 仍然看

$$
cost(l, r)=\sum_{p=l}^r\min({x_p-x_l, x_r-x_p})*a_p+c_j
$$

像上面一样考虑拓展一个的情况, 发现相比 $f_{l, r}$ 有两个变化:

增加了新的位置的数, 但这里距离正好所以直接可以不管.
所有取 $min$ 的 $x_l$ , $x_r$ 变了, 且都是往大里变, 那么取个 min 就显然是包含大于相交了.

凸优化后就是考虑不考虑限制随便选的情况, 设 $g_i$ 表示仓库在 $i$ 时考虑前缀 $[1, i]$ 的代价, $h_i$ 表示仓库在 $i$ 前时前缀 $[1, i]$ 的代价, 再预处理每个前缀所有点到 $1$ 的代价, 后缀所有点到n的代价就可以快速通过 $h$ 和 $g$ 互相转移了. 两个转移都可以斜率优化. 最后复杂度就是 $O(n\log V)$

IOI2014假期

$n$ 个城市一行, $i$ 号城市权值为 $a_i$ , 给定起点 $s$ 每次可以选择向左或向右移动一步或者获得现在所在位置的权值, 权值不能重复获得, 求 $d$ 天内拿到的最大权值和

期间只会回头一次, 否则一定可以调整为不劣的方案. 设走过的区间为 $[s-l, s+r]$ , 移动用时就是 $l+r+\min(l, r)$ , 那么答案就是前 $d-(l+r+min(l, r))$ 大的和这个可以用主席树做.

可以把形式转化成固定 $l$ , 则 $f_l=\max{sumkth(d-l-r-min(l, r))}$ , 其中 $sumkth(k)$ 表示前 $k$ 大的值. 那么只要看看max里面的部分是否满足四边形不等式就能证明 $r$ 对 $l$ 是否有单调性. 考虑 $w(l, r)+w(l-1, r+1)$ 与 $w(l-1, r)+w(l, r+1)$ 的大小关系. 首先等式两边包含的数的个数显然相同, 而左边的任何决策右边都可以覆盖到, 所以这里相交大于等于包含, 式子成立.

既然有决策单调性, 因为算一个决策的代价不是 $O(1)$ 所以单调栈的复杂度是2log, 而因为计算一个点的代价是不依赖于左右两边的答案的, 所以可以分治维护决策单调性做完.

CTT2018旅行

n个点的树, 以s为根, 要把编号区间分成恰好 $k$ 段, 一个区间的得分是从 $s$ 出发的最短回路的边数, 最大化得分和 $nk\le 1e5$

$f_{i, j}=\max_{0\le j’\le j}{f_{i-1, j’}+w(j’+1, j)}$

首先最短回路等价于虚树边权和的二倍

解法1:

todo

解法2:

$w$ 是满足四边形不等式的, 可以分治维护决策单调性, 每次询问中点这个决策的代价.

但 $w$ 很难维护, 第一眼是 $\sqrt n\log n$ 的分块?

然而这题暴力莫队是对的, 考虑在分治过程中, 当前左右端点是分治区间, 那么现在它进入左区间的时候右端点移动到左区间右端点固定不动分治下去, 一会等算完了再移动到右区间, 那么发现这个过程里, 左右端点移动是 $1. 5$ 区间长度的, 所以总复杂度是 $n\log n$ 的. 注意这里分治区间是决策点的区间

实际实现时不用这么维护, 要求哪里时直接移动过去是不比我们上面分析的做法劣的.

启发了一种分治套莫队的方法

Slope Trick

APIO2016烟火表演

给一棵 $n$ 点的带权有根树, 要求给每一个边重新赋值使得根到所有叶子的路径权值和相等, 代价为新旧边权的差的绝对值, 最小化代价

记 $f_{u, x}$ 表示修改 $u$ 的子树, 使高度为 $x$ 的答案

$f_{u, x}=\sum_{u\to v}\min_{0\le i\le x}{f_{v, x-i}+ \vert w_{u\to v}-i \vert }$

转移时先把儿子和绝对值函数做 $\min, +$ 卷积, 再加起来.

把 $f_{u, x}$ 看成关于 $x$ 的函数, 那么一开始这个函数是下凸的(叶子处 $f_0=0, f_i=\inf$), 运用归纳法, 若儿子都是下凸的, 那么绝对值函数显然下凸, 和下一层的函数加起来仍然是下凸, 证明了每一时刻它都是非严格下凸分段函数, 且每一时刻斜率为整数.

于是Slope Trick 维护即可.

然后这题又比较特殊使得代码很简单, 做闵和就是光让函数底部向右平移, 而不改变左边斜率(显然要让函数底部向右平移 $w$, 此时左边正好是接上了长 $w$ 的斜率为 $1$ 的线段不用处理)

ARC070ENarrowRectangles

$f_{i, j}$ 表示前 $i$ 个区间最后一个左端点在 $j$ 的代价, 则有

$$
f_{i, j}=\min_{j-a_{i-1}\le k\le j+a_i}(f_{i-1, k}+ \vert j-l_i \vert )
$$

因为是平面, 所以 $j$ 是无限空间, 可以考虑继续使用刚才的Slope Trick维护, 由于是凸函数, 可以直接根据 $j$ 讨论出最小值是在 $j-a_{i-1}$ 还是在 $j+a_i$ 取得, 那么就成了简单的函数平移. 所以转移就是, 先给上一个函数加上一个绝对值函数, 再把两边向中间平移.

讲的有点快啊

老鼠进洞

$n$ 个球位于, 第 $i$ 个位置为 $a_i$ , $m$ 个洞, 第 $i$ 个位于 $b_i$ , 每个球往洞里走, 一个洞对应一个球, 最小化移动总距离

模拟费用流经典为什么在动态规划里呢? 因为也可以Slope Trick.

法1动态规划

显然可以有他们移动路径不会交叉, 可以看成选取 $n$ 个洞按顺序一个对一个配对, 把路费算在边的左端点上.

记 $f_{i, j}$ 为扫描了前 $i$ 个左端点, 求比洞多 $j$ 个的费用:

那么因为当前球比洞多或少, 一定会有相应的球滚回来或滚过去, 那么此时经过右端点那条边的球数就是 $j$ , 所以扫到球时

$$
f_{i, j}=f_{i-1, j-1}+ \vert j \vert (x_{i+1}-x_i)
$$

扫到洞时 $f_{i, j}=\min {f_{i-1, j}, f_{i-1, j+1}}+ \vert j \vert (x_{i+1}-x_i)$

仍然是下凸折线, 但此时 $\vert j \vert (x_{i+1}-x_i)$ 的斜率可能很大, 所以点要带权. 而函数变换就是遇到洞要把斜率为0的部分(函数的底)扩大一个, 平底可能会拆开支持一个 split

对于第一种转移, 相当于平移一位再加上一个绝对值函数, 问题是这里 $\vert j \vert (x_{i+1}-x_i)$ 的斜率较大, 要改为点带权, 而第二种转移仍然套路的讨论一下它的平移方向再加上一个绝对值函数.

法2模拟费用流

老鼠进洞!

建出模型是一个二分图, 左边表示球右边表示洞, 分别向源点汇点连(1, 0)的边, 中间两两连(1, 球和洞距离)的边跑费用流.

如图

左边是球, 右边是洞, 那么增加最下方的一个球/洞时, 可能有以下几种负环和增广路:

红色的增广路, 表示把一个球和最近都一个洞匹配
蓝色的负环, 表示这个球替换掉原来一个匹配的球
紫色的负环, 不会出现, 因为会只留增广那部分
绿色负环, 表示新洞替换掉一个匹配的洞

法3贪心

路径不会交叉, 可以划分若干个分界线, 两个分界线间的球向左向右状况相同.

设 $f_i$ 表示前 $i$ 个点正好没有都匹配了的最小总路费.

然后呢理解不能todo

杂题部分

莫名选物体

n个物品, 权值 $a_i, b_i >0$

选择一个物品序列 $i_1. . . i_k$ , 最大化

$$
\sum^k_{j=1}((j-1)a_{i_j}+b_{i_j})
$$

对每个 $k$ 求最值, $n\le 3e5$

贪心加dp

首先你把 $a$ 排序

贪心1: $k$ 从小到大的过程中, 一个东西成为最优解的一部分后不会在出来

证明: 考虑证明每次贪心都会遇到它, todo

牛逼老师题CF573E

todo

莫名计数

求有多少个长度为 $n$ , 值不超过 $m$ 的整数构成的序列 $a$ 满足 $a_i%a_{i+1}\ne 0$ , 对Q取模

首先有dp, 设 $f_{i, j}$ 表示前 $i$ 个数最后一个是 $j$ 的方案数

$$
f_{i, j}=\sum_{k%j\ne 0, k\le m}f(i-1, k)\\
=\sum 1\le k\le m f(i-1, k)-\sum_{k \vert j}f(i-1, k)
$$

乱码日文题

用 $1\times 2$ 骨牌覆盖 $H\times W$ 棋盘, 不重叠不超出, 两种方案不同当骨牌覆盖的格子集合不同. 膜998244353. $H\le 5, W\le 10^9, 2s, 1G$

todo

Day1 contest of TYY

T1 小N的独立集

T2 整数序列

T3 有处存储

TYY杂题选讲-%%tyy

UOJ67 新年的毒瘤

UOJ575 光伏元件

UOJ577 打击复读

UOJ152 汉诺塔

UOJ153 世界线

UOJ218 火车管理

Sol1

Sol2

SDOI D1T3 子串统计

UOJ727 团队竞技

UOJ177 新年的腮雷

UOJ730 蚂蚁和方糖

UOJ732 鱼 2

Day5 contest of LXL

T1

T2

T3

lxl讲课-DS is good

半平面技巧

六分树

分块旋转扫描线

半平面莫队

等差数列位置区间加, 等差数列位置求和

3dmq

给定一些点, 求半平面内相等点对个数

半平面逆序对

P8283 「MCOI-08」Dantalion

P4062 [Code+#1]Yazid 的新生舞会

P7889 「MCOI-06」Eert Tuc Knil

半平面数点数据随机做法:

Day6 contest of LXL

T1

总结

相关例题

饮食区

相关例题UOJ515

相关例题Comet OJ Contest#14 D

相关例题Ynoi2009 rprmq1

相关例题Ynoi2019 rprmq2

T2

T3

lxl讲课-lxl

LuoguP7125 Ynoi2008 rsmemq

CF1491H

奇妙小技巧

CF700D Huffman Coding on Segment

CF1476G Minimum Difference

lxl现场造题

Day7 contest of CYX

T1

法1

法2

T2

T3

cyx讲课-只有dp不会, 不会就是不会

四边形不等式

常见形式1DAG上最短路

常见形式2DAG上定长最短路

常见形式3区间DP

基站选址

FJOI物流仓库选址

IOI2014假期

CTT2018旅行

解法1:

解法2:

Slope Trick

APIO2016烟火表演

ARC070ENarrowRectangles

老鼠进洞

法1动态规划

法2模拟费用流

法3贪心

杂题部分

莫名选物体

牛逼老师题CF573E