POJ 2777(线段树)
Count Color
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 42507 | Accepted: 12856 |
Description
Chosen Problem Solving and Program design as an optional course, you are required to solve all kinds of problems. Here, we get a new problem.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.
Input
First line of input contains L (1 <= L <= 100000), T (1 <= T <= 30) and O (1 <= O <= 100000). Here O denotes the number of operations. Following O lines, each contains "C A B C" or "P A B" (here A, B, C are integers, and A may be larger than B) as an operation defined previously.
Ouput
results of the output operation in order, each line contains a number.
Sample Input
2 2 4
C 1 1 2
P 1 2
C 2 2 2
P 1 2
Sample Output
2
1
题目大意：
有L个画板，30种颜色，o个操作：P a b :询问a-b 种有多少种颜色不同的，C a b c:把a-b全部涂成c的颜色（覆盖掉）
解题思路：
线段树+二进制判重
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 100005
using namespace std;
int n,m,q;
char c;
int x,y,z;
int sum;
struct Node
{
int l,r,col;//col用位运算，颜色30种，
int cover;//延时更新，是否涂了颜色
}no[*N];
void pushup(int u)
{
no[u].col=no[u*].col|no[u*+].col;
return;
}
void pushdown(int u)
{
no[u].cover=;
no[u*].cover=;
no[u*].col=no[u].col;
no[u*+].cover=;
no[u*+].col=no[u].col;
return;
}
void build(int u,int left,int right)
{
no[u].l=left;
no[u].r=right;
no[u].col=;
no[u].cover=;//初始状态全为1
if(left==right)
return;//没有赋值
int mid=(no[u].l+no[u].r)>>;
build(u*,left,mid);
build(u*+,mid+,right);
pushup(u);
}
void updata(int u,int left,int right,int val)
{
if(no[u].l==left&&no[u].r==right)
{
no[u].col=<<(val-);//直接等于，覆盖原有颜色
no[u].cover=;
return;
}
if(no[u].col==<<(val-))return;//剪枝：如果颜色一样，不用更新
if(no[u].cover)pushdown(u);//延时更新
int mid=(no[u].l+no[u].r)>>;
if(right<=mid)updata(u*,left,right,val);
else if(left>mid)updata(u*+,left,right,val);
else
{
updata(u*,left,mid,val);
updata(u*+,mid+,right,val);
}
pushup(u);
}
void query(int u,int left,int right)
{
if(no[u].l==left&&no[u].r==right)
{
sum|=no[u].col;
return ;
}
if(no[u].cover)pushdown(u);
int mid=(no[u].l+no[u].r)>>;
if(right<=mid)query(u*,left,right);
else if(left>mid)query(u*+,left,right);
else
{
query(u*,left,mid);
query(u*+,mid+,right);
}
}
int Ans(int sum)
{
int ans=;
while(sum)
{
if(sum&)
ans++;
sum=(sum>>);
}
return ans;
}
int main()
{
freopen("poj2777.in","r",stdin);
freopen("poj2777.out","w",stdout);
scanf("%d%d%d",&n,&m,&q);
build(,,n);
getchar();
for(int i=;i<=q;i++)
{
scanf("%s",&c);
if(c=='C')
{
scanf("%d%d%d",&x,&y,&z);
if(x>y)swap(x,y);
getchar();
updata(,x,y,z);
}
else
{
scanf("%d%d",&x,&y);
getchar();
sum=;
if(x>y)swap(x,y);//x可能>y
query(,x,y);
cout<<Ans(sum)<<endl;;
}
}
return ;
}
最新文章
- Java Selenium封装--RemoteWebDriver
- Dynamics CRM 2013 SP1 升级到Dynamics CRM 2015
- [RxJS] Combination operators: concat, startWith
- Wii硬盘版玩机心得
- ibatis中的resultClass,parameterClass,resultMap,resultType的使用与区别
- virtualenv 管理python 环境
- Inno Setup
- Learning-Python【34】：进程之生产者消费者模型
- Codeforces Round #428 (Div. 2)
- openfire群消息投递
- 2018北美部分CS项目学费
- 1191. [HNOI2006]超级英雄【二分图】
- mybatis 模糊查询和<![CDATA[ ]]>的作用
- jQuery 事件注册
- Centos7中yum安装MySQL
- Google：移动端搜索正式上线移动友好标签
- Python3 PyPAML 模块(配置文件的操作)
- django 部署到Ubuntu-apache2遇到的问题汇总
- python三大神器之迭代器
- PIC32MZ 通过USB在线升级 -- USB CDC bootloader