POJ P2777 Count Color——线段树状态压缩
Description
There is a very long board with length L centimeter, L is a positive integer, so we can evenly divide the board into L segments, and they are labeled by 1, 2, ... L from left to right, each is 1 centimeter long. Now we have to color the board - one segment with only one color. We can do following two operations on the board:
1. "C A B C" Color the board from segment A to segment B with color C.
2. "P A B" Output the number of different colors painted between segment A and segment B (including).
In our daily life, we have very few words to describe a color (red, green, blue, yellow…), so you may assume that the total number of different colors T is very small. To make it simple, we express the names of colors as color 1, color 2, ... color T. At the beginning, the board was painted in color 1. Now the rest of problem is left to your.
题目大意:
#include<cstdio>
using namespace std;
const int MAXN=;
int tree[MAXN<<];
int lz[MAXN<<];
int n,t,o,L,R;
void up(int );
void down(int ,int ,int );
void col(int ,int ,int ,int );
int ask(int ,int ,int );
int ans(int );
int main()
{
int i,j,k;
char s[];
scanf("%d%d%d",&n,&t,&o);
lz[]=;
tree[]=;
for(i=;i<=o;i++){
scanf("%s",s);
if(s[]=='C'){
scanf("%d%d%d",&L,&R,&j);
if(L>=R)
k=L,L=R,R=k;
col(,n,,j);
}
else{
scanf("%d%d",&L,&R);
if(L>=R)
k=L,L=R,R=k;
j=ask(,n,);
printf("%d\n",ans(j));
}
}
}
void up(int nu){
tree[nu]=tree[nu<<]|tree[nu<<|];
}
void down(int l,int r,int nu){
if(!lz[nu])return ;
tree[nu<<]=lz[nu];
tree[nu<<|]=lz[nu];
lz[nu<<]=lz[nu<<|]=lz[nu];
lz[nu]=;
}
void col(int l,int r,int nu,int x){
if(L<=l&&r<=R){
tree[nu]=lz[nu]=(<<(x-));
return ;
}
down(l,r,nu);
int mid=(l+r)>>;
if(L<=mid)
col(l,mid,nu<<,x);
if(R>mid)
col(mid+,r,nu<<|,x);
up(nu);
}
int ask(int l,int r,int nu){
if(L<=l&&r<=R)
return tree[nu];
down(l,r,nu);
int ans=,mid=(l+r)>>;
if(L<=mid)
ans|=ask(l,mid,nu<<);
if(R>mid)
ans|=ask(mid+,r,nu<<|);
return ans;
}
int ans(int x){
int re=;
while(x){
if(x&)
re++;
x>>=;
}
return re;
}
最新文章
- 解决Ubuntu安装openssh-server依赖问题
- Java 毫秒转换为日期类型、日期转换为毫秒
- javascript学习第三课引用类型object
- Python学习总结19:类(一)
- 发布windows phone应用经历实谈
- bzoj1875
- Submission Details
- OpenSSL命令---req
- nginx+memcached+ftp上传图片+iis
- P3414 SAC#1 - 组合数
- HTML5 Canvas、内联 SVG、Canvas vs. SVG
- 初学Log4Net
- jquery的2.0.3版本源码系列(6):2880-3042行,回调对象,对函数的统一管理
- 使用ssh keys实现免验证登陆远程服务
- [Usaco2005 nov]Grazing on the Run 边跑边吃草 BZOJ1742
- spring的DI.IoC是什么
- C++各种优化
- ELKStack
- pandas 视频讲座 from youtube
- 双十二“MathType”限时6折特惠
热门文章
- Python 资源大全
- hibernate与Oracle
- 架构师养成记--35.redis集群搭建
- 2016级算法第六次上机-B.ModricWang&#39;s FFT : EASY VERSION
- UITableView 头部效果/放大/移动跟随效果
- MarkDown添加图片的三种方式
- jquery中ajax使用error调试错误的方法,实例分析了Ajax的使用方法与error函数调试错误的技巧
- 从源码层面解析SpringIOC容器
- 完美原创:centos7.1 从源码升级安装Python3.5.2
- javac的访问者模式