CF620E 【New Year Tree】题解

CF620E [New Year Tree]

前置知识：

线段树 + 状态压缩 + 子树 $Dfn$ 序 + 位运算小知识
难度:3 ~ 4星

题目大意：

(来自 Luogu 的翻译)

解题思路：

考虑到 $C_i$ 很小，有经验的同学不难看出来这是状态压缩。

那么实际上这道题有三种写法，分别为：

不加优化的线段树统计，开一个长度为 $60$ 的标记数组，记录区间内每种颜色出现的次数
发现只需要统计有没有出现，考虑使用bitset优化
考虑到 $C_i$ 只有60，直接状态压缩。

那么我们来分别讲一讲三种做法。

首先这三种做法的根本都是一样的，用线段树维护子树问题。

线段树维护子树问题相信大家都不陌生。

这里就讲一下：一棵子树 $Dfn$ 序的范围是 $[Dfn[u] , Dfn[u] + siz - 1]$

(其中 $u$ 是子树根节点， $siz$ 是子树大小 )

这样子用线段树维护子树问题实际上就相当于将原树上的问题利用 $Dfn$ 序是连续的，就转化到了区间上。

于是维护的时候只维护 $Dfn$ 序对应的值就行了。

这时候就相当于我们在做区间统计了。

那么考虑怎么统计区间内出现的颜色种数（分块是行不通的，复杂度过高）。

我们发现这个是具有区间可加性的，我们可以采用统计区间内每种颜色出现的次数的方式来统计区间内出现的颜色种数。

于是我们可以通过用线段树维护 $60$ 个区间和的形式来做，时间复杂度是 O( $m log n * 60$ ) 的，理论上是能过的，因为时间限制有 3 秒，但是实际上是过不了的，因为空间限制把你卡死了.......

但是我们并不气馁，因为我们想到，实际上只需要统计一个区间内是否出现过某种颜色就行了。

如果某种颜色出现了我们就在对应的数组位置上将其赋值为1即可，最后的统计出来的区间多少个对应的数组位为 $1$ 就是询问的答案。

对于答案的合并运用或运算，因为实际上只要两个区间内有一个是 $1$ 就行了。

那么我们可以使用黑科技 :

$bitset$

这个东西能够帮助你卡空间/卡常

时间复杂度相对于呆板的使用普通的 $bool$ 数组除以了大概 $32$ ，在这道题甚至它跑得跟状态压缩是差不多的，其时间复杂度为:
O( $m log n * \frac{60}{w}$ ) ( $w$ 就是提到的可以除以的常数)，跑得飞快的：

图片说明

其使用方式与数组差不多，但是它只能存储 $0/1$ 两种数，同时它能支持两个 $bitset$ 长度相等的数组 之间的按位与，按位或，按位异或等位运算操作。

也就是说，假设有两个 $bitset$ 长度相等（必须长度相等）数组分别为 $A[60],B[60]$ ，你是可以直接书写：

$A |= B$ 的，相当于是加长版的二进制数。

$bitset$ 在本题中你还需要掌握其两个函数：

$A.reset()$ 表示清空一个 $bitset$ 数组 $A$ , $A.count()$ 表示统计 $bitset$ 数组 $A$ 中有多少个 $1$

(其实不会也没有关系，只是写起来麻烦，不好看而已)

详细内容可以看:OIwiki

有详细的介绍。

当你都想到了用 $bitset$ 了，难道你还想不到使用位运算来进行状态压缩吗？

因为 $C_i$ 小于等于 $60$ ，所以我们可以用一个 $60$ 位的二进制数来记录每种颜色出现的情况，假设某种颜色出现了就把那一位二进制位变成 $1$ , 考虑到 $60$ 位的二进制数是不超过 $long long$ 的范围的，于是我们可以用一个 $long long$ 类型的数来记录区间内出现颜色的情况。

合并区间统计的结果的时候就将两个二进制数按位或起来（因为只要某一个区间出现了，那么它在这个整个区间就出现了，满足按位或运算），对于修改一种颜色实际上我们只需要在对应的二进制位上进行修改即可。查询的答案就是区间统计的结果中对应二进制数的 $1$ 的个数，这个是不难想的。

时间复杂度 O( $mlogn$ )

Code

