1 /*
2 ymc 2009/4/8 线段树
3 zju 1610
4 题目大意：
5 在x轴上，每次在某一个区间画一种颜色，求最后每种颜色的
6 选段要多少条。
7 l[i],r[i],c[i]表示在区间[l[i],r[i]]上画颜色c[i]
8 （颜色保存的时候保存c[i]+1，因为会出现0号颜色，但是
9 线段树中用0表示背景色）
10 用Left,Right记录最左边的左边和最右边的坐标
11 用Left_c,Right_c记录最小的颜色和最大的颜色
12 flag[i]记录第i号颜色的线段数。
13 */
14
15 #include <iostream>
16 #include <limits>
17 using namespace std;
18 const int N=20000;
19 int tree[N];
20 int l[N],r[N],c[N];
21 int flag[N];
22 int n;
23 int Left,Right,Left_c,Right_c;;
24 void Init()
25 {
26 Left=INT_MAX;
27 Right=INT_MIN;
28 Left_c=INT_MAX;
29 Right_c=INT_MIN;
30 for(int i=0;i<n;i++)
31 {
32 scanf("%d %d %d",&l[i],&r[i],&c[i]);
33 if(l[i]<Left)
34 Left=l[i];
35 if(r[i]>Right)
36 Right=r[i];
37 c[i]++;
38 if(c[i]<Left_c)
39 Left_c=c[i];
40 if(c[i]>Right_c)
41 Right_c=c[i];
42 }
43 for(int k=1;k<=2*(Right-Left);k++)
44 tree[k]=0;//0为初始颜色即背景颜色
45 for(int k=Left_c;k<=Right_c;k++)
46 flag[k]=0;//所有颜色的线段数初始为0
47 }
48
49 /*
50 在以tree[k]为树根的线段树(代表的区间为[l,r])上
51 在区间[a,b]颜色c
52 */
53 void Insert(int k,int l,int r,int a,int b,int c)
54 {
55 if(tree[k]==c)//已经有的颜色要要画的颜色相同
56 return;
57 if(l==a&&r==b)//正好画满整个线段树
58 {
59 tree[k]=c;
60 return;
61 }
62 if(tree[k]>=0)//[l,r]上已有一种颜色，则上色后有多种颜色
63 {
64 tree[2*k]=tree[k];
65 tree[2*k+1]=tree[k];
66 tree[k]=-1;//-1表示该区间有多种颜色
67 }
68 int m=(l+r)/2;
69 if(b<=m)//左儿子上色
70 Insert(2*k,l,m,a,b,c);
71 else if(m<=a)//右儿子上色
72 Insert(2*k+1,m,r,a,b,c);
73 else//左右儿子均上色
74 {
75 Insert(2*k,l,m,a,m,c);
76 Insert(2*k+1,m,r,m,b,c);
77 }
78 }
79 /*
80 在以tree[k]为树根的线段树[l,r]上统计不同颜色的线段数
81 lc，rc为[l,r]上左右端点的颜色
82 */
83 void Count(int k,int l,int r,int &lc,int &rc)
84 {
85 if(tree[k]>=0)//[l,r]上颜色单一
86 {
87 lc=tree[k];//父节点需要知道
88 rc=tree[k];
89 flag[tree[k]]++;
90 return ;
91 }
92 if(l>=r) return;
93 int tl,tr;
94 Count(2*k,l,(l+r)/2,lc,tl);//统计左儿子
95 Count(2*k+1,(l+r)/2,r,tr,rc);//统计右儿子
96 if(tl==tr)//左儿子的最右线段与右儿子的最左线段同色
97 flag[tl]--;
98 }
99 void Solve()
100 {
101 for(int i=0;i<n;i++)
102 Insert(1,Left,Right,l[i],r[i],c[i]);
103 int lc,rc;
104 Count(1,Left,Right,lc,rc);
105 }
106 void OutPut()
107 {
108 for(int k=Left_c;k<=Right_c;k++)
109 if(flag[k]>0)
110 printf("%d %d\n",k-1,flag[k]);
111 }
112 int main()
113 {
114 while(scanf("%d",&n)!=EOF)
115 {
116 Init();
117 Solve();
118 OutPut();
119 printf("\n");
120 }
121 }
1 /*
2 1610 Count the Colors
3 ymc
4 */
5
6 #include <iostream>
7 using namespace std;
8 const int N=8010;
9 struct Point
10 {
11 int e;
12 int s;
13 };
14 Point a[N];
15 int b[N];
16 int n;
17
18 int main()
19 {
20 int c,d,color;
21 while( scanf("%d",&n)!=EOF )
22 {
23 for(int i=0;i<N;i++)
24 {
25 a[i].s=a[i].e=-1;
26 b[i]=0;
27 }
28 for(int i=0;i<n;i++)
29 {
30 scanf("%d %d %d",&c,&d,&color);
31 a[c].s=color;
32 a[d].e=color;
33 for(int k=c+1;k<d;k++)
34 a[k].s=a[k].e=color;
35 }
36 int k;
37 for(int i=0;i<N-1;)
38 {
39 while(a[i].s==-1)
40 i++;
41 k=i;
42 while(k<N&&a[k].s==a[i].s)
43 k++;
44 if(k>=N) break;
45 b[a[i].s]++;
46 i=k;
47 }
48 for(int i=0;i<N;i++)
49 if(b[i]>0)
50 printf("%d %d\n",i,b[i]);
51 printf("\n");
52 }
53 }