社区讨论

求助,全wa了。。。

P5490【模板】扫描线 & 矩形面积并参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lo2k28s6
此快照首次捕获于
2023/10/23 15:07
2 年前
此快照最后确认于
2023/10/23 15:07
2 年前
查看原帖
CPP
#include <bits/stdc++.h>
#define lid (id<<1)
#define rid ((id<<1)+1)
#define ll long long
using namespace std;
const int MAXN=300005;
int n;
struct Seg_tree{
    int l,r,len;
    int cnt;
}tree[8*MAXN];
struct rect{
    int x,y2,y3,flg;
}L[MAXN];
int Y[MAXN]; 
ll ans;

void build(int id,int from,int to){
	if(from>=to) return;
    tree[id].l=Y[from],tree[id].r=Y[to];
    tree[id].len=(tree[id].r-tree[id].l+1);
    int mid=(from+to)>>1;
    //cout<<id<<" "<<tree[id].l<<" "<<tree[id].r<<" "<<from<<" "<<to<<" "<<mid<<endl;
    if(from==to-1) return;
    build(lid,from,mid);
    build(rid,mid,to);
}

void pushup(int id){
    if(tree[id].cnt!=0) tree[id].len=tree[id].r-tree[id].l;
    else tree[id].len=tree[lid].len+tree[rid].len;
}
void change(int id,int from,int to,int key){
    if(from>=tree[id].r||to<=tree[id].l) return;
    if((from<=tree[id].l)&&(to>=tree[id].r)){
        tree[id].cnt+=key;
        pushup(id);
        return;
    }
    change(lid,from,to,key);
    change(rid,from,to,key);
    pushup(id);
}
bool cmp1(rect xx,rect yy){
    return xx.x<yy.x;
}
void input(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int x2,x3,y2,y3;
        scanf("%d%d%d%d",&x2,&y2,&x3,&y3);
        L[i]={x2,y2,y3,1},L[i+n]={x3,y2,y3,-1};
        Y[i]=y2,Y[i+n]=y3;
    }
    n*=2;
}
int main()
{
    input();
    sort(L+1,L+n+1,cmp1);
    sort(Y+1,Y+n+1);
    build(1,1,n);
    for(int i=1;i<n;i++){
        change(1,L[i].y2,L[i].y3,L[i].flg);
        //cout<<(L[i+1].x-L[i].x)<<"*"<<(tree[1].len)<<endl;
        ans+=1ll*(L[i+1].x-L[i].x)*(tree[1].len);
    }
    printf("%lld\n",ans);
    
    
    

    return 0;
}

回复

1 条回复,欢迎继续交流。

正在加载回复...