老套路题了
维护一个双向链表，从 \(1\) 到 \(n\) 枚举当前值作为第二大的值，那么可控区间就是\([pre_{pre_i},nxt_{nxt_i}]\) 所以两边取一边即可
求异或最大值需要可持久化 \(trie\) 树，这个是 \(trivial\) 的
刚做过一个维护等差数列的题目，所以这个就又 \(trivial\) 了
树剖来维护路径，那么对于主席树上的每个点，维护 \(d[x]\) 为公差，\(tag[x]\) 为首项
查询答案套上标记永久化，同时对于路径修改考虑先把左右的子区间统计出来，一段一段该，这样首项可以方便地得到
注意这个题目的数组大小，我开到了 \(60N\) 才过，其实也是因为树剖的原因
假的强制在线令人想到计算几何乱写里面的凸包的一个题，那么考虑一样的维护套路：维护每个节点的 \(size\)，如果满脸就合并
对于每次修改，维护 \((l-1,1,0),(r,k,b),(n,1,0)\) 表示三段的信息
归并的时候对于新的 \(k=mul(k_l,k_r),b=add(b_r,mul(k_r,b_l))\)
对于询问区间 \([l,r]\) 放到 \(\log\) 个点上二分 \(k\) 然后修改当前的 \(ans\) 即可
水高分容易 \(AC\) 难
用可持久化 \(fhq\ treap\) 做其实十分显然，所以 \(80\ pts\) 是 \(trivial\) 的
在 \(\texttt{mathew99}\) 的博客里面给出了卡掉的构造：先来一堆 \(ord=1\)，再来一堆 \(ord=2\)，一次类推，这样这个算法的复杂度到了 \(k\log n\)
而正解用了随机化：对于 \(fhq \ treap\) 的合并，这样写：
if((ord[l]==ord[r]&&rand()%(sz[x]+sz[y])<sz[x])||ord[l]<ord[r]) balabala...
else balabala....
这样单次复杂度期望 \(O(k+\log n)\)
证明？Itst说有2019/2018的论文，然而论文网址废掉了
记录两个 \(\texttt{fhq treap}\) 的手残的地方：
\((1)\) \(\texttt{split}\) 第二个的时候记得是 \(\texttt{split(x,size,x,z)}\)
\((2)\) 可持久化的时候 \(merge\) 写的可持久化后的点
每次操作，更新原来的平衡树，删除就删除，添加就添加
一开始得到一个二分的做法，但是发现这个没有单调性，所以就放弃了
换一个角度，\(fhq \ treap\) 对每个人的获得量和当前剩余的钱数进行维护
对于每个货物，二分得到买得起它的子树，打钱数减少和答案增加的标记
对于权值减少后的重复，也就是 \(cost\le v\le 2cost\) 的 \(v\) 暴力插入平衡树里面，剩下的因为肯定还是权值大的部分，直接合并
每次插入会导致 \(v\) 减少一半，所以复杂度是合法的
这个标记下方要注意，尤其是最后输出答案的时候要遍历全树下放标记
维护原始的平衡树来对付 \(3\) 操作，每次拆出来对应的区间合并就行
对于 \(2\) 操作，考虑 \(k<r-l+1\) 的时候这个区间是会被不断复制的
那么把区间分裂出来，然后倍增出来每段的树，最后统一合并区间即可
这里还有一个 \(trick\) 是定期重构，具体而言：
if(tot<M-N/3) rebuild();
其实代码不好写
原文：https://www.cnblogs.com/yspm/p/14399728.html