冰楓論壇

 找回密碼
 立即註冊
搜索
查看: 380|回覆: 0

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

[複製鏈接]

12

主題

0

好友

13

積分

新手上路

Rank: 1

UID
276768
帖子
27
主題
12
精華
0
積分
13
楓幣
363
威望
13
存款
0
贊助金額
0
推廣
0
GP
82
閱讀權限
10
性別
保密
在線時間
3 小時
註冊時間
2020-2-5
最後登入
2021-10-6
發表於 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";
}

求解...




複製連結並發給好友,以賺取推廣點數
簡單兩步驟,註冊、分享網址,即可獲得獎勵! 一起推廣文章換商品、賺$$
高級模式
B Color Image Link Quote Code Smilies |上傳

正在連接伺服器...
打開冰楓聊天室
廣告刊登意見回饋關於我們職位招聘本站規範DMCA隱私權政策

Copyright © 2011-2022 冰楓論壇, All rights reserved

免責聲明:本網站是以即時上載留言的方式運作,本站對所有留言的真實性、完整性及立場等,不負任何法律責任。

而一切留言之言論只代表留言者個人意見,並非本網站之立場,用戶不應信賴內容,並應自行判斷內容之真實性。

小黑屋|手機版|冰楓論壇

GMT+8, 2022-8-19 12:44

APP Store下載 Play Store下載
回頂部