F

题意：给一段0-8000的线段染色问最后颜色x 有几段

题解：标准线段树但是没有push_up 最后查询是单点按顺序查询每一个点

考虑过使用区间来维护不同的线段有多少种各色的线段思路是两个子区间合并：左子区最右边和右子区最左边如果相同，那么就不变，不同就+1 但是不好维护所以直接单点查还更方便

注意染色是染区间不是染点例如 0 3是染 0 1 2 3这4个数中间的空如果不考虑清楚这一点就会导致染了 2-3 颜色1 0 2颜色2 3-4颜色3 0 到4颜色分别为 2 2 3 3只有两种颜色而如果是染区间的话

2 3区间中染了 1 后面的操作都没有覆盖掉所以要把边映射成点 n个点有n-1个边那么很自然把第一条边成1 8000也就是8000了 update就要符合映射让 l+1 即可

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<set>
 4 #include<vector>
 5 #include<cstring>
 6 #include<iostream>
 7 using namespace std;
 8 const int maxn=8000+10;
 9 int num[maxn],ans[maxn];
10 struct Node{
11     int l,r,lazy,v;
12     void update(int x){
13         v=x;
14         lazy=x;
15     }
16 }tree[maxn*4];
17 void push_up(int x){
18 
19 }
20 void push_down(int x){
21     int lazyval=tree[x].lazy;
22     if(lazyval!=-1){
23         tree[x<<1].update(lazyval);
24         tree[x<<1|1].update(lazyval);
25         tree[x].lazy=-1;
26     }
27 }
28 void update(int x,int l,int r,int c){
29     int L=tree[x].l,R=tree[x].r;
30     if(l<=L&&R<=r){
31         tree[x].update(c);
32     }
33     else{
34         int mid=L+R>>1;
35         push_down(x);
36         if(mid>=l)update(x<<1,l,r,c);
37         if(mid<r)update(x<<1|1,l,r,c);
38 //        push_up(x);
39     }
40 }
41 int lastcolor=-1;
42 int query(int x,int l,int r){
43     //int L=tree[x].l,R=tree[x].r;
44     if(l==r){
45      if(tree[x].v!=-1&&tree[x].v!=lastcolor)ans[tree[x].v]++;
46      lastcolor=tree[x].v;
47      //if(lastcolor!=-1)cout<<l<<" " <<x<<" "<<tree[x].v<<endl;
48     }
49     else {
50       push_down(x);
51         int mid=l+r>>1;
52         query(x<<1,l,mid);
53         query(x<<1|1,mid+1,r);
54     }
55 }
56 void build(int x,int l,int r){
57     tree[x].l=l,tree[x].r=r;
58     tree[x].lazy=-1;
59     if(l==r){
60     tree[x].v=-1;
61     //if(l==8000)cout<<" !zzz! "<<x<<endl;
62         return ;
63     }
64     else {
65         int mid=l+r>>1;
66         build(x<<1,l,mid);
67         build(x<<1|1,mid+1,r);
68         //push_up(x);
69     }
70 
71 }
72 int main(){
73     int n;
74     while(scanf("%d",&n)==1)
75     {
76         lastcolor=-1;
77         build(1,1,8000);
78         memset(ans,0,sizeof(ans));
79         for(int i=1;i<=n;i++){
80             int x,y,c;
81             scanf("%d%d%d",&x,&y,&c);
82             update(1,x+1,y,c);
83         }
84     //        cout<<tree[8286].v<<"!!  "<<endl;
85         query(1,1,8000);
86     //        cout<<tree[8286].v<<" 22222"<<endl;
87         for(int i=0;i<=8000;i++){
88             if(ans[i]){
89                 printf("%d %d
",i,ans[i]);
90             }
91         }
92         cout<<endl;
93     }
94 }