kb-07线段树-06离散化（与第四题类似）

  1 /*
  2    zoj1610
  3    这题是离散化，区间特殊查询的，和之前的第4 题是异曲同工的
  4  */
  5 #include<iostream>
  6 #include<cstdio>
  7 #include<cstring>
  8 #include<algorithm>
  9 using namespace std;
 10 struct Node
 11 {
 12     int l,r,value;
 13 }tr[40005]={0};
 14 int col[8005]={0};
 15 int c[8005]={0};
 16 int discrete[40005]={0};
 17 void build(int rt,int l,int r)
 18 {
 19     tr[rt].l=l;
 20     tr[rt].r=r;
 21     tr[rt].value=-1;
 22     if(l==r)
 23         return ;
 24     int mid=(l+r)/2;
 25     build(rt<<1,l,mid);
 26     build(rt<<1|1,mid+1,r);
 27 }
 28 void Pushdown(int rt)
 29 {
 30     tr[rt<<1].value=tr[rt<<1|1].value=tr[rt].value;
 31     tr[rt].value=-1;
 32 }
 33 void Update(int rt,int l,int r,int x)
 34 {
 35     if(tr[rt].value==x)
 36         return ;
 37     if(tr[rt].l>=l&&tr[rt].r<=r)
 38     {
 39         tr[rt].value=x;
 40         return ;
 41     }
 42     if(tr[rt].value!=-1)
 43         Pushdown(rt);
 44     if(l<=tr[rt<<1].r)
 45     {
 46         if(r<=tr[rt<<1].r)
 47             Update(rt<<1,l,r,x);
 48         else 
 49             Update(rt<<1,l,tr[rt<<1].r,x);
 50     }
 51     if(r>=tr[rt<<1|1].l)
 52     {
 53         if(l>=tr[rt<<1|1].l)
 54             Update(rt<<1|1,l,r,x);
 55         else 
 56             Update(rt<<1|1,tr[rt<<1|1].l,r,x);
 57     }
 58     if(tr[rt<<1].value==tr[rt<<1|1].value&&tr[rt<<1].value!=-1)
 59         tr[rt].value=tr[rt<<1].value;
 60 }
 61 int erfen(int l,int r,int x)
 62 {
 63     while(l<=r)
 64     {
 65         int mid=(l+r)/2;
 66         if(x<discrete[mid])
 67             r=mid-1;
 68         else
 69             l=mid+1;
 70     }
 71     return r;
 72 }
 73 void Query(int rt)
 74 {
 75     if(tr[rt].value!=-1)
 76     {
 77         for(int i=tr[rt].l;i<=tr[rt].r;i++)
 78             col[i]=tr[rt].value;
 79         return ;
 80     }
 81     if(tr[rt].l==tr[rt].r)
 82         return ;
 83     Query(rt<<1);
 84     Query(rt<<1|1);
 85 }
 86 int main()
 87 {
 88     int n;
 89     while(scanf("%d",&n)!=EOF&&n)
 90     {
 91         int a[8005][3]={0};
 92         int t=0;
 93         memset(col,-1,sizeof(col));
 94         memset(c,0,sizeof(c));
 95         memset(tr,0,sizeof(tr));
 96         memset(discrete,0,sizeof(discrete));
 97         for(int i=0;i<n;i++)
 98         {
 99             scanf("%d%d%d",&a[i][0],&a[i][1],&a[i][2]);
100             discrete[t++]=a[i][0];
101             discrete[t++]=a[i][1];
102         }
103         sort(discrete,discrete+t);
104         int z=1;
105         for(int i=1;i<t;i++)
106         {
107             if(discrete[i]!=discrete[i-1])
108                 discrete[z++]=discrete[i];
109         }
110         for(int i=z-1;i>0;i--)
111         {
112             if(discrete[i]-discrete[i-1]>1)
113                 discrete[z++]=discrete[i-1]+1;
114         }
115         sort(discrete,discrete+z);
116         for(int i=z;i>0;i--)
117         {
118             discrete[i]=discrete[i-1];
119         }
120         build(1,1,z+5);
121         for(int i=0;i<n;i++)
122         {
123             int ll=erfen(1,z,a[i][0]);
124             int rr=erfen(1,z,a[i][1]);
125             Update(1,ll,rr-1,a[i][2]);
126         }
127         Query(1);
128         int temp=-1;
129         for(int i=1;i<=z;i++)
130         {
131             if(temp!=col[i])
132             {
133                 c[col[i]]++;
134                 temp=col[i];
135             }
136         }
137         for(int i=0;i<=8000;i++)
138         {
139             if(c[i]>0)
140             {
141                 printf("%d %d
",i,c[i]);
142             }
143         }
144         printf("
");
145     }
146     return 0;
147 }