80pts WA#3#10求助
查看原帖
80pts WA#3#10求助
218752
smy2006楼主2022/7/25 20:38
#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int q=0;char ch=' ';
	while(ch<'0' || ch>'9') ch=getchar();
	while(ch<='9' && ch>='0') q=q*10+ch-'0',ch=getchar();
	return q;
}

const int MAXN = 2e6+15;
int n,a,b,k,ranks[MAXN];
struct Sl{
	int val,num;
}X[MAXN];
struct Line{
	int l,r,w,y;
}sq[MAXN];
inline bool cmp1(Sl x,Sl y){ return x.val<y.val;}
inline bool cmp2(Line x,Line y){ return x.y<y.y;}
struct Segment_Tree{
	int minn,num,len,tag;
}tre[MAXN];
void build(int l,int r,int p){
	if(l==r){ tre[p].len=X[l+1].val-X[l].val;return;}
	int mid=(l+r)>>1;
	build(l,mid,p*2);build(mid+1,r,p*2+1);
	tre[p].len=tre[p*2].len+tre[p*2+1].len;return;
}
inline void push_down(int l,int r,int p){
	if(tre[p].tag==0) return;
	int mid=(l+r)>>1;
	tre[p*2].minn+=tre[p].tag;tre[p*2+1].minn+=tre[p].tag;
	tre[p*2].tag+=tre[p].tag;tre[p*2+1].tag+=tre[p].tag;
	tre[p].tag=0;return;
}
void change(int l,int r,int p){
	if(a<=l && r<=b){
		tre[p].minn+=k;tre[p].tag+=k;return;
	}
	push_down(l,r,p);int mid=(l+r)>>1;
	if(a<=mid) change(l,mid,p*2);
	if(b>mid) change(mid+1,r,p*2+1);
	if(tre[p*2].minn==tre[p*2+1].minn){
		tre[p].minn=tre[p*2].minn,tre[p].num=tre[p*2].num+tre[p*2+1].num;
	}else if(tre[p*2].minn<tre[p*2+1].minn){
		tre[p].minn=tre[p*2].minn,tre[p].num=tre[p*2].num;
	}else{
		tre[p].minn=tre[p*2+1].minn,tre[p].num=tre[p*2+1].num;
	}
	return;
}
long long query(int l,int r,int p){
	if(l==r){
		return tre[p].minn*tre[p].len;
	}
	push_down(l,r,p);
	if(tre[p].minn!=0) return tre[p].len;
	long long cnt=0;int mid=(l+r)>>1;
	cnt=query(l,mid,p*2)+query(mid+1,r,p*2+1);
	return cnt;
}

signed main(){
	freopen("data.txt","r",stdin);
	freopen("mycpp.txt","w",stdout);
	n=read();
	for(int i=1; i<=n; i++){
		int x1=read(),y1=read(),x2=read(),y2=read();
		sq[i].l=i,sq[i].r=i+n,sq[i].w=1,sq[i].y=y1;
		sq[i+n].l=i,sq[i+n].r=i+n,sq[i+n].w=-1,sq[i+n].y=y2;
		X[i].val=x1,X[i+n].val=x2,X[i].num=i,X[i+n].num=i+n;
	}
	sort(X+1,X+2*n+1,cmp1);sort(sq+1,sq+2*n+1,cmp2);
	for(int i=1; i<=2*n; i++) ranks[X[i].num]=i;
	build(1,2*n-1,1);
	long long ans=0,crslen=0,higlen=0;
	for(int i=1; i<=2*n; i++){
		a=ranks[sq[i].l],b=ranks[sq[i].r]-1,k=sq[i].w;
		change(1,2*n-1,1);
		ans+=1ll*crslen*(sq[i].y-higlen);
		crslen=query(1,n*2-1,1),higlen=sq[i].y;
	}
	cout<<ans<<endl;
}
2022/7/25 20:38
加载中...