POJ - 2777 Count Color 线段树+位运算
ACM
6 分钟 读完 (大约 861 个字) 0次访问

POJ - 2777 Count Color 线段树+位运算

Count Color
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 55483 Accepted: 16628
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.
Output

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为多少个气球，T代表有多少种颜色，O代表操作数。C命令是区间[A,B]的气球染成C颜色，P命令是查询区间[A,B]有多少不同的颜色。
题解：一开始的时候是线段树维护大小为30的数组，明显被卡掉了。于是换了个思路，其实就是用二进制做，最大就是1<<L-1，而每一位二进制上代表存在，0代表不存在。于是就能很简单的用位运算进行实现，唯一的难点就是要想到二进制，幸好做这道题的前一天学的是状压dp。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<iostream>
#include<cstring>
#include<sstream>
#include<string>
#include<cstdio>
#include<cctype>
#include<vector>
#include<queue>
#include<cmath>
#include<stack>
#include<list>
#include<set>
#include<map>
#include<algorithm>
#define fi first
#define se second
#define MP make_pair
#define P pair<int,int>
#define PLL pair<ll,ll>
#define Sca(x) scanf("%d",&x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x)
#define Scl2(x,y) scanf("%lld%lld",&x,&y)
#define Scl3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)
#define Pri(x) printf("%d\n",x)
#define Prl(x) printf("%lld\n",x)
#define For(i,x,y) for(int i=x;i<=y;i++)
#define _For(i,x,y) for(int i=x;i>=y;i--)
#define FAST_IO std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define ll long long
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;
const double Pi = acos(-1.0);
using namespace std;
template <class T>void tomax(T&a,T b){ a=max(a,b); }  
template <class T>void tomin(T&a,T b){ a=min(a,b); }
const int N=1e5+5;
int T;
int color;
struct Segt{
	#define lc (p<<1)
	#define rc (p<<1|1)
	#define MID (tree[p].l+tree[p].r)>>1
	struct Tree{
		int l,r;
		int have,lz;
		inline void init(int left,int right){ l=left; r=right; have=1; lz=0; }
		inline void updata(int who){ have=who; lz=who; }
		inline void lable(){ color|=have; } 
	}tree[N<<2|1];
	inline void pushdown(int p){ tree[p].have=tree[lc].have|tree[rc].have; }
	inline void pushup(int p){
		tree[lc].updata(tree[p].lz);
		tree[rc].updata(tree[p].lz);
		tree[p].lz=0;
	}
	void build(int l,int r,int p){
		tree[p].init(l,r);
		if(l==r)  return ;
		int mid=MID;
		build(l,mid,lc);
		build(mid+1,r,rc);
	}
	void updata(int l,int r,int p,int who){
		if(tree[p].l>=l&&tree[p].r<=r){
			tree[p].updata(who);
			return ;
		}
		if(tree[p].lz) pushup(p);
		int mid=MID;
		if(l<=mid) updata(l,r,lc,who);
		if(r>mid) updata(l,r,rc,who);
		pushdown(p);
	}
	void getans(int l,int r,int p){
		if(tree[p].l>=l&&tree[p].r<=r){
			tree[p].lable();
			return ;
		}
		if(tree[p].lz) pushup(p);
		int mid=MID;
		if(l<=mid) getans(l,r,lc);
		if(r>mid) getans(l,r,rc);
		return ; 
	}
	
}t;
int main(){
	int n,m;
	Sca3(n,T,m);
	t.build(1,n,1);
	while(m--){
		char cmd; scanf(" %c",&cmd);
		int A,B; Sca2(A,B);
		if(A>B) swap(A,B); 
		if(cmd=='C'){
			int C; Sca(C); 
			t.updata(A,B,1,1<<(C-1)); 
		}
		else if(cmd=='P'){
			color=0;
			t.getans(A,B,1);
			int sum=0;
			while(color){
				if(color&1) sum++;
				color>>=1;
			}
			Pri(sum);
		}
	}
	return 0;
}
ACM, 位运算, 线段树

喜欢这篇文章？打赏一下作者吧

UVA11992
关注我

链接

分类

标签云

ACM Git Hexo MySQL Python SQL 位运算 内存管理 并查集 枚举和暴力 模拟 正则表达式 物理，大学 线段树 递推

最新文章

归档

标签

ACM 4
Git 1
Hexo 1
MySQL 8
Python 6
SQL 1
位运算 1
内存管理 1
并查集 1
枚举和暴力 1
模拟 1
正则表达式 2
物理，大学 1
线段树 3
递推 1
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×