poj2777Count Color——线段树+状压-白红宇的个人博客

poj2777Count Color——线段树+状压

发布日期：2021-08-19 19:59:31 浏览次数：6 分类：技术文章

本文共 1601 字，大约阅读时间需要 5 分钟。

题目：

状压每个颜色的选择情况，取答案时 | 一番；

注意题目中的区间端点可能大小相反，在读入时换一下位置；

注意pushdown()中要lazy标签不为0才进行更新。

代码如下：

#include
     
      #include
      
       using namespace std;int const N=2000005;int t[N],lazy[N],len,tt,o;char dc;void pushdown(int x){    if(lazy[x])//!    {        lazy[x*2]=lazy[x];        lazy[x*2+1]=lazy[x];        t[x*2]=lazy[x];        t[x*2+1]=lazy[x];        lazy[x]=0;    }}void pushup(int x){    t[x]=(t[x*2]|t[x*2+1]);}void build(int l,int r,int x){    t[x]=1;    if(l==r)return;    int mid=(l+r)/2;    build(l,mid,x*2);    build(mid+1,r,x*2+1);}void update(int l,int r,int ll,int rr,int s,int x){    if(l>=ll&&r<=rr)    {        t[x]=s;        lazy[x]=s;        return;    }    pushdown(x);    int mid=(l+r)/2;    if(mid>=ll)update(l,mid,ll,rr,s,x*2);    if(mid
       
        =ll&&r<=rr)        return t[x];    pushdown(x);    int mid=(l+r)/2;    if(mid>=ll)ans|=query(l,mid,ll,rr,x*2);    if(mid
        
         >dc;    //        printf("(%c)\n",dc);            if(dc=='C')            {                int x,y,z;                scanf("%d%d%d",&x,&y,&z);                if(x>y)swap(x,y);                z=(1<<(z-1));                update(1,len,x,y,z,1);            }            if(dc=='P')            {                int x,y;                scanf("%d%d",&x,&y);                if(x>y)swap(x,y);                int k=query(1,len,x,y,1);                int ans=0;                for(int i=1;i<=tt;i++)                    if(k&(1<<(i-1)))ans++;                printf("%d\n",ans);            }        }    }    return 0;}

转载于:https://www.cnblogs.com/Zinn/p/8721329.html

转载地址：https://blog.csdn.net/weixin_30951743/article/details/95823119 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：bzoj 2259 [Oibh] 新型计算机 —— 最短路

下一篇：data 原生用法 jquery 用法

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章