sdutCity Horizon（离散化）

http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2426

这题本来是按高度从大到小找的要向上向下都得更新啊结果TLE了然后又从小到大排序

线段树+离散化把对应的值开个数组存起来最后算面积的时候用离散前的值算高度从小到大排好序更新这样比较简单

View Code

  1 #include<stdio.h>
  2 #include<iostream>
  3 #include<string.h>
  4 #include<algorithm>
  5 using namespace std;
  6 #define N 100001
  7 int num[N];
  8 struct mode
  9 {
 10     int po[2],h;
 11 }q[N*2];
 12 struct node
 13 {
 14     int li,da;
 15 }line[100001];
 16 long long s[N*4];
 17 bool cmp(mode x,mode y)
 18 {
 19     return x.h<y.h;
 20 }
 21 void build(int l,int r,int w)
 22 {
 23     s[w] = -1;
 24     if(l==r-1)
 25     {
 26         return ;
 27     }
 28     int m = (l+r)/2;
 29     build(l,m,2*w);
 30     build(m,r,2*w+1);
 31 }
 32 void add(int a,int b,int da,int l,int r,int w)
 33 {
 34     if(l==a&&b==r)
 35     {
 36         s[w] = da;
 37         return ;
 38     }
 39     int m = (l+r)/2;
 40     if(s[w]>0)
 41     {
 42         s[2*w] = s[w];
 43         s[2*w+1] = s[w];
 44         s[w] = -1;
 45     }
 46     if(b<=m)
 47         add(a,b,da,l,m,2*w);
 48     else
 49         if(a>=m)
 50             add(a,b,da,m,r,2*w+1);
 51         else
 52         {
 53             add(a,m,da,l,m,2*w);
 54             add(m,b,da,m,r,2*w+1);
 55         }
 56 }
 57 long long  search(int l,int r,int w)
 58 {
 59     if(s[w]>0)
 60     {
 61         long long  k = s[w];
 62         return (num[r]-num[l])*k;
 63     }
 64     if(l==r-1)
 65         return 0;
 66     int m = (l+r)/2;
 67     long long  re =0 ;
 68     re+=search(l,m,2*w);
 69     re+=search(m,r,2*w+1);
 70     return re;
 71 }
 72 bool cmpp(node a,node b)
 73 {
 74     return a.da<b.da;
 75 }
 76 int main()
 77 {
 78     int i,j,k,n,m;
 79     long long  s;
 80     while(scanf("%d", &n)!=EOF)
 81     {
 82         build(1,N,1);
 83         s = 0;
 84         for(i = 0; i < n ; i++)
 85         {
 86             scanf("%d%d%d", &q[i].po[0],&q[i].po[1],&q[i+1].h);
 87             line[2*i].li = i+1;
 88             line[2*i].da = q[i].po[0];
 89             line[2*i+1].li = -(i+1);
 90             line[2*i+1].da = q[i].po[1];
 91         }
 92         sort(line,line+2*n,cmpp);
 93         int te = line[0].da,g = 1;
 94         for(i = 0 ; i < 2*n ; i++)
 95         {
 96             if(te!=line[i].da)
 97             {
 98                 te = line[i].da;
 99                 g++;
100             }
101             if(line[i].li>0)
102             {
103                 num[g] = line[i].da;
104                 q[line[i].li].po[0] = g;
105             }
106             else
107             {
108                 num[g] = line[i].da;
109                 q[-line[i].li].po[1] =g;
110             }
111         }
112         sort(q+1,q+n+1,cmp);
113         for(i = 1; i<= n ; i++)
114             add(q[i].po[0],q[i].po[1],q[i].h,1,N,1);
115         s = search(1,N,1);
116         printf("%lld\n",s);
117     }
118     return 0;
119 }