POJ 2777 Count Color (线段树成段更新+二进制思维)
2024-08-21 04:30:00
题目链接：http://poj.org/problem?id=2777
题意是有L个单位长的画板，T种颜色，O个操作。画板初始化为颜色1。操作C讲l到r单位之间的颜色变为c，操作P查询l到r单位之间的颜色有几种。
很明显的线段树成段更新，但是查询却不好弄。经过提醒，发现颜色的种类最多不超过30种，所以我们用二进制的思维解决这个问题，颜色1可以用二进制的1表示，同理，颜色2用二进制的10表示，3用100，...。假设有一个区间有颜色2和颜色3，那么区间的值为二进制的110(十进制为6)。那我们就把一个区间的颜色种类表示为（左孩子的值‘|’右孩子的值）。
然后就是一个线段树的成段更新。
有个坑点是这个题目的l可能比r大...
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = ;
struct segtree {
int l , r , val , lazy;
}T[MAXN << ];
//获取颜色的种类
int get(int n) {
int cont = ;
while(n) {
if(n & )
cont++;
n >>= ;
}
return cont;
} void init(int p , int l , int r) {
int mid = (l + r) >> ;
T[p].l = l , T[p].r = r , T[p].lazy = ;
if(l == r) {
T[p].val = ;
return ;
}
init(p << , l , mid);
init((p << )| , mid + , r);
T[p].val = (T[p << ].val | T[(p << )|].val);
} void updata(int p , int l , int r , int val) {
int mid = (T[p].l + T[p].r) >> ;
if(l == T[p].l && T[p].r == r) {
T[p].val = val;
T[p].lazy = val;
return ;
}
if(T[p].lazy) {
T[p << ].val = T[(p << )|].val = T[p].lazy;
T[p << ].lazy = T[(p << )|].lazy = T[p].lazy;
T[p].lazy = ;
}
if(r <= mid) {
updata(p << , l , r , val);
}
else if(l > mid) {
updata((p << )| , l , r , val);
}
else {
updata(p << , l , mid , val);
updata((p << )| , mid + , r , val);
}
T[p].val = (T[p << ].val | T[(p << )|].val);
}
//返回颜色种类的二进制对应的十进制的值
int query(int p , int l , int r) {
int mid = (T[p].l + T[p].r) >> ;
if(T[p].l == l && T[p].r == r) {
return T[p].val;
}
if(T[p].lazy) {
T[p << ].val = T[(p << )|].val = T[p].lazy;
T[p << ].lazy = T[(p << )|].lazy = T[p].lazy;
T[p].lazy = ;
}
if(r <= mid) {
return query(p << , l , r);
}
else if(l > mid) {
return query((p << )| , l , r);
}
else {
return query(p << , l , mid) | query((p << )| , mid + , r);
}
} int main()
{
int L , t , n , l , r , c;
char str[];
while(~scanf("%d %d %d" , &L , &t , &n)) {
init( , , L);
while(n--) {
scanf("%s" , str);
if(str[] == 'C') {
scanf("%d %d %d" , &l , &r , &c);
int temp = l + r;
l = min(l , r);
r = temp - l;
updata( , l , r , ( << (c - )));
}
else {
scanf("%d %d" , &l , &r);
int temp = l + r;
l = min(l , r);
r = temp - l;
int res = get(query( , l , r));
printf("%d\n" , res);
}
}
}
}
最新文章
- .NET开发者必备的工具箱
- android 待机流程
- Go语言_时间篇
- .Net AppDomain.CurrentDomain.AppendPrivatePath(@"Libs");
- 用JavaScript操作Media Queries
- jquery调用页面的方法
- C++编程规范之18：尽可能局部地声明变量
- QLineEdit 自动完成（使用setCompleter，内含一个ListView）
- Android 增量更新实例（Smart App Updates）
- ipset批量配置iptables
- 图像实验室 website 项目日志
- 一个请求过来都经过了什么?(Thrift版)
- import文件时 ~/ 不识别问题（react）
- 【收藏】JS获取鼠标的X,Y坐标位置
- Scrum Meeting 7 -2014.11.13
- [HTML5和Flash视频播放器]Video.js 学习笔记(一 ) HLS库:videojs-contrib-hls
- 新手福利：Apache Spark入门攻略
- 056——VUE中vue-router之路由参数的验证处理保存路由安全
- 机器学习 ----Tensorflow
- 在spring中常被忽视的注解 @Primary