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[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";
}

求解...