为什么有的题需要pushup,有的题不需要
查看原帖
为什么有的题需要pushup,有的题不需要
795784
zxh923楼主2024/11/29 20:47

这题的代码:

#include<bits/stdc++.h> 
#define int long long
#define N 100005
#define pii pair<int,int>
#define x first
#define y second
#define pct __builtin_popcount
#define mod 7
#define pi acos(-1)
#define inf 2e18
#define eps 1e-8
using namespace std;
int T=1,n,w,h,x[N<<1];
struct line{
    int l,r,h,flag;
    bool operator<(const line &t)const{
        return h<t.h;
    }
}l[N<<1];
struct sgt{
    struct node{
        int l,r,sum,len;
    }tr[N<<4];
    void pushup(int u){
    	int l=tr[u].l,r=tr[u].r;
    	if(tr[u].sum!=0)tr[u].len=x[r+1]-x[l];
    	else tr[u].len=tr[u<<1].len+tr[u<<1|1].len;
    }
    void build(int u,int l,int r){
        tr[u]={l,r,0,0};
        if(l==r)return;
        int mid=l+r>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
        pushup(u);
    }
    void modify(int u,int L,int R,int v){
        int l=tr[u].l,r=tr[u].r;
        if(l>=L&&r<=R){
            tr[u].sum+=v;
            tr[u].len+=v;
            pushup(u);
            return;
        }
        int mid=l+r>>1;
        if(L<=mid)modify(u<<1,L,R,v);
        if(R>mid)modify(u<<1|1,L,R,v);
        pushup(u);
    }
}s;
void solve(int cs){
    cin>>n;
    for(int i=1;i<=n;i++){
        int x_1,y_1,x_2,y_2;
        cin>>x_1>>y_1>>x_2>>y_2;
        x[i*2-1]=x_1;x[i*2]=x_2;
        l[i*2-1]={x_1,x_2,y_1,1};
        l[i*2]={x_1,x_2,y_2,-1};
    }
    n<<=1;
    sort(x+1,x+n+1);
    sort(l+1,l+n+1);
    int tot=unique(x+1,x+n+1)-x-1;
    for(int i=1;i<=n;i++){
        l[i].l=lower_bound(x+1,x+tot+1,l[i].l)-x;
        l[i].r=lower_bound(x+1,x+tot+1,l[i].r)-x;
    }
    s.build(1,1,tot-1);
    int res=0;
    for(int i=1;i<n;i++){
        s.modify(1,l[i].l,l[i].r-1,l[i].flag);
        res+=s.tr[1].len*(l[i+1].h-l[i].h);
    }
    cout<<res<<'\n';
}
void solution(){
    /*
    nothing here
    */
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//  init();
//  cin>>T;
    for(int cs=1;cs<=T;cs++){
        solve(cs);
    }
    return 0;
}

modify 函数内的第一个 if 就需要 pushup,但是窗口的星星那题就不能 pushup。想问下怎么判断要不要 pushup?

2024/11/29 20:47
加载中...