問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2777思路:
線段樹的典型題
參考:
http://blog.csdn.net/xiaofengsheng/archive/2009/03/03/3953265.aspx代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_N 100001
5 #define MAX_T 31
6 #define LEFT(i) (i<<1)
7 #define RIGHT(i) ((i<<1)+1)
8 int L, T, O;
9 struct Node {
10 int left, right;
11 int color;
12 };
13 struct Node nodes[MAX_N*3];
14 int rt, visited[MAX_T];
15
16 void
17 build(int begin, int end, int step)
18 {
19 int mid;
20 nodes[step].left = begin;
21 nodes[step].right = end;
22 nodes[step].color = 1;
23 if(begin == end)
24 return;
25 mid = (begin+end)>>1;
26 build(begin, mid, LEFT(step));
27 build(mid+1, end, RIGHT(step));
28 }
29
30 void
31 insert(int begin, int end, int color, int step)
32 {
33 int mid;
34 if(nodes[step].left==begin && nodes[step].right==end) {
35 nodes[step].color = color;
36 return;
37 };
38 if(nodes[step].color != -1) {
39 nodes[LEFT(step)].color = nodes[RIGHT(step)].color = nodes[step].color;
40 nodes[step].color = -1; /* mixed color */
41 }
42 mid = (nodes[step].left+nodes[step].right)>>1;
43 if(begin > mid)
44 insert(begin, end, color, RIGHT(step));
45 else if(end<=mid)
46 insert(begin, end, color, LEFT(step));
47 else {
48 insert(begin, mid, color, LEFT(step));
49 insert(mid+1, end, color, RIGHT(step));
50 }
51 }
52
53 void
54 calculate(int begin, int end, int step)
55 {
56 if(nodes[step].color != -1) {
57 if(!visited[nodes[step].color]) {
58 visited[nodes[step].color] = 1;
59 ++rt;
60 }
61 return;
62 }
63 int mid = (nodes[step].left+nodes[step].right)>>1;
64 if(mid < begin)
65 calculate(begin, end, RIGHT(step));
66 else if(mid >= end)
67 calculate(begin, end, LEFT(step));
68 else {
69 calculate(begin, mid, LEFT(step));
70 calculate(mid+1, end, RIGHT(step));
71 }
72 }
73
74 int
75 main(int argc, char **argv)
76 {
77 int i, a, b, c;
78 char ops[2];
79 while(scanf("%d %d %d", &L, &T, &O) != EOF) {
80 build(1, L, 1);
81 for(i=1; i<=O; i++) {
82 scanf("%s", ops);
83 if(ops[0] == 'C') {
84 scanf("%d %d %d", &a, &b, &c);
85 if(a <= b)
86 insert(a, b, c, 1);
87 else
88 insert(b, a, c, 1);
89 } else if(ops[0] == 'P') {
90 scanf("%d %d", &a, &b);
91 rt = 0;
92 memset(visited, 0, sizeof(visited));
93 if(a <= b)
94 calculate(a, b, 1);
95 else
96 calculate(b, a, 1);
97 printf("%d\n", rt);
98 }
99 }
100 }
101 }