title: poj-2777线段树刷题
date: 2018-10-16 20:01:07
tags:
刷题
categories:
ACM-线段树
概述这道题是一道线段树的染色问题,,,,
做了几道染色的问题，，好像渐渐的熟悉的染色问题的大概的解体思路，，，不再像刚开始做的时候那样一脸懵逼，，，只能去翻博客去看别人的思路，，，好歹这次没有看别人博客自己写出来，，，（除了一些细节没考虑到wa的一发，，，，逃
分析与思路 题面大概的意思就是给一个区间1~n，，，然后最多有30种颜色，，，q次操作对[l,r]这个区间染色，，，中间有一些询问区间[l , r]内一共有几种颜色，，，
分析首先考虑线段树所维护的东西，，，染色问题大多是维护每个区间的颜色，，，对于这道题就是维护该区间的颜色的种类，，，然后对于每两个子区间都要向上合并颜色的种类，，，，相同的忽略一边的不同的就加一，，，求出父区间的种类数，，，，也就是更新操作，，，询问呢就是再询问的区间[L , R]里的话直接返沪这个区间的种类数，，，跨区间的递归继续向下查找，，，
然后考虑颜色，，，最多一共有30种，，，如果每个区间都用一个30长的数组col[30]去存放每种颜色的种类，，col[i] == 1表示这个区间有第i种颜色反之没有的话，，，空间消耗较大，，，而且相关的操作也不好表达，，，因为每个区间的每种颜色只有两种情况，，，有或没有，，，所以选择状态压缩来实现比较好，，，这里我想到前段时间看到的一个很好的状压stl--bitset，，，优点有很多，，，比如说：他就像bool数组一样但是每一位只占1bit，，，而且有很多成员函数很方便，，，具体的食用方法戳这里
另一个需要注意的是，，，线段树要选择lazy的，，，还有一些细节：
区间的合并需要或操作，，，包括更新和询问
初始时所有区间都为1
当整个区间都染色时是将该区间的node[rt].col改为c,,,而不是或
还有一个最坑人的，，，，题目不保证l <= r，，，（poj上的题都这样的吗，，噗噗噗噗
这次又写成node结构体实现的了，，，还是因为这个理解起来很容易，，，，
但是缺点是占用的空间比较大，，，，
下次再写这道题的时候要换用另一种裸的了QAQ
#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <bitset> using namespace std; #define lson rt<<1,l,mid #define rson rt<<1|1,mid+1,r #define aaa cout << node[rt].col << endl; const int maxn = 1e5 + 10; struct node { int l; int r; int laz; bitset<30> col; //bitset,,表示该区间的颜色的种类 }node[maxn << 2]; void build(int rt , int l , int r) { node[rt].l = l; node[rt].r = r; node[rt].laz = 0; node[rt].col = 0; if(node[rt].l == node[rt].r) { node[rt].col = 1; //初始化为1 return; } int mid = (node[rt].l + node[rt].r) >> 1; build(lson); build(rson); node[rt].col = node[rt << 1].col | node[rt << 1 | 1].col; //记得更新，，用或 return; } void pushdown(int rt) { if(node[rt].laz) { bitset<30> t; t.set(node[rt].laz - 1); //标记为laz那一个颜色 node[rt << 1].col = t; //不是或操作 node[rt << 1 | 1].col = t; node[rt << 1].laz = node[rt].laz; node[rt << 1 | 1].laz = node[rt].laz; node[rt].laz = 0; } } void update(int rt , int L , int R , int c) { if(L <= node[rt].l && node[rt].r <= R) { bitset<30> t; t.set(c - 1); node[rt].col = t; //同上 node[rt].laz = c; return; } pushdown(rt); int mid = (node[rt].l + node[rt].r) >> 1; if(L <= mid) update(rt << 1 , L , R , c); if(R > mid) update(rt << 1 | 1 , L , R , c); node[rt].col = node[rt << 1].col | node[rt << 1 | 1].col; return; } bitset<30> query(int rt , int L , int R) { //对每两个子区间合并，，，同样是或操作，，，所以函数返回值类型为bitset<30> //最后的答案为 返回值.count() if(L <= node[rt].l && node[rt].r <= R) { return node[rt].col; } pushdown(rt); int mid = (node[rt].l + node[rt].r) >> 1; bitset<30> ans (0); if(L <= mid) ans |= query(rt << 1 , L , R); //用或合并 if(R > mid) ans |= query(rt << 1 | 1 , L , R); //cout << ans << endl; return ans; } int main() { int n , t , m; while(scanf("%d%d%d" , &n , &t , &m) != EOF) { build(1 , 1 , n); while(m--) { char q; scanf(" %c" , &q); if(q == 'C') { int l , r , c; scanf("%d%d%d", &l , &r , &c); if(l > r) swap(l , r); //巨坑！！！！ update(1 , l , r , c); } else { int l , r; scanf("%d%d" , &l , &r); if(l > r) swap(l , r); printf("%d\n" , query(1 , l , r).count()); } } } } 感想算了不说了QAQ