值域

\(\text{Link - Luogu Blog}\) 原题传送门 没啥重要的事情，就是终于过了这题非常开心，发现自己是莫队的时间戳部分写错了调了 114514 年我也只能说是十分趣味。 以及今天深刻地认识到了带修莫队应该 len=pow(n,0.66);。 就是裸的带修莫队+值域分块，就不说了， ......

题目大意: 给一个序列 n 会有n次操作, 每次都会 删除 一个数 这个数 是 连续子序列里面 最大的逆序对的个数 ^ Q[i], q[i] 给出 思路 : 启发式 拆分, 每次选择长度小的序列来 进行处理 数学化: rev(逆序对个数) rev(x + 1, r) = rev(l, r) - re ......

这其实是一道洛谷模板题，题目是5435 对预处理的讲解可以看看[这个博客](https://www.luogu.com.cn/blog/chtholly-willem/solution-p5435)（代码看自己的，见下） ``` void getprime() { for(int i=0;iv[i] ......

这个分治策略其实跟整体二分差不多，但是它的应用面比较单一和具有针对性。 通常是 $dp_1,dp_2,dp_3,...,dp_n$ 只有 $O(d)$ 段。然后我们通过分治来看 $dp_i=v$ 的应该是哪一段。 ``` def solve(l,r) if dp(l)==dp(r) fill dp( ......

首先 $c$ 很大，因此复杂度跟 $c$ 有关的项肯定只能是 $\log c$ 之类的。 类比 IOI2021 dungeons 的套路，我们**对值域进行分层**，假设 $c\in[2^{\omega-1},2^{\omega})$，考虑令重量在 $\ge 2^{\omega-1}$ 的物品为“重 ......