首页 > 代码库 > 【POJ2777】Count Color（线段树）
【POJ2777】Count Color（线段树）
以下是题目大意：
有水平方向上很多块板子拼成的墙，一开始每一块都被涂成了颜色1，有C和P两个操作，代表的意思是：
C X Y Z —— 从X到Y将板子涂成颜色Z
P X Y —— 查询X到Y的板子共有多少种颜色
1 2 2 4 //有2块板子 两2颜色 4个询问2 C 1 1 23 P 1 24 C 2 2 25 P 1 2
自己AC后上网查阅了许多别人的题解，看很多人用的什么“状态压缩”、“位运算”等等方法。感觉自己不会的知识还有很多。我用的方法是类似于hash的思想，每次将颜色查询时标记，由于这题的数据范围很小，不需要用离散化处理，所以比较好写。下面附上代码。
1 /*********************************************/ 2 /* author: Desgard_Duan */ 3 /* motto : Everything is surprise for you! */ 4 /*********************************************/ 5 6 #include <iostream> 7 #include <cstring> 8 #include <cstdlib> 9 #include <cstdio>10 #include <cctype>11 #include <cmath>12 #include <algorithm>13 #include <numeric>14 #include <string>15 #include <limits.h>16 #include <vector>17 #include <set>18 #include <map>19 20 using namespace std;21 22 const int maxn = 100100;23 int col[maxn << 2], ans = 0;24 int Hash[50];25 26 void pushDown (int rt) {27 if (col[rt]) {28 col[rt * 2] = col[rt * 2 + 1] = col[rt];29 col[rt] = 0;30 }31 }32 33 void build (int l, int r, int rt) {34 col[rt] = 1;35 if (l == r) return ;36 int m = (l + r) / 2;37 build (l, m, rt * 2);38 build (m + 1, r, rt * 2 + 1);39 }40 41 void update (int L, int R, int c, int l, int r, int rt) {42 if (L <= l && r <= R) {43 col[rt] = c;44 return ;45 }46 pushDown (rt);47 int m = (l + r) / 2;48 if (L <= m) update (L, R, c, l, m, rt * 2 );49 if (m < R) update (L, R, c, m + 1, r, rt * 2 + 1);50 }51 52 void query (int L, int R, int l, int r, int rt) {53 if (col[rt]) {54 if (Hash[col[rt]] == 0) {55 ans ++;56 Hash[col[rt]] = 1;57 }58 return ;59 }60 int m = (l + r) / 2;61 if (m >= L) query (L, R, l, m, rt * 2);62 if (m < R) query (L, R, m + 1, r, rt * 2 + 1);63 }64 65 int main () {66 int L, T, O, x, y, z;67 char op[5];68 while (~scanf ("%d%d%d", &L, &T, &O)) {69 memset (col, 1, sizeof (col));70 build (1, L, 1);71 while (O --) {72 scanf ("%s%d%d", op, &x, &y);73 if (x > y) swap (x, y);74 if (op[0] == ‘C‘) {75 scanf ("%d", &z);76 update (x, y, z, 1, L, 1);77 } else {78 memset (Hash, 0, sizeof (Hash));79 ans = 0;80 query (x, y, 1, L, 1);81 printf ("%d\n", ans);82 }83 }84 }85 return 0;86 }
【POJ2777】Count Color（线段树）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。