Hint
The first building overlaps with the fourth building for an area of 1 square unit, so the total area is just 3*1 + 1*4 + 2*2 + 2*3 - 1 = 16.
￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥
第一份代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
struct node1{
int x,y;
__int64 h;
bool operator<(const node1 &T)const
{
return h<T.h;
}
}M[400005];
struct node2{
int s,n,flag;
bool operator<(const node2 &T)const
{
if(s!=T.s)
return s<T.s;
else return n<T.n;
}
}F[400005*2+10];
struct node3{
int l,r;
__int64 h;
int mid()
{
return (l+r)>>1;
}
}T[400005*5];
int H[400005*2+10];
__int64 ss=0;
void build(int l,int r,int root)
{
T[root].l=l;T[root].r=r;
T[root].h=0;
if(r>l+1)
{
int mid=T[root].mid();
build(l,mid,root<<1);
build(mid,r,root<<1|1);
}
}
void modify(int l,int r,int h,int root)
{
if(T[root].l==l&&T[root].r==r)
{
T[root].h=h;
return ;
}
if(T[root].h!=0)
{
T[root<<1].h=T[root].h;
T[root<<1|1].h=T[root].h;
T[root].h=0;
}
int mid=T[root].mid();
if(r<=mid)
modify(l,r,h,root<<1);
else if(l>=mid)
modify(l,r,h,root<<1|1);
else {
modify(l,mid,h,root<<1);
modify(mid,r,h,root<<1|1);
}
}
void find(int l,int r,int root)
{
if(T[root].h)
{
ss+=(H[T[root].r]-H[T[root].l])*T[root].h;
return ;
}
if(r!=l+1)
{
int mid=T[root].mid();
find(l,mid,root<<1);
find(mid,r,root<<1|1);
}
}
int main()
{
int i,j,k,n,m;
while(scanf("%d",&n)==1)
{
ss=0;
memset(M,0,sizeof(M));
memset(F,0,sizeof(F));
memset(H,0,sizeof(H));
for(i=1;i<=n;i++)
{
scanf("%d%d%d",&M[i].x,&M[i].y,&M[i].h);
F[2*i-1].s=M[i].x;F[2*i-1].n=i;F[2*i-1].flag=1;
F[2*i].s=M[i].y;F[2*i].n=i;F[2*i].flag=0;
}
j=1;
sort(F+1,F+2*n+1);
H[1]=F[1].s;
for(i=1;i<2*n;i++)
{
if(F[i].s!=F[i+1].s)
H[++j]=F[i+1].s;
}
M[F[1].n].x=1;
int s=1;
for(i=2;i<=2*n;i++)
{
if(F[i].s!=F[i-1].s)
s++;
if(F[i].flag)
M[F[i].n].x=s;
else M[F[i].n].y=s;
}
build(1,j,1);//printf("***\n");
sort(M+1,M+n+1);
for(i=1;i<=n;i++)
{
modify(M[i].x,M[i].y,M[i].h,1);
}
find(1,j,1);
printf("%I64d\n",ss);
}
return 0;
}
第二份代码：
#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <map>
#include <math.h>
#include <queue>
#include <stack>
#include <list>
#include <deque>
#include <set>
#include <numeric>
#include <functional>
#include <ctype.h>
using namespace std;
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define N 80010
typedef __int64 LL;
LL tree[N*4],hash[N*2];
//int z[40005][3];
LL ans;
struct Node
{
int value,flag,pos;
bool operator< (const Node &b) const
{
return value < b.value;
}
}tt[N];
struct node
{
int x,y,h;
bool operator<(const node &b) const
{
return h<b.h;
}
}z[40050];
void insert(int p,int l,int r,int ll,int rr,int h)
{
// if( tree[p] >= h) return ;
if(ll==l && rr==r)
{
tree[p] = max(h,tree[p]);
return ;
}
if( tree[p] != -1 && tree[p] < h)
{
tree[2*p]=tree[p]; tree[2*p+1]=tree[p];
tree[p] = -1;
}
int mid= (l+r)>>1;
if(rr <= mid) insert(2*p,l,mid,ll,rr,h);
else if(ll > mid) insert(2*p+1,mid+1,r,ll,rr,h);
else {
insert(2*p,l,mid,ll,mid,h);
insert(2*p+1,mid+1,r,mid+1,rr,h);
}
}
void query(int p,int l,int r)
{
if(tree[p] != -1)
{
ans += ((hash[r+1]-hash[l])*tree[p]);
return ;
}
if(l==r) return ;
int mid=(l+r)>>1;
query(2*p,l,mid);
query(2*p+1,mid+1,r);
}
int main()
{
int n,i,j=0;
while( scanf("%d",&n) == 1){
j=0;
memset(hash,0,sizeof(hash));
for(i=0;i<n;i++)
{
scanf("%d%d%d",&z[i].x,&z[i].y,&z[i].h);
tt[j].value=z[i].x; tt[j].pos=i; tt[j++].flag=0;
tt[j].value=z[i].y; tt[j].pos=i; tt[j++].flag=1;
}
sort(tt,tt+2*n);
int index=1;
hash[index]=tt[0].value;
if(tt[0].flag)
z[tt[0].pos].y = index;
else z[tt[0].pos].x=index;
for(i=1;i<2*n;i++)
{
if(tt[i].value != tt[i-1].value)
{
index++;
hash[index] = tt[i].value;
}
if(tt[i].flag)
z[tt[i].pos].y = index;
else z[tt[i].pos].x=index;
}
sort(z,z+n);
//for(i=0;i<n;i++) printf("%d %d %I64d %I64d %d\n",z[i][0],z[i][1],hash[z[i][0]],hash[z[i][1]],z[i][2]);
//printf("-----------\n");
memset(tree,-1,sizeof(tree));
for(i=0;i<n;i++) insert(1,1,index-1,z[i].x,z[i].y-1,z[i].h);
ans=0;
query(1,1,index-1);
printf("%I64d\n",ans);
}
return 0;
}
第三份代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int a[100000],b[100000],len;
__int64 sum;
struct node
{
int l,r,h;
}t[400000],p[100000];
bool cmp(node Q,node P)
{
return Q.h<P.h;
};
void build(int root,int l,int r)
{
t[root].l=l,t[root].r=r,t[root].h=0;
if(r-l==1)return ;
int mid=(l+r)>>1;
build(root<<1,l,mid);
build(root<<1|1,mid,r);
}
void insert(int root,int l,int r,int h)
{
if(l==t[root].l&&t[root].r==r)
{
t[root].h=h;
return;
}
if(t[root].h>0)
{
t[root<<1].h=t[root].h;
t[root<<1|1].h=t[root].h;
t[root].h=0;
}
int mid=(t[root].l+t[root].r)>>1;
// if(r>mid)insert(root<<1|1,l,r,h);
// if(l<mid)insert(root<<1,l,r,h);
if(r<=mid)insert(root<<1,l,r,h);
else if(l>=mid)insert(root<<1|1,l,r,h);
else
{
insert(root<<1,l,mid,h);
insert(root<<1|1,mid,r,h);
}
}
void search(int root)
{
if(t[root].h>0)
{
sum+=(__int64)(b[t[root].r]-b[t[root].l])*t[root].h;
return;
}
if(t[root].r-t[root].l==1)return ;
search(root<<1);
search(root<<1|1);
}
void div(int u)
{
int i;
sort(a+1,a+u);
b[1]=a[1],len=1;
for(i=2,len=2;i<u;i++)
{
if(a[i-1]!=a[i])
{
b[len]=a[i];
len+=1;
}
}
}
int find(int x)
{
int mid,l,r;
l=1;
r=len-1;
while(l<=r)
{
mid=(l+r)/2;
if(x<b[mid])r=mid-1;
else if(x>b[mid]) l=mid+1;
else return mid;
}
}
int main()
{
int n,i=1,j;
scanf("%d",&n);
for(j=0;j<n;j++)
{
scanf("%d%d%d",&p[j].l,&p[j].r,&p[j].h);
a[i++]=p[j].l;
a[i++]=p[j].r;
}
div(i);
build(1,1,len-1);
sort(p,p+n,cmp); //让高的后加，好覆盖前面低的。
for(i=0;i<n;i++){
insert(1,find(p[i].l),find(p[i].r),p[i].h);
}
sum=0;
search(1);
printf("%I64d\n",sum);
return 0;
}
第四份代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define MAX 40010
int a[MAX*2],turn;
struct rec{
int l,r;
int h;
}f[MAX];
struct ndoe{
int l,r;
int height;
int mid()
{
return (l+r)>>1;
}
}t[MAX*7];
bool cmp(rec x,rec y)
{
return x.h<y.h;
}
void build(int l,int r,int root)
{
t[root].l=l;
t[root].r=r;
t[root].height=-1;
if(l+1==r)
return ;
int mid=t[root].mid();
build(l,mid,root<<1);
build(mid,r,root<<1|1);
}
void insert(int l,int r,int root,int h)
{
if(t[root].height>=h)
return ;
if(l==t[root].l&&r==t[root].r)
{
if(t[root].height<h)
t[root].height=h;
return ;
}
if(t[root].height!=-1&&(t[root].l+1!=t[root].r))
{
t[root<<1].height=t[root<<1|1].height=t[root].height;
t[root].height=-1;
}
int mid=t[root].mid();
if(r<=mid)
insert(l,r,root<<1,h);
else if(l>=mid)
insert(l,r,root<<1|1,h);
else
{
insert(l,mid,root<<1,h);
insert(mid,r,root<<1|1,h);
}
}
__int64 query(int root)
{
if(t[root].l+1==t[root].r&&t[root].height<0)
return 0;
if(t[root].height>0)
return t[root].height*(__int64)(a[t[root].r]-a[t[root].l]);
else
return query(root<<1)+query(root<<1|1);
}
int bsearch(int x)
{
int left=0,right=turn-1;
while(left<=right)
{
int mid=(left+right)>>1;
if(a[mid]==x)
return mid;
else if(a[mid]>x)
right=mid-1;
else
left=mid+1;
}
return -1;
}
int main()
{
int n,i,x,y,z;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
{
scanf("%d%d%d",&x,&y,&z);
f[i].l=x;f[i].r=y;f[i].h=z;
a[i*2]=f[i].l;
a[i*2+1]=f[i].r;
}
sort(a,a+2*n);
sort(f,f+n,cmp);
turn=1;
for(i=1;i<2*n;i++)
{
if(a[i]!=a[i-1])
a[turn++]=a[i];
}
//printf("%d\n",turn);
build(0,turn-1,1);
for(i=0;i<n;i++)
{
// printf("%d %d %d\n",bsearch(f[i].l),bsearch(f[i].r),f[i].h);
insert(bsearch(f[i].l),bsearch(f[i].r),1,f[i].h);
}
__int64 ans;
ans=query(1);
printf("%I64d\n",ans);
}
return 0;
}
第五份代码：
#pragma warning (disable:4786)
#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <map>
#include <math.h>
#include <queue>
#include <stack>
#include <list>
#include <deque>
#include <set>
#include <numeric>
#include <functional>
#include <ctype.h>
#include <utility>
#include <cassert>
#include <time.h>
using namespace std;
#define Maxn 100010
__int64 ans=0;
__int64 v[500000];
__int64 xx[1000000];
struct no
{
int a;int b;
int hi;
}s[Maxn];
struct node
{
__int64 pos;
int num;
}a[1000000];
bool cmp1(struct node a,struct node b)
{
return a.pos<b.pos;
}
bool cmp2(struct node a,struct node b)
{
return a.num<b.num;
}
struct node1
{
__int64 h;
int l,r;
__int64 lv,rv;
}T[Maxn*4];
void Build(int l,int r,int root)
{
T[root].l=l;
T[root].r=r;
T[root].h=0;
if(r-l==1)
{
T[root].lv=xx[l];
T[root].rv=xx[r];
return;
}
int Mid=(l+r)/2;
Build(l,Mid,root*2);
Build(Mid,r,root*2+1);
}
void addadd(__int64 w,int l,int r,int root)
{
if(l==T[root].l&&r==T[root].r)
{
// printf("*********\n");
if(T[root].h<w)
T[root].h=w;
return;
}
int Mid=(T[root].l+T[root].r)/2;
if(r<=Mid)
{
addadd(w,l,r,root*2);
}
else if(l>=Mid)
{
addadd(w,l,r,root*2+1);
}
else
{
addadd(w,l,Mid,root*2);
addadd(w,Mid,r,root*2+1);
}
}
void querysum(int h,int root)
{
if(h>T[root].h)
T[root].h = h;
if(T[root].l +1 == T[root].r)
{
ans+=T[root].h *(xx[T[root].r] - xx[T[root].l]);
return ;
}
querysum(T[root].h,2*root);
querysum(T[root].h,2*root+1);
}
int main()
{
int n,i;
scanf("%d",&n);
for(i=0;i<n;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
if(x>y)
{
int temp=x;
x=y;
y=temp;
}
s[i].a=x;
s[i].b=y;
s[i].hi=z;
a[i*2].pos=s[i].a;
a[i*2].num=-(i+1);
a[i*2+1].pos=s[i].b;
a[i*2+1].num=i+1;
}
sort(a,a+2*n,cmp1);
int tp=1;
int temp=a[0].pos;
for(i=0;i<2*n;i++)
{
if(a[i].pos!=temp)
{
tp++;
temp=a[i].pos;
}
if(a[i].num<0)
{
xx[tp]=s[-a[i].num-1].a;
s[-a[i].num-1].a=tp;
}
else
{
xx[tp]=s[a[i].num-1].b;
s[a[i].num-1].b=tp;
}
}
// printf("k=%d\n",tp);
Build(1,tp,1);
sort(a,a+2*n,cmp2);
for(i=0;i<n;i++)
addadd(s[i].hi,s[i].a,s[i].b,1);
querysum(0,1);
printf("%I64d\n",ans);
return 0;
}
