//貢獻6個WA
//先建樹，然后插入，總計，mixcolor表示該段不止一色
1
#include<iostream>
2#define MAX 100000
3#define mixcolor -1
4using namespace std;
5
6struct Seg
7
{
8
int left,right;
9 int color;
10
};
11
12Seg Segtree[3*MAX+1];
13bool colortable[31];
14
15void 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
28void 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
59void 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
76int 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 閱讀(326)
評論(1) 編輯 收藏 引用 所屬分類:
POJ