关键词：
title: poj-2777线段树刷题
date: 2018-10-16 20:01:07
tags:
- acm
- 刷题
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
" , query(1 , l , r).count());
感想
算了不说了QAQ
(end)
poj2777countcolor线段树(代码片段)
CountColorTimeLimit:1000MSMemoryLimit:65536KTotalSubmissions:62027Accepted:18419DescriptionChosenProblemSolvingandProgramdesignasanoptionalcourse,youarerequiredtosolveallkindsofproblems.Here,wegetanew 查看详情
poj2777（线段树）(代码片段)
...[a,b]的不同颜色数），输出每次询问的值。思路：典型的线段树的题目。用线段树实现表示一段区间的颜色值。线段树结点的属性包括l（区间左端点），r（区间右端点），value 查看详情
poj-2777——countcolor（懒标记线段树二进制）(代码片段)
CountColorTimeLimit: 1000MS MemoryLimit: 65536KTotalSubmissions: 53639 Accepted: 16153DescriptionChosenProblemSolvingandProgramdesignasanoptionalcourse,youarerequiredtosolveallkindsofproblems.Here,wegetanewproblem. ThereisaverylongboardwithlengthLcentimeter,Lisapos... 查看详情
poj2777线段树
...颜色最多有30种，所以对这30中颜色状态压缩一下，放在线段树里面，这样就容易更新了最后只要计算一下query返回值得数有多少个1就行了代码：31intL,T,O;32intTree[MAXN<<2];33intLa 查看详情
poj2777-countcolor线段树
题目传送门：http://poj.org/problem?id=2777 CountColorTimeLimit: 1000MS MemoryLimit: 65536KTotalSubmissions: 45259 Accepted: 13703DescriptionChosenProblemSolvingandProgramd 查看详情
poj2777countcolor线段树
DescriptionChosenProblemSolvingandProgramdesignasanoptionalcourse,youarerequiredtosolveallkindsofproblems.Here,wegetanewproblem.ThereisaverylongboardwithlengthLcentimeter,Lisapositiveinteger,sowecanev 查看详情
poj2777
...这么菜的我，还是搞搞专题吧。一道比较裸也比较基础的线段树的题目。题意：就是有一段木头，可以对这个木头进行两种操作，一是进行涂色，而是进行查询，如果一个木头之前涂过色，那么之后涂色的话，会对之前的进行覆... 查看详情
poj2777countcolor(代码片段)
【POJ2777】CountColorDescriptionChosenProblemSolvingandProgramdesignasanoptionalcourse,youarerequiredtosolveallkindsofproblems.Here,wegetanewproblem. ThereisaverylongboardwithlengthLcentimeter,Lisa 查看详情
poj2777countcolor(代码片段)
鏍囩锛?ahref='http://www.mamicode.com/so/1/%e5%a4%9a%e9%87%8d'title='澶氶噸'>澶氶噸 鍘婚噸 while 鍖洪棿瑕嗙洊 cstring poj2777 & 查看详情
[日常摸鱼][poj2777]countcolor-线段树
...状数组直接过掉了…这题颜色范围这么小的范围直接想到线段树了吧，直接把一个区间的颜色二进制按位压缩成一个状态，维护区间或题面还特地说了可能$a>b$…然而我没看到#include< 查看详情
poj2777
调了一天，囧！第一次写lazy更新线段树，结果在查询和add时没有考虑到我用了区间lazy更新。后面在增加lazy更新处理代码时，将bitmap作为color传进去。导致add函数逻辑不正确。本题还有一个坑，要考虑输入参数的大小。L参数可能... 查看详情
二叉树刷题(代码片段)
剑指Offer55-I.二叉树的深度输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。例如：给定二叉树[3,9,20,null,null,15,7]&#... 查看详情
poj2777(代码片段)
#include<bits/stdc++.h>usingnamespacestd;#definelllonglongllsum[500000];lln,p,ans;llql,qr,v;voidmk(llo,lll,llr)if(ql<=l&&qr>=r)sum[o]=1<<(v-1);elsellm=l+(r-l)/2;if(m>=ql 查看详情
poj2777解题报告
...色。颜色数小于等于30。大致思路： 首先很容易发现线段树可以解决问题，不过怎么储存颜色呢？我们发现颜色总数很少，于是可以为2进制位来表示颜色，问题就可以很好地解决了。代码：#include<iostream> 查看详情
leetcode之并查集+记忆化搜索+回溯+最小生成树刷题总结1(代码片段)
leetcode之并查集+记忆化搜索+回溯+最小生成树刷题总结11-连接所有点的最小费用题目连接：题目连接戳这里！！！思路:cruskal+并查集根据题意，我们得到了一张n个节点的完全图，任意两点之间... 查看详情
二叉树刷题
...的PDF进行学习，十分不错，给大家安利一波二叉树刷题二叉树的前中后遍历二叉树的前中后遍历可以使用递归方法和迭代法进行遍历在递归中，最大的体会就是程序由于递归的作用不断的向下执行，通过压栈把当... 查看详情
poj2777-题解
五、源代码 #pragmacomment(linker,"/STACK:1024000000,1024000000")#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#include<cmath>#include<cctype>#incl 查看详情
二叉树刷题专练(代码片段)
文章目录前言一、二叉树的最小深度1.题目介绍2.思路3.代码二、完全二叉树的节点个数1.题目介绍2.思路3.代码前言继承前面的写作思路，此篇文章继续二叉树的oj题一、二叉树的最小深度1.题目介绍题目在力扣二叉树的最小深... 查看详情