记录一些有意思的题。
\(*2600\).
维护一个当前指针endpos，指向序列末尾，同时维护一个 set<pair<int,int> >，表示每个数第一次出现的位置。
加操作可以直接加入，如果当前这个数已经出现过直接右移指针，否则维护一棵树状数组，加上贡献。
减操作直接将 endpos 左移即可。
回滚操作时，因为可以记录上一次操作，然后就可以直接减操作变成加，加操作变成减。
询问直接在BIT上查就行。
注意细节。
*2500.
感觉很显然啊。
考虑对于每个可重集，添加怎么维护 size。对于一个可重集，如果这个数存在，那么 size 乘二，否则 size 加一。
因为是对一段添加并且值域为 \(n\)，所以容易想到用 ODT 来维护数 \(x\) 是否存在。如果某一段的值为 0，就对这一段区间加。否则，就区间乘 2。线段树实现即可。
容易犯错的是没有保证 ODT 的复杂度正确，即在 ODT 上跳完之后没有将遍历的区间推平。
代码很好写。
*1800.
双指针。差分之后维护一个 gcd ST表，然后判 \(\gcd _{i=l}^r\not= 1\) 即可。
据说叫什么不删除双指针？
*2400.
简单树上莫队。
*2800.
lzqy_讲状态数 dp 的例题，好像秒了。
发现这个 \(x\) 很小，想一下哪些状态和 X-substring 有关，直接把需要的状态存下来，而这是很对的。
*2500.
区间 dp.
看到 \(n,x \le 100\)， \(\sum x\le 500\) 发现可以 \(O(n^3x)\)。
很奢侈地设 \(f_{i,j,k}\) 指令区间 \([i,j]\) 全部为 \(k\) 的代价。
发现这个不包含 \(k\) 覆盖的操作很难转移，考虑再设一个 \(g_{i,j,k}\) 表示令区间 \([i,j]\) 不含 \(k\) 的代价。
考虑怎么转移。
发现 \(g\) 的转移就是一个区间 dp 板子，发现 \(g_{i,j,k}\) 要对所有 \(({g_{i,j,o}+1})(1\le o \le x)\) 取 \(\min\)。
然后对着 \(f\) 区间 dp 一下，算上 \(g\) 的贡献即可。
需要注意什么时候需要对 \(\min(g_{i,j,k})\) 加一，不然可能会 WA on #2。
*2800.
首先知道是一个 \(\log\) 级别的。
考虑一个神秘哈希，如果一段区间合法，那么你对每个数值进行哈希，这段区间哈希值的和必定是 \(k\) 的倍数。注意到这只是充分条件，不能反推，所以多哈希几次就行。
常数太大不想调。
upd：调用太多次函数且不内联且早期丑陋马蜂导致的。重构完就过了。
upd2：过段时间又交一次又不过，发现原因是 umap 常数太大/fn，直接将原来的值改为指向离散化数组的位置就跑的飞快了。
感觉很神。
先有一个引理：b 中区间 \([l,r]\) 的最小众数必定为 \(b_l\) 或 \(1\)。用反证法证明。
然后对 \(lt=2,3,\dots,\max a\) 分别计算对应的最小众数为 \(b_{lt}\) 的 \(rt\) 数量。其余的为最小众数为 \(1\) 的区间。
问题转化为计算对应的最小众数为 \(b_{lt}\) 的 \(rt\) 数量。考虑一段 a 中区间满足能从 b 的 \(lt\) 走到 \(rt\) 当且仅当\(\forall x\in[lt,rt],a_x\ge b_{lt}\)。用链表维护答案。
嘴巴会的：
根号分治。
字符串哈希之后转化题意为：
长度为 \(n\) 的序列，\(q\) 次询问求最短的包含数 \(x,y\) 的区间长度。
这很根号分治。设阈值为 \(B\)。
如果 \(x,y\) 出现次数均小于 \(B\)，那么直接类似归并，在两个 vector 里面扫一遍即可。
否则出现次数 \(\ge B\) 的数 \(p\) 显然 \(\large\le \frac n B\)个。考虑一个暴力，从头到尾扫一遍，发现一个数\(q\) 和 \(p\) 的贡献要么是在 \(p\) 前且和 \(p\) 最近的 \(q\) ，要么是后面的且离 \(p\) 最近的 \(q\)。所以直接记录一下就可以了。所以和其他的匹配是 \(O(n\sqrt n)\)的。令 \(B=\sqrt n\)，丢到一个 umap 里面就做到了纯正的 \(O(n\sqrt n)\)。
ps:lsy提出在存 \(q\) 的位置里面二分，然后调一下 \(B\) 就可以 \(O(n\sqrt {n\log n})\)。感觉好写一点啊。
代码有点难写，但是嘴巴会了就是会了！！！1
标签：le,sqrt,lt,哈希,区间,杂题,dp From： https://www.cnblogs.com/lgh-blog/p/18043526