「找性质+线段树(兔队线段树的应用)」[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 的。

#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 ;
}