1 //Accepted    804 KB    40 ms  2 //整个题，都是坑  3 //1.The first line of each data set contains exactly one integer n,  4 //1 <= n <= 8000, equal to the number of colored segments  5 //意思是：n表示染色线段的条数，而不是区间的总长度  6 //2.x1 and x2 indicate the left endpoint and right endpoint of the segment, c indicates the color of the segment.  7 //x1 ,x2 表示染色区间的端点位置，而染色的是区间  8 #include <cstdio>  9 #include <cstring> 10 #include <iostream> 11 #include <queue> 12 #include <cmath> 13 #include <algorithm> 14 using namespace std; 15 /** 16   * This is a documentation comment block 17   * 如果有一天你坚持不下去了，就想想你为什么走到这儿！ 18   * @authr songt 19   */ 20 const int imax_n = 8005; 21 int color[imax_n]; 22 struct node 23 { 24     int l,r; 25     int c; 26     int change; 27 }f[imax_n*4]; 28 void build(int t,int l,int r) 29 { 30     f[t].l=l; 31     f[t].r=r; 32     f[t].c=0; 33     f[t].change=0; 34     if (l==r) 35     { 36         return ; 37     } 38     int mid=(f[t].l+f[t].r)/2; 39     build(2*t,l,mid); 40     build(2*t+1,mid+1,r); 41 } 42 void update(int t,int l,int r,int c) 43 { 44     if (f[t].l==l && f[t].r==r) 45     { 46         f[t].c=c; 47         f[t].change=1; 48         return ; 49     } 50     if (f[t].change!=0) 51     { 52         f[2*t].c=f[t].c; 53         f[2*t+1].c=f[t].c; 54         f[2*t].change=f[2*t+1].change=1; 55         f[t].change=0; 56     } 57     int mid=(f[t].l+f[t].r)/2; 58     if (r<=mid) update(2*t,l,r,c); 59     else 60     { 61         if (l>mid) update(2*t+1,l,r,c); 62         else 63         { 64             update(2*t,l,mid,c); 65             update(2*t+1,mid+1,r,c); 66         } 67     } 68 } 69 int query(int t,int k) 70 { 71     if (!(f[t].l<=k && f[t].r>=k)) return 0; 72     if (f[t].l==f[t].r && f[t].l==k) 73     { 74         return f[t].c; 75     } 76     if (f[t].change!=0) 77     { 78         return f[t].c; 79     } 80     int mid=(f[t].l+f[t].r)/2; 81     if (k<=mid) return query(2*t,k); 82     else return query(2*t+1,k); 83 } 84 int n; 85 int x,y,c; 86 void slove() 87 { 88     build(1,1,8000); 89     for (int i=1;i<=n;i++) 90     { 91         scanf("%d%d%d",&x,&y,&c); 92         x++; 93         c++; 94         if (x>y) continue ; 95         update(1,x,y,c); 96     } 97     int t1,t2; 98     t1=0; 99     memset(color,0,sizeof(color));100     for (int i=1;i<=8000;i++)101     {102         t2=query(1,i);103         if (t2==0)104         {105             t1=t2;106             continue ;107         }108         if (t2==t1) continue;109         color[t2]++;110         t1=t2;111     }112     for (int i=1;i<=8001;i++)113     if (color[i]!=0)114     {115         printf("%d %d\n",i-1,color[i]);116     }117 }118 int main()119 {120     while (scanf("%d",&n)!=EOF)121     {122         slove();123         printf("\n");124     }125     return 0;126 }