「找性质+线段树(兔队线段树的应用)」[Codeforces1209G2] Into Blocks (hard version)

这题是真的????????！是十分有趣题目！ xyx 写在 CSDN 里的题解是俩 log 的，但其实只需要用一点「兔队线段树」的小技巧，就可以优化到一个 log。 大概首先是要对上面那个 easy version 的一些结论进行形式化的提炼和总结。考虑答案的本质。考虑把一个颜色 $c$ 的出现区间化成左开右闭的形式 $[s_c,t_c)$，意思是对于区间中的每个 $i$ ，要把 $i,i+1$ 涂成一个颜色。那么可以发现如果对所有 $c$ 的该区间进行区间 $+1$ ，那么最后可以保留的颜色数就是相邻两个 $0$ 之间出现最多的颜色的数量和。正确性显然。…但这个转化确实十分神奇。 考虑用线段树快速维护这个东西。考虑需要维护什么信息： 1、需要维护分界点。即区间中被覆盖次数为 $0$ 的点。 2、需要维护颜色数。即区间中出现次数最多的颜色。 3、但是 $2$ 中有要求，要求必须是连续段中出现次数最多的颜色。而这个连续段的「连续」对应于一段连续的、覆盖次数 $>0$ 的段。 4、注意到要维护区间中出现次数的最大值，还要求连续且只有全局询问的话，有个小技巧。考虑让颜色 $c$ 的出现次数 $e(c)$ 放到 $s_c$ 处维护，记作 $w_{s_c}$，这样就只需要维护一个 $\max \{w_i,w_{i+1}\}$ 状物。 发现难以维护分界点？但是考虑到**只有全局询问**，于是可以借鉴兔队线段树里那个类似的思想。具体来说，发现对于线段树的根节点，有效信息是区间 $[1,n]$ ，而 $n$ 这个点必然不会被任何一个线段覆盖，也就是说如果统计全局信息，那么必然会存在 $n$ 为 $0$。那么就好办了，考虑用维护「区间最小值」来代替维护「区间分界点」。 具体细节方面，考虑维护区间中每段里颜色出现次数最大值 ${\rm seg}_x$，左/右端点所在连续区间的最大值 $\mathrm{lmax}_x,\mathrm{rmax}_x$ 。转移时考虑两个区间的 $\min v$ 的关系，其中 $v$ 是覆盖次数。 然后考虑修改操作，发现就是一个区间加再加一个单点维护。注意当 $l=r$ 时，有些量不是良定义，当作不知道就好了（赋值为 $0$） 。 注意到颜色的修改可以再单独拿一个 set 来维护。最终复杂度 $O(n\log n)$ 。 然后具体为什么能比 xyx 的做法少掉一个 log，个人认为是充分利用了『只有全局询问』这个性质，否则是不能用兔队线段树的 trick 的。 ```cpp #include <set> #include <cstdio> const int N = 200005 ; #define _be begin #define _en rbegin #define era erase #define ins insert using namespace std ; set <int> col[N] ; int seg[N * 3] ; int mnv[N * 3] ; int mxt[N * 3] ; int tag[N * 3] ; int lcon[N * 3] ; int rcon[N * 3] ; #define lc (rt << 1) #define rc (rt << 1 | 1) inline void _down(int rt){ if (tag[rt]){ mnv[lc] += tag[rt] ; mnv[rc] += tag[rt] ; tag[lc] += tag[rt] ; tag[rc] += tag[rt] ; tag[rt] = 0 ; } } inline void _up(int rt){ int ls = rt << 1 ; int rs = rt << 1 | 1 ; mxt[rt] = max(mxt[ls], mxt[rs]) ; mnv[rt] = min(mnv[ls], mnv[rs]) ; if (mnv[ls] < mnv[rs]){ seg[rt] = seg[ls] ; lcon[rt] = lcon[ls] ; rcon[rt] = max(mxt[rs], rcon[ls]) ; //此处由于最后要覆盖，所以 max_Time(rc) 本质上就是包含右端点的值。 } else if (mnv[ls] > mnv[rs]){ seg[rt] = seg[rs] ; rcon[rt] = rcon[rs] ; lcon[rt] = max(mxt[ls], lcon[rs]) ; } else { lcon[rt] = lcon[ls] ; rcon[rt] = rcon[rs] ; seg[rt] = seg[ls] + seg[rs] + max(lcon[rs], rcon[ls]) ; } } void upd(int rt, int l, int r, int ul, int ur, int v){ if (ul > ur) return ; if (ul <= l && r <= ur) return mnv[rt] += v, void(tag[rt] += v) ; int mid = (l + r) >> 1 ; _down(rt) ; if (ul <= mid) upd(lc, l, mid, ul, ur, v) ; if (ur > mid) upd(rc, mid + 1, r, ul, ur, v) ; _up(rt) ; } void cov(int rt, int l, int r, int p, int v){ if (l == r) return void(mxt[rt] = lcon[rt] = v) ; int mid = (l + r) >> 1 ; _down(rt) ; if (p <= mid) cov(lc, l, mid, p, v) ; else cov(rc, mid + 1, r, p, v) ; _up(rt) ; } int n, q ; int base[N] ; void mdf(int c, int mk){ int w ; if (!(w = col[c].size())) return ; // printf("%d %d %d %d %d\n", c, mk, *col[c]._be(), *-- col[c]._en(), (int)col[c].size()) ; cov(1, 1, n, *col[c]._be(), mk > 0 ? w : 0) ; upd(1, 1, n, *col[c]._be(), *col[c]._en() - 1, mk) ; } int val_it(){ return n - seg[1] - lcon[1] - rcon[1] ; } int main(){ int x, y, z ; scanf("%d%d", &n, &q) ; for (int i = 1 ; i <= n ; ++ i) scanf("%d", &base[i]), col[base[i]].ins(i) ; for (int i = 1 ; i < N ; ++ i) mdf(i, 1) ; printf("%d\n", val_it()) ; while (q --){ scanf("%d%d", &x, &y) ; z = base[x] ; mdf(z, -1) ; col[z].era(x) ; mdf(z, 1) ; mdf(y, -1) ; col[y].ins(x) ; mdf(y, 1) ; printf("%d\n", val_it()) ; base[x] = y ; } return 0 ; } ```