ZR24 Summer A Day2 | DS

Mirasycle · 2025-03-21 16:08:27 · 算法·理论

去年暑假 ZR 集训 Day2 的笔记，代码和题解终于全部补完了/tuu。除了 DMOPC 那题真没听懂，网上也没有题解，我去问 xtq 了，但是问到一半他后来没回复我了/ll，那道题目描述和部分思路放在下方了，有会的人可以教我一下吗/kel。

P4719 【模板】动态 DP

可以用树剖或者全局平衡二叉树维护。

lct 维护子树信息

对于每个点记录所有轻儿子信息和。把 u 转成根后，u 所在重链就是平衡树上右子树了。

在 access 中 ch(x,1)=y 的时候 O(1) 修改即可。

P8265 [Ynoi Easy Round 2020] TEST_63

发现本题这些操作有点像 LCT，于是我们考虑用 LCT 的虚实边来维护树上的轻重边。也就是对应映射一下。那么每个 Splay 上面维护的便是一条重链的信息。

考虑将 y 变成 rt 的操作，是先 \operatorname{access} 和 \operatorname{splay}，再翻转。一次 \operatorname{access} 之后 y-rt 的所有边都变成了实边，对应一下也就是所有都变成了重边，但是显然不太符合实际情况。我们需要找到那些轻边在 LCT 中把他们变成虚边。因为根据轻边定义 sz_u > 2 sz_{son}，所以对于每条轻边必然存在一个 k 使得 sz_u \ge 2^k > sz_{son}。可以枚举 k 通过 Splay 上二分找到 sz_u \ge 2^k > sz_{son}，然后直接修。

对于统计重链第 k 大，在每次上述修改虚实边后一条重链会断成两段，我们将两段加入权值线段树中即可。

同时补充一下，对于上述 sz 的维护是在 LCT 中维护子树信息。做法是对于每个点记录所有轻儿子信息之和 gs ，改在 \operatorname{access} 中 ch(x,1)=y 的时候 O(1) 修改即可。子树大小就是 gs(u)+s(ch(u,1))+1。同时本题规定了在子树大小相同的时候，选择下接重链上编号更大的那个作为重儿子，于是我们还要记录最大编号。

然后有一个卡常小技巧就是用两个优先队列来代替 set，一个优先队列负责添加元素，一个优先队列负责删元素，这样子常数小了好多。

下面是对于 LCT 一些传统的函数内部细节的说明。

在 \operatorname{push} 中维护的信息 sz 信息不只是平衡树上信息了，还要加上其他轻儿子信息 gs。维护 val 代表实链异或和，也就是重链异或和。同时记录一下该重链中最大编号。

void pushup(int u){
   s[u]=1+gs[u]+s[lc]+s[rc];
   Mx[u]=max({Mx[lc],Mx[rc],u});
   val[u]=val[lc]^val[rc]^u;
}

在 \operatorname{access} 中由于要修改 Splay 中右子树信息，这一项的修改涉及到了重链断裂成两个重链，同时新的重链生成。轻儿子的信息修改。于是我们记录下一路需要断开的边的位置，然后从上到下倒着修改一下。需要用到函数 modify(u,v)表示断开 u 原先的右子树，连上 v。首先，把原先保存的两条重链权值删掉。因为重链会发生变化。然后维护轻儿子信息，也就是轻儿子的子树信息和，还有 sz 的排名保存下来。然后在权值线段树中加入新产生的两条重链，注意第二条重链要在 \operatorname{pushup} 更新过新的重链信息后再加入权值线段树。当然对于 \operatorname{access} 造成的重链数量变多，我们在 \operatorname{link}，\operatorname{cut} 和 \operatorname{makeroot} 这些调用 \operatorname{access} 的函数里面再修改，而不是立刻修改。

void modify(int u,int v){
    seg.update(1,0,V,val[u],-1); if(v) 
    seg.update(1,0,V,val[v],-1);
    if(rc) S[u].ins(s[rc],Mx[rc]);
    if(v) S[u].del(s[v],Mx[v]); 
    gs[u]+=s[rc]; gs[u]-=s[v];
    if(rc) seg.update(1,0,V,val[rc],1);
    rc=v; pushup(u); seg.update(1,0,V,val[u],1); 
}

然后 \operatorname{cut} 的时候，要注意我们先要根据子树大小看看谁是谁的父亲，然后本来要判断一下 v 是否是 u 的轻儿子，但是我们可以通过 access(u) 让 v 先变成 u 的轻儿子，这样子后面的操作就统一了。

暴力 dp 是 O(n^2) 的。

发现对于第一类转移是 i\to i 自己贡献到自己，这启发我们用线段树合并维护 dp，只需要打一个乘法标记就行了。可是第二类转移不满足啊，考虑约束条件经过异或哈希处理之后是要求哈希值相等，于是我们直接用哈希当成下标就可以完成统一形式了。很巧妙。

时间复杂度 O(n\log n)。

P6109 [Ynoi2009] rprmq1

先考虑扫描线，扫 x 维度。矩阵加法可以用差分转化为两次区间加，然后对于矩阵 \max，可以转化为执行时间 [1,x_2] 内的操作，但是只统计时间 [x_1,x_2] 内的区间历史最大值。

看到一段时间内的信息，可以用线段树分治来解决。但是这样子的话，由于每个询问会被分裂成 \log 个区间，所以最后 q 前面的系数会多一个 \log，会造成对于 q 是 2\log 的。这样子会被卡常。于是我们采用猫树分治就可以去掉这个 \log 了。

由于是猫树分治，所以每一层内部使用扫描线，从左往右扫，对于加法操作，左加右减就行了。每次在询问右端点查询区间历史最大值，为了防止在不受到前面的影响，我们可以在进入左端点前给后面加上 \infty，最后再减去即可。也可以打了一个标记，表示 his\gets mx。

时间复杂度 O(m\log^2n+q\log n)。

QOJ8240. Card Game

对于一个区间 [l,r]，其价值为维护一个栈从左往右将数压入栈中，如果当前即将加入栈中的数在栈中已经出现了就先执行弹栈直到那个数被弹出。强制在线，n,q\le 3\times 10^5。

设 t_i 为 i 后面第一次出现 a_i 的位置，记 \rm solve(l,r) 表示 (l,r) 的答案。对于 l 进行从右往左扫描线，

使用主席树 + 标记永久化即可。