鏈接：https://vjudge.net/problem/POJ-2777#author=0

題意：

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.?

思路：

線段樹，還是普通的線段樹，染色的查詢和更新使用位運算，因為顏色區間在（1-30）之內。

所以可以使用(1<<1-1<<30)來表示這中二進制1的個數來表示顏色的數量。

不過我之前的寫的普通的線段樹我也不知道為啥會WA。

代碼：

#include <cstdio> #include <cstring> #include <iostream> #include <memory.h> #include <algorithm> #include <string> #include <stack> #include <vector> #include <queue>using namespace std; typedef long long LL; const int MAXN = 1e5+10;int Seg[MAXN*4]; int lazy[MAXN*4]; int Vis[100]; int n, t, o; int res;void PushDown(int root) {if (lazy[root] != 0){Seg[root<<1] = (1<<lazy[root]);Seg[root<<1|1] = (1<<lazy[root]);lazy[root<<1] = lazy[root];lazy[root<<1|1] = lazy[root];lazy[root] = 0;} }void PushUp(int root) {Seg[root] = Seg[root<<1]|Seg[root<<1|1]; }void Build(int root, int l, int r) {if (l == r){Seg[root] = 2;return;}int mid = (l + r) / 2;Build(root << 1, l, mid);Build(root << 1 | 1, mid + 1, r);PushUp(root); }void Update(int root, int l, int r, int ql, int qr, int c) {if (r < ql || qr < l)return;if (ql <= l && r <= qr){Seg[root] = (1<<c);lazy[root] = c;return;}PushDown(root);int mid = (l+r)/2;Update(root<<1, l, mid, ql, qr, c);Update(root<<1|1, mid+1, r, ql, qr, c);PushUp(root); }int Query(int root, int l, int r, int ql, int qr) {if (r < ql || qr < l)return 0;if (ql <= l && r <= qr){return Seg[root];}int mid = (l+r)/2;PushDown(root);int col1 = 0, col2 = 0;col1 = Query(root<<1, l, mid, ql, qr);col2 = Query(root<<1|1, mid+1, r, ql, qr);return col1|col2; }int Get(int x) {int res = 0;while (x){if (x&1)res++;x >>= 1;}return res; }int main() {char op[10];int a, b, c;while (~scanf("%d%d%d", &n, &t, &o)){Build(1, 1, n);while (o--){scanf("%s", op);if (op[0] == 'C'){scanf("%d%d%d", &a, &b, &c);if (a > b)swap(a, b);Update(1, 1, n, a, b, c);}else{scanf("%d%d", &a, &b);if (a > b)swap(a, b);memset(Vis, 0, sizeof(Vis));int res = Query(1, 1, n, a, b);printf("%d\n", Get(res));}}}return 0; }

　　

轉載于:https://www.cnblogs.com/YDDDD/p/10847767.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的POJ-2777-CountColor(线段树，位运算）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。