|
|
##[$POJ$ $2777$ $Count$ $Color$](http://poj.org/problem?id=2777)
|
|
|
|
|
|
### 一、题目大意
|
|
|
题意：有$L$块连续的板子，每块板子最多染一种颜色，有$T$种($<=30$)颜色，刚开始将所有板子染成颜色$1$，$O$次操作（包括将$[a,b]$染成颜色$k$，和询问$[a,b]$的不同颜色数），输出每次询问的值。
|
|
|
|
|
|
### 二、题目分析
|
|
|
经典的区间染色问题。
|
|
|
|
|
|
因为总共的颜色最多只有$30$种，因此我们可以用一个范围在$int$的二进制数$bit$存储每一种颜色（$bit$的二进制下的每一位代表着一种颜色）
|
|
|
|
|
|
之后我们只需要用线段树对区间上的$bit$进行维护即可。注意在我们区间合并$pushup$的过程中，我们需要将某个结点的左右儿子的值都或起来，作为该结点的值。
|
|
|
|
|
|
之后对于操作$C$，我们只需要将区间$[l,r]$的值更新即可。
|
|
|
|
|
|
对于操作$Q$，我们只需要将区间$[l,r]$的$bit$求出，并求出$bit$在二进制位下的$1$的个数为答案。
|
|
|
|
|
|
`ps`：这个问题种还有一个坑点，对于每一个操作种的$l$和$r$，题目中并没有说明哪个是左区间，哪个是有区间，因此我们还需要特判一下大小。
|
|
|
|
|
|
### 三、实现代码
|
|
|
```cpp {.line-numbers}
|
|
|
#include <cstdio>
|
|
|
#include <cstring>
|
|
|
#include <algorithm>
|
|
|
#include <iostream>
|
|
|
|
|
|
using namespace std;
|
|
|
const int N = 100010;
|
|
|
|
|
|
#define ls u << 1
|
|
|
#define rs u << 1 | 1
|
|
|
|
|
|
struct Node {
|
|
|
int l, r;
|
|
|
int add, sum;
|
|
|
} tr[N << 2];
|
|
|
|
|
|
void pushup(int u) {
|
|
|
tr[u].sum = tr[ls].sum | tr[rs].sum; //因为是模拟二进制的操作，所以采用 或 运算即可完成拼接操作
|
|
|
}
|
|
|
|
|
|
void pushdown(int u) {
|
|
|
if (tr[u].add) {
|
|
|
tr[ls].add = tr[rs].add = tr[u].add;
|
|
|
tr[ls].sum = tr[rs].sum = tr[u].add;
|
|
|
tr[u].add = 0;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
void build(int u, int l, int r) {
|
|
|
tr[u].l = l, tr[u].r = r;
|
|
|
if (l == r) {
|
|
|
tr[u].sum = 1; // sum记录的其实是一个30位的二进制压缩模拟数字，此时置为1表示最后一位即0位为1，是默认的颜色
|
|
|
return;
|
|
|
}
|
|
|
int mid = (l + r) >> 1;
|
|
|
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
|
|
|
pushup(u);
|
|
|
}
|
|
|
|
|
|
void modify(int u, int l, int r, int c) {
|
|
|
if (l <= tr[u].l && tr[u].r <= r) {
|
|
|
tr[u].add = 1 << (c - 1);
|
|
|
tr[u].sum = 1 << (c - 1);
|
|
|
return;
|
|
|
}
|
|
|
|
|
|
pushdown(u);
|
|
|
int mid = tr[u].l + tr[u].r >> 1;
|
|
|
if (l <= mid) modify(u << 1, l, r, c);
|
|
|
if (r > mid) modify(u << 1 | 1, l, r, c);
|
|
|
pushup(u);
|
|
|
}
|
|
|
|
|
|
int query(int u, int l, int r) {
|
|
|
if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
|
|
|
|
|
|
int ans = 0;
|
|
|
pushdown(u);
|
|
|
int mid = tr[u].l + tr[u].r >> 1;
|
|
|
if (l <= mid) ans = query(u << 1, l, r);
|
|
|
if (r > mid) ans = ans | query(u << 1 | 1, l, r);
|
|
|
return ans;
|
|
|
}
|
|
|
|
|
|
//手工版本数字1个数
|
|
|
int count(int x) {
|
|
|
int cnt = 0;
|
|
|
while (x) {
|
|
|
cnt++;
|
|
|
x -= (x & -x);
|
|
|
}
|
|
|
return cnt;
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
//加快读入
|
|
|
ios::sync_with_stdio(false), cin.tie(0);
|
|
|
int n, t, m; //区间[1,n],t种颜色,m个操作
|
|
|
cin >> n >> t >> m;
|
|
|
|
|
|
//构建
|
|
|
build(1, 1, n);
|
|
|
|
|
|
while (m--) {
|
|
|
char op;
|
|
|
int l, r;
|
|
|
cin >> op >> l >> r;
|
|
|
if (l > r) swap(l, r); //坑点题目没说哪个大哪个小，需要特判
|
|
|
if (op == 'C') {
|
|
|
int c;
|
|
|
cin >> c;
|
|
|
modify(1, l, r, c);
|
|
|
} else {
|
|
|
int ans = query(1, l, r);
|
|
|
int cnt = count(ans); //获取某个数二进制位1的个数
|
|
|
printf("%d\n", cnt);
|
|
|
}
|
|
|
}
|
|
|
return 0;
|
|
|
}
|
|
|
``` |
