随笔 - 97, 文章 - 22, 评论 - 81, 引用 - 0
数据加载中……

PKU 2777 Count Color

题目链接:http://poj.org/problem?id=2777
/*
题意:
    给定一个长度为N(N <= 100000)的数列Si,紧接着Q(Q <= 100000)条操作,操作
形式有两种:
1. "C A B C" 将A到B的数都染成C这种颜色。 
2. "P A B" 输出A和B之间不同颜色的数目。


解法:
线段树(染色问题)

思路:
    一看到数据量就可以首先确定是线段树了,经典的区间染色问题,涉及到区间的
更新和询问,和pku 3468 类似,巧妙运用lazy思想。就是每次更新区间段的时候延迟
更新,只是在完全覆盖的区间打上一个lazy标记。这题的询问是求区间段中不同颜色的
数量,因为颜色数不多只有30种,可以巧妙运用二进制位运算,用一个int就可以表示
当前区间段的颜色情况。比如1001表示有两种颜色,如果左子树的当前颜色情况是101
,而右子树的颜色情况是011,那么父亲的颜色情况就是两者的位或,这样就可以避免
掉重复的情况。
    再来谈谈lazy思想。做了这么多的线段树,应该总结一下,lazy是一个很经典的思
想。所谓lazy,就是懒惰,每次不想做太多,只要插入的区间完全覆盖了当前结点所管
理的区间就不再往下做了,在当前结点上打上一个lazy标记,然后直接返回。下次如果
遇到当前结点有lazy标记的话,直接传递给两个儿子,自己的标记清空。这样做肯定是
正确的。我们以染色为例,可以这样想,如果当前结点和它的子孙都有lazy标记的话,
必定是子孙的先标记,因为如果是自己先标记,那么在访问子孙的时候,必定会将自己
的标记下传给儿子,而自己的标记必定会清空,那么lazy标记也就不存在了。所以可以
肯定,当前的lazy标记必定覆盖了子孙的,所以直接下传即可,不需要做任何判断。当
然,这是染色问题,是直接赋值的,如果像pku 3468那样,每次是区间加和,则传递标
记的时候不能简单的赋值,必须累加,这是显而易见的。
*/
/*
lazy思想
    染色模型
        适合颜色数目较少(64以内)的区间染色问题。
        具体操作:
            1、对某个连续区间进行染色。
            2、询问某个连续区间的颜色情况(种类、数目等等)。
        适用题型:
            poj 2777 Count Color
            hdu 5023 A Corrupt Mayor's Performance Art
        结点存储
            颜色值的位或colorBit:每个颜色用2的幂来表示,颜色值表示分别为1、2、4、8,该区间有哪些颜色就可以用他们的或来表示
            延迟标记lazy:该段区间完全被染色成了lazy这种颜色,这里的lazy要么是2的幂,要么是0

        接口说明
            giveLazyToSon      传递延迟标记给两个子结点(调用子结点的updateByValue,并且lazy重置)
            updateByValue      通过某个颜色值更新当前结点信息(更新colorBit、lazy)
            updateFromSon      通过两个子结点更新当前结点信息(更新colorBit)
            mergeQuery         询问时用于对分割后的子结点进行合并用,不同情况实现不同

        调用说明
            建树:              调用静态函数   treeNode::segtree_build(1, 1, n);
            插入([x, y], val): 调用静态函数   treeNode::segtree_insert(1, 1, n, x, y, val);
            询问([x, y]):       调用静态函数   treeNode::segtree_query(1, 1, n, x, y, ans);

*/ 
#include <iostream>

using namespace std;

#define MAXN 131072
typedef int ValueType;


// 返回[l, r]和[x, y]两条线段是否相交
bool is_intersect(int l, int r, int x, int y) {
      return !(r < x || l > y);
}
// 返回[x, y]是否完全包含[l, r]
bool is_contain(int l, int r, int x, int y) {
      return x <= l && r <= y;
}

struct treeNode {
    ValueType lazy;
    ValueType colorBit;
      int pid;
      int len;

    treeNode() {
        reset(-1, 0);
    }
      void reset(int p, int _len) {
        pid = p;
        colorBit = 0;
        lazy = 0;
        len = _len;
    }
    int lson() { return pid << 1; }
    int rson() { return pid<<1|1; }

