[求助] zerojudge e886: Q4 覆蓋總面積

[複製鏈接]

宇志王

12 主題	0 好友	13 積分

新手上路

Rank: 1

UID: 276768
帖子: 27
主題: 12
精華: 0
積分: 13
楓幣: 363
威望: 13
存款: 0
贊助金額: 0
推廣: 0
ＧＰ: 82
閱讀權限: 10
性別: 保密
在線時間: 3 小時
註冊時間: 2020-2-5
最後登入: 2021-10-6

發消息

電梯直達

1樓

發表於 2020-2-15 00:49:10 |只看該作者 |倒序瀏覽

這題要用線段樹才能達到題目要的複雜度

我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[1200005];

COOR coor[300005];
int x[300005];
int n;

bool cmp(COOR a,COOR b){
return a.h < b.h;
}

void build(int idx,int l,int r){
tree[idx].l = l;
tree[idx].r = r;
tree[idx].cov = 0;
tree[idx].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[idx].cov)
      tree[idx].len = x[tree[idx].r] - x[tree[idx].l];
else
      tree[idx].len = tree[idx*2+1].len + tree[idx*2+2].len;
}

void update(int idx,int st,int en,int covNum){
int l = tree[idx].l;
int r = tree[idx].r;
if(l == r-1){
      if(st<=l && r<=en){
         tree[idx].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[ptr].l = xI , coor[ptr].r = xII;
      coor[ptr].h = yI , coor[ptr].status = 1;
      ptr++;
      coor[ptr].l = xI , coor[ptr].r = xII;
      coor[ptr].h = yII , coor[ptr].status = -1;
      ptr++;
      x[ptrI++] = xI;
      x[ptrI++] = xII;
}*/

for(int i=0 ; i<n ; i++){ //測試用
      cin >> xI >> yI >> xII >> yII;
      coor[ptr].l = xI , coor[ptr].r = xII;
      coor[ptr].h = yI , coor[ptr].status = 1;
      ptr++;
      coor[ptr].l = xI , coor[ptr].r = xII;
      coor[ptr].h = yII , coor[ptr].status = -1;
      ptr++;
      x[ptrI++] = xI;
      x[ptrI++] = 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[i].l)-x;
      int en = lower_bound(x,x+ptrI,coor[i].r)-x;
      update(0,st,en,coor[i].status);
      ans += ((long long)(coor[i+1].h-coor[i].h))*((long long)tree[0].len);
}

cout << ans << "\n";
}

求解...

e886