WC2023 解题报告

WC2023 解题报告

stairs

考虑阶梯的右下折线，称竖线为 0，横线为 1，从上到下形成一个 01 序列。
原题要求的子楼梯边界格数转化成 01 序列里靠前的 0 和靠后的 1 的位置差。

我们将 01 序列从 0 开始标号，那么最后一个位置是 \(p\)。
由于保证了查询的 \(q|p\)，我们标记所有形如 \(kq,k\geq 0\) 的位置。
由于位置 0 的值为 0，位置 \(p\) 的值为 1，所有标记的位置一定会出现一对相邻的 01，即有解。

如果得到了 01 序列，容易通过二分出中间的标记点判断递归左右。

而修改操作对于 01 序列的改动形如：

1. 添加一整段 1。
2. 添加一段 \(k\) 个 1 后，在末尾截取掉一段包含 \(k\) 个 1 的段。

使用平衡树维护。由于只撤销添加一整段 1 的操作，较好处理。

总复杂度 \(O(m\log^2 m)\)。

contest

鱼大做法太阴间了。笔者认为相较于更阳间的做法是 dls 调整法。

一些贪心和随机化做法在此题中也拿到了超高分，例如 hzr 的随机化拿到了 92pts，xzy 贪心拿到了 72pts。

ds

叙述一个 txx 的 \(O(n\log n)\) 做法。

我们考虑对于一个点 \(x\) 将其到根的路径上的边权换成一个连续区间 \([1,dep_x]\)。
具体操作考虑执行：

for(i=1;;i++){
    if(query(x)==i)break;
    exchange(i,query(x));
    if(query(x)==i)break;
}

不妨记这段值域区间为 \([1,w]\)，我们不断选取下一个点 \(x\)，如法炮制，可以将树剖分成若干条链，且我们知道链上的值域是连续的和链上的点集。这部分操作复杂度是 \(O(n)\) 的。

我们考虑将每条链上的边权按深度升序排列以得到每个点的具体在链上的位置和对应的边权。
一个 \(O(n\log n)\) 的做法是考虑快排的思想，仍然像上述链剖分的做法一般随机选取一个点集内的 \(x\)，不断做替换操作，之后询问可以将点集、权值分成两部分。

唯一剩下的问题是如何找到链头的父亲，也就是链头父亲目前对应的权值。
由于我们对链做好了排序，此时链头的权值是链头到根路径上的最大值，且链头父亲对应的权值是次大值。
我们想要求得次大值的话，一个简单的想法是考虑把最大值换成一个比次大值小的值，这样就能查出次大值了。

我们考虑一个最深的点 \(u\)，满足 \([1,dep_u]\) 以此分布在 \(u\) 到根的路径上。（这个 \(u\) 显然是值域最小的若干条链拼成的最后一个点。）

那么我们考虑能把最大值换成比次大值小的方法失效当且仅当这个链头接在 \(1\rightarrow u\) 的链上。
对于方法有效的情况，我们使用 \(dep_u\) 进行替换可以查询出次大值。
而方法失效的情况下，我们使用 \(dep_u\) 替换后查询出的值为 \(dep_u\)，我们考虑在 \(1\to u\) 的链上二分出链头挂载的位置。具体方法是挂载位置即更浅的边换过来最大值不变，而更深的边换过来最大值即改为这条更深的边。

那么我们得到了这个 \(O(n\log n)\) 的做法。具体来说它在考场上 txx 的实现中拿到了 76pts 的全场最高分。