POJ 2777-题解
一、题意
给你一排N个格子,M种颜色,P个操作。有两种操作:(1)C A B D:把[A, B]区间内的所有格子涂成颜色D。(2)P A B:输出[A, B]区间内的颜色的种类数。注意,初始颜色为1。
二、思路
对于这种区间修改,区间查询种类数的,很明显,线段树是个强有力的工具。但是,我们最常用的线段树是用来求区间最值之类的东西,因此我们需要修改线段树节点数值的意义。在这题中,我们注意到,颜色最多只有30种,所以,应该不难想到位存储。线段树的每一个节点存储它所代表的区间内的颜色,如果该区间有一种颜色c,那么,这个节点的数值二进制表示的右数第c位就设置为1,即当前节点的数值 |= 1 << c。区间查询时,只需要查询给定区间内的位存储数值的二进制表示中1的个数即可。接下来进入详细的讲解。
1、区间修改:给定要修改的区间[A, B]后,和往常使用的线段树一样,分割区间,然后对子区间做处理。假设给定要修改的区间为[A, B],颜色为ct,当当前节点所表示的区间完全含于区间[A, B]时,修改该节点的数值为1 << ct。否则,分割当前节点所表示的区间,递归的对子区间做相同的处理。对子区间处理完成之后,需要合并两个子节点的颜色种类,也即把两个子节点的数值按位或得到当前节点的数值。这一步很关键。如果不这么干,那么,查询就几乎退化成O(N)了。同时,还有一步很关键,当前节点所表示的区间不完全含于区间[A, B]且和区间[A, B]有交集时,需要先做下推,然后再分割区间递归地对子节点做处理。为什么要下推呢?因为,你想想,假设当前节点所表示的区间为[C, D],当前一次的修改把区间[C, D]修改为一种纯色时,实际上当前节点的子节点的数值并没有做修改,因为递归到这一层就返回了。那么,既然子节点没有做修改,当我用另外一种颜色去修改左子节点所表示的区间的某一段区间时,按理来说,左子节点所表示的区间内应该有两种颜色,但实际上,由于没有第二次修改的时候,并没有做下推,导致左子节点所表示的区间缺失一种颜色,这就和我们想要的结果不对了。所以,需要做下推操作。在下推操作中也有一点需要注意,只有当当前节点所表示的区间是纯色(只有一种颜色)时,才能把当前节点的颜色下推给子节点。这个应该很容易理解。因为,如果当前节点所表示的区间是五颜六色的,一段红一段紫一段黑……,那说明它的子节点颜色很杂,如果直接把所有颜色都下推给左右两个子节点,那显然不对。如果是左子节点纯红而右子节点纯绿呢?是吧。
2、区间查询:道理和上面的修改类似,给定要查询的区间[A, B],讨论当前节点所表示的区间和要查询的区间的关系,分别做相应的处理。完全不相交:返回0(0或任何值都不会改变那个值)。代表当前节点所表示的区间不是你要查的区间。当前节点所表示的区间完全含于区间[A, B]:直接返回当前节点的数值。有交集,但当前节点所表示的区间不完全含于区间[A, B]:分割当前节点所表示的区间,对子节点做相同的处理。同样地,在查询的过程中,也需要和【区间修改】一样,做下推操作。假如这样,只做一次修改,再做一次查询。修改时,如果区间[C, D]被涂成了纯色,那么,它的子节点是还没被涂色的。如果查询时要查它的子节点的颜色种类,如果不做下推操作,那显然查出来的结果和我们想要不一样。
PS:这题要非常注意,所有格子的初始颜色是1,而不是0。我一开始初始化线段树的节点数值时,全部初始化成了1,即认为初始颜色是0,然后,调bug了调了几个小时,后来看此题的discuss才发现,初始颜色是1。不过话说回来,这题就是题目没出好了,题目中也没说清楚初始颜色,另外,给定的样例又刚好满足初始颜色为0这种情况。这很容易误导刷题者。
另外一点需要注意,题目中明确说明了A和B的大小关系,A不一定小于等于B,所以,这点不要掉坑。这不是出题人的错。
三、源代码
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<cctype> #include<algorithm> #include<utility> #include<vector> #include<set> #include<map> #include<stack> #include<queue> using namespace std; typedef long long LL; ; ]; int n, m, q; , , int r = n) { data[root] = ;//注意啊,初始颜色是1。位值就是1<<1=2。坑啊,在这里调了几个小时。 if(l < r) { ; init(root << , l, mid); init(root << | , mid + , r); } } void pushDown(int root) { )) == ){ data[root << ] = data[root]; data[root << | ] = data[root]; //data[root] = 2; /*注意啊,颜色位值下推后,父节点的值不要变啊,否则查询就变成O(N)了。*/ } } , , int r = n) { if(l > ur || r < ul)return; << ct; else { pushDown(root); ; , l, mid); | , mid + , r); data[root] = data[root << ] | data[root << | ];//注意更新父节点的位值。 } } , , int r = n) { ; if(l >= ul && r <= ur)return data[root]; else { pushDown(root); ; , rch = ; , l, mid); | , mid + , r); return lch | rch; } } int main() { #ifndef ONLINE_JUDGE //freopen("Cinput.txt", "r", stdin); //freopen("Coutput2.txt", "w", stdout); #endif // ONLINE_JUDGE char op; int A, B, C; while(~scanf("%d%d%d", &n, &m, &q)) { init(); for(getchar(); q--; getchar()) { scanf("%c", &op); switch(op) { case 'C': { scanf("%d%d%d", &A, &B, &C); if(A > B)swap(A, B); update(A, B, C); break; } case 'P': { scanf("%d%d", &A, &B); if(A > B)swap(A, B); int res = query(A, B); printf("%d\n", __builtin_popcount(res)); break; } } } } ; }
最新文章
- ANSI Common Lisp Learn
- [android] 手机卫士保存密码时进行md5加密
- LINQ浅析
- 【周期串】NYOJ-1121 周期串
- A题笔记(7)
- oracle单行函数之通用函数
- 【转】利用Ajax.BeginForm提交文件
- DedeCMS新建模型字段【附件样式】修改方法
- JMeter关联的几种方式总结案例
- es6 语法 (map、set和obj 的对比)
- 将模型.pb文件在tensorboard中展示结构
- Microsoft Visual Studio 2010(vs10)安装与使用
- Python首次安装后运行报错(0xc000007b)的解决方法
- Jenkins Maven安装设置
- 广州工业大学2016校赛 F 我是好人4 dfs+容斥
- 四层and七层负载均衡
- Ubuntu或者Ubuntu server重新设置IP地址
- Visual studio C++ MFC之Menu editor
- 【防火墙】DMZ
- Vue计算属性和监听属性