Menu
Article ACM

POJ 2777 Count Color 附带线段树小结

NodeKey

NodeKey

• 4 min read

POJ 2777 题解

好久没这么兴奋过了
poj2777 这绝对是 是道线段树的好题 至少对我来说
一开始看这题的时候 看了一下数据范围就知道了 可以用位运算 进行状态压缩
我想要自己做 对 完全不看题解 结果问题就慢慢显现出来了
尤其是我对pushdown操作的理解完全不够 最后还是自己动笔好好画了一下模拟几遍才恍然大悟 我真是太辣鸡了

先附上 代码和注释 最后写上我对线段树基础操作的理解（包括以前写的一些 觉得太基础了就没卸载博客上 今天就在这里汇总一下

AC Code（G++好像就超了 C++能过

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
#define root tree[id]
#define lson tree[id<<1]
#define rson tree[id<<1|1]

using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=100005;
int st,en,n,m,qnum;
long long change,col;//col是最后query的最终颜色汇总   最后对其位操作计算颜色数量即可
struct segtree
{
    int le,ri;
    long long color,change_color;//这段区间上的颜色总和   延迟更新标记
} tree[maxn<<2];

inline void pushup(int id)
{
    root.color=lson.color|rson.color;//颜色汇总
}

inline void pushdown(int id)
{
    if(root.change_color!=0&&root.le!=root.ri)
    {
        long long cc=root.change_color;
        lson.change_color=rson.change_color=lson.color=rson.color=cc;
        root.change_color=0;
    }
}

void build_tree(int id,int le,int ri)
{
    root.le=le,root.ri=ri,root.change_color=0;
    root.colo=1;
    if(le==ri) return;
    int mid=(le+ri)/2;
    build_tree(id<<1,le,mid);
    build_tree(id<<1|1,mid+1,ri);
}

void update(int id)
{
    int le=root.le,ri=root.ri;
    if(st<=le&&ri<=en)
    {
        root.color=root.change_color=change;
        return ;
    }
    pushdown(id);
    int mid=(le+ri)/2;
    if(st<=mid) update(id<<1);
    if(en>mid) update(id<<1|1);
    pushup(id);
}

void query(int id)
{
    int le=root.le,ri=root.ri;
    if(st<=le&&ri<=en)
    {
        col=col|root.color;
        return ;
    }
    pushdown(id);//牛逼啊！！！！真的牛逼！！！！pushdown这个位置  沃夫
    int mid=(le+ri)/2;
    if(st<=mid) query(id<<1);
    if(en>mid) query(id<<1|1);
}

int main()
{
    while(scanf("%d%d%d",&n,&m,&qnum)!=EOF)
    {
        char op[2];
        build_tree(1,1,n);
        while(qnum--)
        {
            scanf("%s",op);
            if(op[0]=='C')
            {
                scanf("%d%d%I64d",&st,&en,&change);
                if(st>en) swap(st,en);
                change=1<<(change-1);
                update(1);
            }
            else
            {
                scanf("%d%d",&st,&en);
                if(st>en) swap(st,en);
                int ans=0;
                col=0;//col初始化
                query(1);
                for(int i=0; i<m; i++)
                    if((col>>i)&1) ans++;
                printf("%d\n",ans);
            }
        }
    }
    return 0;
}

线段树小结

下面是对线段树的理解（从小白开始的历程 不喜勿喷…………

线段树的精髓 就在于 它永远都是从根节点出发

1.关于query以及update时判断的标志 st<=le&&ri<=en 的理解
假如区间为 1-7 要求求出 2-6的值
并不是说 什么2-3 2-4 3-5 3-6 什么乱七八糟的都可以满足条件
首先由于线段树的性质 如果该节点 在区间内部 那么只要我一个return 该节点的所有叶子节点就不会再出现，更不用说是该节点内的数字
也就是说 假如我 1-4 满足条件 那么1-2 3-4都不会再出现 1,2,3,4也不会再次被访问到
所以 如此继续向下查询 线段式地返回 最后就是所要求的区间值

2.关于pushdown与pushup的理解
就如字面意思 假如 一个节点更新 那么它的叶子节点和父亲节点都需要更新
如果每次都这么向下向上更新 百分之8000要超时 效率低下
所以我们先暂时向下更新 一直向下更新 到最后再一起向上更新 如此就能实现所有更新

3.关于pushdown和lazy标记的详解

现在才知道为什么总是说线段树对递归的要求稍微高了一些

以此题为例 在update时 在此区间更新后 直接return 这个区间和他的子区间都不会被再次访问

并不是说不会更新 而是他觉得暂时没必要

当query操作时 如果你不会访问他的子区间 他就不会更新

eg 总区间是 1-12 你更新 4-5区间 查询 5-6区间

当你访问到4-5区间时 发现没有符合条件 他才会向下更新 4和5节点

这样说来可能还有优化的余地 就是当切仅当你要查询的区间与 你当前访问的区间有交集的时候 才向下更新 也不失为一个方法 有兴趣的可以尝试一下

啊！ 果然 算法的优化是无止尽的！！

Share