CF620E New Year Tree (线段树+状压)

题目链接
题目大意:
图片说明
树初始每个节点也有颜***r>总体思路:
题目是在每一棵子树整体做一个修改,所以我们就没有必要用树剖来写了。直接通过一边DFS来的到整棵树DFS序列,于是我们就将问题在一棵子树上进行操作转化为在一段连续的区间经行操作,这时候我们就可以用线段树来维护区间信息了。
我们可以注意到所有颜色的种类是有60种,所有我们可以用状态压缩来表示一棵树不同颜色的状态。每一中颜色存在为1,对应状态long long的一位。区间合并我们用|运算就可以了,注意每次更新是将前一次的颜色覆盖掉,所以lazy和sum表示也会直接被覆盖掉。
总之看见状态数比较小就可以考虑用状压来表示状态。
代码实现:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m;
ll x,y;
ll inx;
ll idx;
ll ch,c;
ll l,r;
ll a[400005];
ll h[400005],e[400005*2],ne[400005*2];
ll s[400005],dfsxu[400005],ni[400005];
struct ty{
    ll l,r;
    ll sum;
    ll lazy;
    ty():l(0),r(0),sum(0),lazy(0){ }
};
ty tr[400005*4];
void add(ll x,ll y){
    ne[inx]=h[x];e[inx]=y;h[x]=inx++;
    return ;
}
void dfs(ll u,ll fa){
    s[u]=++idx;
    dfsxu[idx]=u;
    for(ll i=h[u];i!=-1;i=ne[i]){
        int to=e[i];
        if(to==fa) continue;
        dfs(to,u);
    }
    ni[u]=idx;
    return ;
}
void pushup(ll u){
    tr[u].sum=tr[u<<1].sum|tr[u<<1|1].sum;
    return ;
}
void build(ll u,ll l,ll r){
    tr[u].l=l; tr[u].r=r;
    if(l==r){
        tr[u].sum=1ll<<a[dfsxu[l]];
        tr[u].lazy=0;
        return ;
    }
    ll mind=(l+r)>>1;
    build(u<<1,l,mind);
    build(u<<1|1,mind+1,r);
    pushup(u);
    return ;
}
void pushdown(ll u){
    if(tr[u].lazy){
        tr[u<<1].sum=tr[u].lazy;
//如果每一更新不会覆盖掉上一次的状态,那tr[u<<1].sum|=tr[u].lazy;lazy标记同理
        tr[u<<1|1].sum=tr[u].lazy;
        tr[u<<1].lazy=tr[u].lazy;
        tr[u<<1|1].lazy=tr[u].lazy;
        tr[u].lazy=0;
    }
    return ;
}
void modify(ll u,ll l,ll r,ll da){
    if(tr[u].l>=l&&tr[u].r<=r){
        tr[u].sum=1ll<<da;
        tr[u].lazy=1ll<<da;
        return ;
    }
    pushdown(u);
    ll mind=(tr[u].l+tr[u].r)>>1;
    if(l<=mind) modify(u<<1,l,r,da);
    if(r>mind) modify(u<<1|1,l,r,da);
    pushup(u);
    return ;
}
ll query(ll u,ll l,ll r){
    if(tr[u].l>=l&&tr[u].r<=r){
        return tr[u].sum;
    }
    pushdown(u);
    ll ans=0;
    ll mind=(tr[u].l+tr[u].r)>>1;
    if(l<=mind) ans|=query(u<<1,l,r);
    if(r>mind) ans|=query(u<<1|1,l,r);
    return ans;
}
ll lowbit(ll i){
    return i&-i;
}
int main(){
    memset(h,-1,sizeof(h));
    scanf(" %lld %lld",&n,&m);
    for(ll i=1;i<=n;i++) scanf(" %lld",&a[i]);
    for(ll i=1;i<n;i++){
        scanf(" %lld %lld",&x,&y);
        add(x,y); add(y,x);
    }
    dfs(1,-1);
    build(1,1,n);
    for(ll i=1;i<=m;i++){
        scanf(" %lld",&ch);
        if(ch==1){
            scanf(" %d %d",&x,&c);
            l=s[x]; r=ni[x];
            modify(1,l,r,c);
        }
        else{
            scanf(" %d",&x);
            l=s[x]; r=ni[x];
            ll temp=query(1,l,r);
            ll cnt=0;
            while(temp>0){
                cnt++;
                temp-=lowbit(temp);
            }
            printf("%lld\n",cnt);
        }
    }
    return 0;
}
全部评论

相关推荐

找个工作&nbsp;学历是要卡的&nbsp;要求是高的&nbsp;技能不足是真的&nbsp;实习经验是0的&nbsp;简历无处可写是事实的&nbsp;钱不好赚是真的&nbsp;想躺平又不敢躺&nbsp;也不甘心躺&nbsp;怕自己的灵感和才华被掩埋甚至从未被自己发现&nbsp;又质疑自己是否真正有才华
码农索隆:你现在啊,你心里都明白咋回事,但是你没办法改变现状,一想到未来,你又没有信心狠下心来在当下努力。 得走出这种状态,不能一直困在那里面,哪不行就去提升哪,你一动不动那指定改变不了未来,动起来,积少成多才能越来越好
点赞 评论 收藏
分享
头顶尖尖的程序员:我是26届的不太懂,25届不应该是找的正式工作吗?为什么还在找实习?大四还实习的话是为了能转正的的岗位吗
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-04 14:35
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务