    void updateByValue(ValueType _val);
    void giveLazyToSon();
    void updateFromSon();

    // 询问的时候将结点合并后计入答案
    void mergeQuery(int p);

    // 建树 
    static void segtree_build(int p, int l, int r);
    // 插入线段[x, y]到[l, r]
    static void segtree_insert(int p, int l, int r, int x, int y, ValueType val);
    // 区间询问[x, y]上的信息
    static void segtree_query(int p, int l, int r, int x, int y, treeNode& ans);
};

/* 全局变量 
    nodes[MAXN*2] 存储所有静态线段树结点(动态开内存太费时间)
    totalNodes    存储结点数目
*/
treeNode nodes[MAXN*2];

void treeNode::updateByValue(ValueType _val) {
    lazy = _val;
    colorBit = _val;
}

void treeNode::giveLazyToSon() {
      if(lazy) {
        nodes[ lson() ].updateByValue(lazy);
        nodes[ rson() ].updateByValue(lazy);    
        lazy = 0;        
    }
}

void treeNode::updateFromSon() {
    colorBit = nodes[ lson() ].colorBit | nodes[ rson() ].colorBit;
}

void treeNode::mergeQuery(int p) {
    colorBit |= nodes[p].colorBit;
}

void treeNode::segtree_build(int p, int l, int r) {
    // 创建线段树结点的时候只需要知道该线段树结点管辖区间的长度,区间端点不用存,可以在递归的时候作为函数传参
    nodes[p].reset(p, r-l+1);
      if (l < r) {
            int mid = (l + r) >> 1;
            // 递归创建左右儿子结点
        treeNode::segtree_build(p<<1, l, mid);
        treeNode::segtree_build(p<<1|1, mid+1, r);
        nodes[p].updateFromSon();
    }
}

void treeNode::segtree_insert(int p, int l, int r, int x, int y, ValueType val) {
      if( !is_intersect(l, r, x, y) ) {
            return ;
      }
      if( is_contain(l, r, x, y) ) {
        nodes[p].updateByValue(val);
            return ;
    } 
    nodes[p].giveLazyToSon();
      int mid = (l + r) >> 1; 
    treeNode::segtree_insert(p<<1, l, mid, x, y, val);
    treeNode::segtree_insert(p<<1|1, mid+1, r, x, y, val);
    nodes[p].updateFromSon();
}

void treeNode::segtree_query(int p, int l, int r, int x, int y, treeNode& ans) {
      if( !is_intersect(l, r, x, y) ) {
            return ;
      }
      if( is_contain(l, r, x, y) ) {
            ans.mergeQuery(p);
            return;
    }
    nodes[p].giveLazyToSon();
      int mid = (l + r) >> 1; 
    treeNode::segtree_query(p<<1, l, mid, x, y, ans);
    treeNode::segtree_query(p<<1|1, mid+1, r, x, y, ans);
    nodes[p].updateFromSon();


int n, t, o;

int main() {
    int i;
    while( scanf("%d %d %d", &n, &t, &o) != EOF ) {
            treeNode::segtree_build(1, 1, n);
            for(i = 1; i <= n; i++) {
            treeNode::segtree_insert(1, 1, n, i, i, 1<<0);
            }
            while(o--) {
                  char str[10];
                  int x, y, z;

                  scanf("%s", str);
                  if(str[0] == 'C') {
                           scanf("%d %d %d", &x, &y, &z);
                           if(x > y) swap(x, y);
                           treeNode::segtree_insert(1, 1, n, x, y, 1<<(z-1) );
                  }else {
                           scanf("%d %d", &x, &y);
                           if(x > y) swap(x, y);
                 treeNode ans;
                 treeNode::segtree_query(1, 1, n, x, y, ans);
                 z = 0;
                          for(i = 0; i < t; i++) {
                                if( (1<<i) & ans.colorBit ) {
                        z ++;
                    }
                }
                printf("%d\n", z);
            }
        }
    }
    return 0;
}

/*
2 2 4
C 1 1 2
P 1 2
C 2 2 2
P 1 2
*/

posted on 2011-03-31 19:49 英雄哪里出来 阅读(1616) 评论(0)  编辑 收藏 引用 所属分类: 线段树


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理