//贡献6个WA
//先建树,然后插入,总计,mixcolor表示该段不止一色
1
#include<iostream>
2
#define MAX 100000
3
#define mixcolor -1
4
using namespace std;
5
6
struct Seg
7

{
8
int left,right;
9
int color;
10
};
11
12
Seg Segtree[3*MAX+1];
13
bool colortable[31];
14
15
void buildsegtree(int v,int l,int r)
16

{
17
18
Segtree[v].left=l;
19
Segtree[v].right=r;
20
Segtree[v].color=1;
21
if(l==r) return ;
22
23
int mid=(l+r)>>1; // div 2
24
buildsegtree(v*2,l,mid);
25
buildsegtree(v*2+1,mid+1,r);
26
}
27
28
void insertseg(int v,int l,int r,int c)
29

{
30
if( Segtree[v].color != c)
31
{
32
if(Segtree[v].left==l && Segtree[v].right==r)
33
{
34
Segtree[v].color=c;
35
return ;
36
}
37
//only one color
38
if(Segtree[v].color != mixcolor)
39
{
40
Segtree[2*v].color=Segtree[v].color;
41
Segtree[2*v+1].color=Segtree[v].color;
42
Segtree[v].color=mixcolor;
43
}
44
45
int mid=(Segtree[v].left + Segtree[v].right) >> 1 ;
46
47
if(r<=mid) insertseg(2*v,l,r,c);
48
else
49
if(mid<l) insertseg(2*v+1,l,r,c);
50
else
51
{
52
insertseg(2*v,l,mid,c);
53
insertseg(2*v+1,mid+1,r,c);
54
}
55
56
}
57
}
58
59
void count(int v ,int l,int r)
60

{
61
if(Segtree[v].color!=mixcolor )
62
{
63
colortable[Segtree[v].color]=true;
64
return ;
65
}
66
int mid=(Segtree[v].left + Segtree[v].right) >> 1;
67
if(r<=mid) count(2*v,l,r);
68
else if(mid<l) count(2*v+1,l,r);
69
else
70
{
71
count(2*v,l,mid);
72
count(2*v+1,mid+1,r);
73
}
74
}
75
76
int main()
77

{
78
int L,T,O,i,sum=0;
79
char op;
80
int a,b,c;
81
scanf("%d%d%d",&L,&T,&O);
82
buildsegtree(1,1,L);
83
while(O--)
84
{
85
scanf(" %c",&op);
86
if(op=='C')
87
{
88
scanf("%d%d%d",&a,&b,&c);
89
if(a>b)
{sum=a;a=b;b=sum;}
90
insertseg(1,a,b,c);
91
}
92
else
93
{
94
scanf("%d%d",&a,&b);
95
if(a>b)
{sum=a;a=b;b=sum;}
96
count(1,a,b);
97
sum=0;
98
for(i=1;i<=30;i++)
99
if(colortable[i]==true)
100
{
101
sum++;
102
colortable[i]=false;
103
}
104
printf("%d\n",sum);
105
}
106
}
107
return 0;
108
}
109
110
111
112
posted on 2009-04-16 17:01
wyiu 阅读(318)
评论(1) 编辑 收藏 引用 所属分类:
POJ