不写注释真的是 泰裤辣！
原题链接：823.Paint by Rectangles--Platinum
2023-07-16 18:33:05
发布于：广东
#include<bits/stdc++.h>
using namespace std;
#define F(i,a,b) for(int i=a;i<=b;i++)
#define Fd(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
#define N 200010
LL X,C,F,B;
int n,T,L[N],R[N],op[N],f[N],col[N];
struct node{int lx,ly,rx,ry;}a[N];
int find(int x){return f[x]==x?x:(f[x]=find(f[x]));}
void merge(int x,int y){int A=find(x),B=find(y);if(A!=B)f[A]=B;}
struct tree{
#define ls x<<1
#define rs (x<<1)|1
int tag[N4],sum[N4];
void pushdown(int x){
if(!tag[x])return;
if(sum[ls]){
if(!tag[ls])tag[ls]=tag[x];
else merge(tag[ls],tag[x]);
}
if(sum[rs]){
if(!tag[rs])tag[rs]=tag[x];
else merge(tag[rs],tag[x]);
}
tag[x]=0;
}
void pushup(int x){sum[x]=sum[ls]+sum[rs];}
void modify(int x,int l,int r,int ll,int rr,int pos){
if(r<ll||l>rr)return;
if(l>=ll&&r<=rr){
if(!sum[x])return;
if(!tag[x])tag[x]=pos;
else merge(tag[x],pos);
return;
}
int mid=l+r>>1;
pushdown(x);
modify(ls,l,mid,ll,rr,pos);modify(rs,mid+1,r,ll,rr,pos);
pushup(x);
}
void change(int x,int l,int r,int k,int pos){
if(lr){
if(k1)sum[x]++;
else sum[x]--,tag[x]=0;
return;
}
int mid=l+r>>1;
pushdown(x);
pos<=mid?change(ls,l,mid,k,pos):change(rs,mid+1,r,k,pos);
pushup(x);
}
int query(int x,int l,int r,int ll,int rr){
if(r<ll||l>rr)return 0;
if(l>=ll&&r<=rr)return sum[x];
int mid=l+r>>1;
return query(ls,l,mid,ll,rr)+query(rs,mid+1,r,ll,rr);
}
}t;
vector<int>S[N];
int main(){
scanf("%d%d",&n,&T);
F(i,1,n){
f[i]=i;
scanf("%d%d%d%d",&a[i].lx,&a[i].ly,&a[i].rx,&a[i].ry);
op[a[i].lx]=i;op[a[i].rx]=-i;
L[a[i].lx]=L[a[i].rx]=a[i].ly;R[a[i].lx]=R[a[i].rx]=a[i].ry;
}
F(i,1,2n){
if(op[i]>0){
t.change(1,1,n2,1,L[i]);t.change(1,1,n2,1,R[i]);
t.modify(1,1,n2,L[i],R[i],op[i]);
int q=t.query(1,1,n2,L[i]+1,R[i]-1),d=t.query(1,1,n2,1,L[i]-1)+1;
d&1?B+=(q>>1)+1:B+=q+1>>1;
X+=q;
col[i]=d&1;
}else{
t.change(1,1,n2,-1,L[i]);t.change(1,1,n2,-1,R[i]);
t.modify(1,1,n2,L[i],R[i],-op[i]);
int q=t.query(1,1,n2,L[i]+1,R[i]-1);
int u=t.query(1,1,n2,R[i]+1,n2)+1,d=t.query(1,1,n2,1,L[i]-1)+1;
// Black 1,White 0
if((d&1)&&(u&1))B+=q>>1;
else if(!(d&1)&&!(u&1))B+=(q>>1)-1;
else B+=(q+1>>1)-1;
X+=q;
}
}
F(i,1,n){if(find(i)==i)C++;S[find(i)].push_back(a[i].lx);}
F(i,1,n)if(find(i)==i){
int tx=n2+1,pos;
for(auto d:S[i])if(d<tx)tx=d,pos=d;
if(!col[pos])B++;
}
F=X+C+1;
if(T==1)printf("%lld",F);
else printf("%lld %lld",F-B,B);
return 0;
}
有帮助，赞一个