// Problem: CF620E New Year Tree
// Memory Limit: 250 MB
// Time Limit: 3000 ms

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4e5 + 50;
long long Ans = 0ll;
int n,Q,tot = 0,now = 0;
int start[MAXN];
int data[MAXN],siz[MAXN],son[MAXN],deep[MAXN],fa[MAXN];
int dfn[MAXN],dfn_id[MAXN];

struct SegmentTree {
    int l,r;
    long long B,F;
} T[MAXN * 4];

struct Edge {
    int next,to;
    void add(int from,int To) {next = start[from], to = To , start[from] = tot;}
} edge[MAXN * 2];

inline int read() {
    int x = 0 , flag = 1;
    char ch = getchar();
    for( ; ch > '9' || ch < '0' ; ch = getchar());
    for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
    return x * flag;
}

int DFS1(int x,int from) {//求DFS序，从树链剖分那里偷了个板子改了一下
    siz[x] = 1, son[x] = 0;
    deep[x] = deep[from] + 1 , fa[x] = from;
    dfn[x] = ++now , dfn_id[now] = x;
    for(int i = start[x] ; i ; i = edge[i].next) {
        int to = edge[i].to;
        if(to == from) continue;
        int v = DFS1(to , x);
        if(siz[v] > siz[son[x]]) son[x] = to;
        siz[x] += v;
    }
    return siz[x];
}

void build(int x,int l,int r) {
    T[x].l = l , T[x].r = r;
    T[x].B = 0ll, T[x].F = 0ll;
    if(l == r) {
        T[x].B = 1ll << data[dfn_id[l]];//dfn_id表示的是Dfn序对应的原数组的下标
        return ;
    }
    int mid = (l + r) >> 1;
    build(x << 1 , l , mid);
    build(x << 1 | 1 , mid + 1 , r);
    T[x].B = T[x << 1].B | T[x << 1 | 1].B;//用或运算连接
    return ;
}

void update(int x,long long k) {
    T[x].B = T[x].F = k;
    return ;
}

void pushdown(int x) {//下传标记
    if(T[x].F == 0ll) return ;
    update(x << 1 | 1 , T[x].F);//这个F就是被覆盖的标记
    update(x << 1 , T[x].F);
    T[x].F = 0ll;
    return ;
}

void change(int x,int l,int r,long long k) {//注意这里一定要用long long 哦
    if(T[x].l >= l && T[x].r <= r) {
        update(x, k);
        return ;
    }
    pushdown(x);
    int mid = (T[x].l + T[x].r) >> 1;
    if(l <= mid) change(x << 1 , l , r , k);
    if(r  > mid) change(x << 1 | 1 , l , r , k);
    T[x].B = T[x << 1].B | T[x << 1 | 1].B;
    return ;
}

void GetAns(int x,int l,int r) {// 统计答案，对于涉及到的区间用 "|" 运算来取得答案
    if(T[x].l >= l && T[x].r <= r) {
        Ans |= T[x].B;
        return ;
    }
    pushdown(x);
    int mid = (T[x].l + T[x].r) >> 1;
    if(l <= mid) GetAns(x << 1 , l , r );
    if(r >  mid) GetAns(x << 1 | 1 , l , r);
    return ;
}

int main() {
    n = read() , Q = read();
    for(int i = 1 ; i <= n ; i ++) data[i] = read();
    for(int i = 1 ; i <= n - 1 ; i ++) {
        int u = read() , v = read();
        edge[++tot].add(u,v);
        edge[++tot].add(v,u);
    }
    DFS1(1,0);//预处理
    build(1 , 1 , n);
    while(Q --) {
        int op = read() , u = read() , c;
        if(op == 1) c = read();
        if(op == 1) change(1 , dfn[u] , dfn[u] + siz[u] - 1 , 1ll << (long long)c);//子树修改
        else {
            Ans = 0ll;//每次询问都要清空。
            GetAns(1 , dfn[u] , dfn[u] + siz[u] - 1);
            int cnt = 0;
            while(Ans) { //统计答案，有多少个1就表示有多少个颜色
                if(Ans & 1ll) cnt ++;
                Ans >>= 1ll;
            }
            printf("%d\n",cnt);
        }
    }
    return 0;
}

Code2 （bitset）

方便排版就发在这里了:代码

总结

算是一道比较好的线段树进阶题 $and$ 状态压缩 / 位运算入门题。

或者你可以用 $bitset$ 过这一题， $bitset$ 也是一种常用而且好用的 $STL$

CF620E 【New Year Tree】 题解