这题的代码:
#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?