zerojudge e886: Q4 覆蓋總面積
這題要用線段樹才能達到題目要的複雜度我debug很久了還是過不了
用的是 線段樹+掃描線
code如下:
#include <bits/stdc++.h>
using namespace std;
struct COOR{
int l,r,h,status;
};
struct Node{
int l,r;
int cov;
int len = 0;
}tree;
COOR coor;
int x;
int n;
bool cmp(COOR a,COOR b){
return a.h < b.h;
}
void build(int idx,int l,int r){
tree.l = l;
tree.r = r;
tree.cov = 0;
tree.len = 0;
if(l == r-1)
return;
int mid = (l+r)/2;
build(idx*2+1,l,mid);
build(idx*2+2,mid,r);
return;
}
void pushup(int idx){
if(tree.cov)
tree.len = x.r] - x.l];
else
tree.len = tree.len + tree.len;
}
void update(int idx,int st,int en,int covNum){
int l = tree.l;
int r = tree.r;
if(l == r-1){
if(st<=l && r<=en){
tree.cov += covNum;
pushup(idx);
}
return;
}
int mid = (l+r)/2;
if(mid > st) update(idx*2+1,st,en,covNum);
if(mid < en) update(idx*2+2,st,en,covNum);
pushup(idx);
return;
}
int main(){
cin.tie(0);
int n=0;
cin >> n; //測試用
int ptr,ptrI;
ptr = ptrI = 0;
int xI,xII,yI,yII;
/*while(scanf("%d %d %d %d",&xI,&yI,&xII,&yII) != EOF){
coor.l = xI , coor.r = xII;
coor.h = yI , coor.status = 1;
ptr++;
coor.l = xI , coor.r = xII;
coor.h = yII , coor.status = -1;
ptr++;
x = xI;
x = xII;
}*/
for(int i=0 ; i<n ; i++){ //測試用
cin >> xI >> yI >> xII >> yII;
coor.l = xI , coor.r = xII;
coor.h = yI , coor.status = 1;
ptr++;
coor.l = xI , coor.r = xII;
coor.h = yII , coor.status = -1;
ptr++;
x = xI;
x = xII;
}
sort(coor,coor+ptr,cmp);
sort(x,x+ptrI);
ptrI = unique(x,x+ptrI)-x;
build(0,0,ptrI-1);
long long ans = 0;
for(int i=0 ; i<ptr-1 ; i++){
int st = lower_bound(x,x+ptrI,coor.l)-x;
int en = lower_bound(x,x+ptrI,coor.r)-x;
update(0,st,en,coor.status);
ans += ((long long)(coor.h-coor.h))*((long long)tree.len);
}
cout << ans << "\n";
}
求解...
頁:
[1]