C31 扫描线 P1856 [IOI1998] 矩形周长

#include<bits/stdc++.h>
#define lc (p<<1)
#define rc (p<<1|1)
#define mid ((tr[p].l+tr[p].r)>>1)
using namespace std;
const int N=1e5+10;
struct Line{int p,st,ed,flg; }L[N],L1[N],L2[N];// 一条竖线：x坐标是p，y的范围是st至ed 
int cmp(Line n1,Line n2){return n1.p<n2.p;} 
int lsh[N],lsh1[N],lsh2[N];
struct trnode{int l,r,c,len;}tr[N<<3];
void bt(int p,int l,int r)
{
	tr[p]=trnode{l,r,0,0};
	if(l+1==r)return ;
	bt(lc,l,mid);
	bt(rc,mid,r);
}
void change(int p,int l,int r,int c)
{
	if(r<=lsh[tr[p].l] || lsh[tr[p].r]<=l)return;
	if(l<=lsh[tr[p].l] && lsh[tr[p].r]<=r)tr[p].c+=c;
	else change(lc,l,r,c),change(rc,l,r,c);
	tr[p].len= tr[p].c>0? (lsh[tr[p].r]-lsh[tr[p].l]) : (tr[lc].len+tr[rc].len) ;//pushup 
}
int main()
{
	int n,ln;scanf("%d",&n);
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		int X1,Y1,X2,Y2;scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2);
		L1[i]  =Line{X1,Y1,Y2, 1};
		L1[n+i]=Line{X2,Y1,Y2,-1};
		lsh1[i]=Y1,lsh1[n+i]=Y2;
		
		L2[i]  =Line{Y1,X1,X2, 1};
		L2[n+i]=Line{Y2,X1,X2,-1};
		lsh2[i]=X1,lsh2[n+i]=X2;
	}
	
	memcpy(lsh,lsh1,sizeof(lsh));memcpy(L,L1,sizeof(L));
	sort(lsh+1,lsh+2*n+1);ln=unique(lsh+1,lsh+2*n+1)-lsh-1;
	bt(1,1,ln);
	sort(L+1,L+2*n+1,cmp);
	for(int i=1,lastlen=0;i<=2*n;i++)
	{
		change(1,L[i].st,L[i].ed,L[i].flg);
		ans+=abs(tr[1].len-lastlen);lastlen=tr[1].len;
	}
	
	memcpy(lsh,lsh2,sizeof(lsh));memcpy(L,L2,sizeof(L));
	sort(lsh+1,lsh+2*n+1);ln=unique(lsh+1,lsh+2*n+1)-lsh-1;
	bt(1,1,ln);
	sort(L+1,L+2*n+1,cmp);
	for(int i=1,lastlen=0;i<=2*n;i++)
	{
		change(1,L[i].st,L[i].ed,L[i].flg);
		ans+=abs(tr[1].len-lastlen);lastlen=tr[1].len;
	}
		
	printf("%d\n",ans);
	return 0;
}

C31 扫描线 P1856 [IOI1998] 矩形周长

#include<bits/stdc++.h>
#define lc (p<<1)
#define rc (p<<1|1)
#define mid ((tr[p].l+tr[p].r)>>1)
using namespace std;
const int N=1e5+10;
struct Line{int p,st,ed,flg; }L[N],L1[N],L2[N];// 一条竖线：x坐标是p，y的范围是st至ed 
int cmp(Line n1,Line n2){return n1.p<n2.p;} 
int lsh[N],lsh1[N],lsh2[N];
struct trnode{int l,r,c,len;}tr[N<<3];
void bt(int p,int l,int r)
{
	tr[p]=trnode{l,r,0,0};
	if(l+1==r)return ;
	bt(lc,l,mid);
	bt(rc,mid,r);
}
void change(int p,int l,int r,int c)
{
	if(r<=lsh[tr[p].l] || lsh[tr[p].r]<=l)return;
	if(l<=lsh[tr[p].l] && lsh[tr[p].r]<=r)tr[p].c+=c;
	else change(lc,l,r,c),change(rc,l,r,c);
	tr[p].len= tr[p].c>0? (lsh[tr[p].r]-lsh[tr[p].l]) : (tr[lc].len+tr[rc].len) ;//pushup 
}
int main()
{
	int n,ln;scanf("%d",&n);
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		int X1,Y1,X2,Y2;scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2);
		L1[i]  =Line{X1,Y1,Y2, 1};
		L1[n+i]=Line{X2,Y1,Y2,-1};
		lsh1[i]=Y1,lsh1[n+i]=Y2;
		
		L2[i]  =Line{Y1,X1,X2, 1};
		L2[n+i]=Line{Y2,X1,X2,-1};
		lsh2[i]=X1,lsh2[n+i]=X2;
	}
	
	memcpy(lsh,lsh1,sizeof(lsh));memcpy(L,L1,sizeof(L));
	sort(lsh+1,lsh+2*n+1);ln=unique(lsh+1,lsh+2*n+1)-lsh-1;
	bt(1,1,ln);
	sort(L+1,L+2*n+1,cmp);
	for(int i=1,lastlen=0;i<=2*n;i++)
	{
		change(1,L[i].st,L[i].ed,L[i].flg);
		ans+=abs(tr[1].len-lastlen);lastlen=tr[1].len;
	}
	
	memcpy(lsh,lsh2,sizeof(lsh));memcpy(L,L2,sizeof(L));
	sort(lsh+1,lsh+2*n+1);ln=unique(lsh+1,lsh+2*n+1)-lsh-1;
	bt(1,1,ln);
	sort(L+1,L+2*n+1,cmp);
	for(int i=1,lastlen=0;i<=2*n;i++)
	{
		change(1,L[i].st,L[i].ed,L[i].flg);
		ans+=abs(tr[1].len-lastlen);lastlen=tr[1].len;
	}
		
	printf("%d\n",ans);
	return 0;
}