P7446 [Ynoi2007] rfplca 题解
一道分块题，应该是 Ynoi 题里面为数不多的不卡常题(?)，反正我没卡就过了，这道题 Idea 不错。
前置知识：根号做法的弹飞绵羊，下面认为读者已经会了这个做法。
首先类似于弹飞绵羊，我们设一个 \(Top_i\) 表示当前这个点不断往前跳，跳到这个块的最前面的位置（当然也可以跳出块外第一个位置，但是这道题这么写好点），然后 \(fa_i\) 就是他父亲，不包括区间整块打的标记。
当然如果这个点 \(fa_i\) 已经在块外了就直接令 \(Top_i = i\)。
下面认为 \(fa_i\) 表示只在暴力单点修改情况下的父亲，\(ffa_i\) 表示其真实父亲。
先看修改操作：\([l,r]\) 区间减，\(\red{x \geq 1}\)。
按照分块老套路，我们可以对于零散块（含 \(l,r\) 在同一块）的情况暴力减去并且重构，但是对于整块的情况我们就不好搞了，因为我们没办法快速维护 \(Top\)……
但是观察到 \(\red{x \geq 1}\)，这意味着每一个点至多修改 \(\sqrt{n}\) 次其 \(ffa_i\) 就会跳出这个块，于是我们可以考虑对于每一个块首先暴力重构，当这个块内的所有 \(ffa_i\) 都跳出这个块了，就意味着这个块实际上没有必要再重构了，可以直接跳过，这块的总复杂度是 \(O(n\sqrt{n})\) 的。
当每一个块被区间减的时候，我们直接打一个 \(tag_{ys_i} \leftarrow tag_{ys_i} + x\) 表示这块整体区间减的标记，于是我们得到了 \(ffa_i=fa_i - tag_{ys_i}\)，其中 \(ys_i\) 表示 \(i\) 所在块标号。
至于维护这个块是否没有必要重构，我们可以在每一次重构的时候看下是否所有 \(Top_i=i\)，满足就可以不重构了，否则就需要重构。
然后查询操作的话我们模仿树剖求 LCA 就好了，先按照 \(Top_i\) 跳，然后按照 \(ff_i\) 跳即可。
这道题写代码的时候需要注意：
- 第一个点是需要单独开一个块的，同时查询操作需要特判一下。
- 注意这些操作（暴力重构，查询操作）是需要使用 \(ffa_i\) 的，而暴力单点修改的时候是使用 \(fa_i\) 的。
- 这道题是不太卡常的，被卡常了是你写丑了。
Code：GitHub CodeBase-of-Plozia P7446 [Ynoi2007] rfplca.cpp