题解 P5386 【[Cnoi2019]数字游戏】

不会莫队+链表，写了个莫队+并查集，过了。 乍看好像两层限制，直接莫队是 $\mathcal{O}(n^{5/3}\log n)$。如果莫队+线段树 $\mathcal{O}(n\sqrt{n}\log n)$ 常数太大不能过，那么就开发另一种常数小的 $\mathcal{O}(n\sqrt{n}\log n)$。 先对值域分块，对于每块跑回滚莫队，使得并查集能够撤销上次操作。接下来考虑 $[l,r]$ 的限制。若区间整个被覆盖，直接返回所有数对。否则，我们先把包含 $l$ 和 $r$ 的区间求出来，设 $l_1\le l\le r_1,l_2\le r\le r_2$，特判掉两个区间后加上 $(r_1,l_2)$ 的答案就可以了。 一个区间的答案是 $\Large \frac {L(L+1)}{2}$。我们在并查集上维护左端点和右端点 $[l,r]$。求一段区间包含区间的答案相当于每次我们在一段区间的根上加一下，然后区间求和。因为我们已经特判掉了两个相交的区间，所以这样不用管一段区间的根在哪里。 这样用序列分块来维护单点加区间查，时间 $\mathcal{O}(n\sqrt{n}\log n)$。实际常数很小，最大的点也只有 $\text{5.76s}$，常数大概是链表的 $2\sim 3$ 倍。