WA 求助
查看原帖
WA 求助
556362
Unnamed114514楼主2022/12/17 15:22
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+5,inf=1e9,maxk=5e6+5;
int n,ans,bef,num,a[maxn],b[maxn],c[maxn],d[maxn];
inline int read(){
	int res=0,f=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		f|=(ch=='-');
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		res=(res<<1)+(res<<3)+(ch^'0');
		ch=getchar();
	}
	return f?-res:res;
}
struct ask{
	int p,l,r,v;
	inline bool operator <(const ask &o) const{
		return p<o.p||(p==o.p&&v<o.v);
	}
}N[maxn<<1];
struct ST{
	int l,r,ls,rs,sum,tag;
}t[maxk];
inline void pushdown(int p,int l,int r){
	int mid=l+r>>1;
	if(!t[p].ls)
		t[p].ls=++num,t[t[p].ls].l=l,t[t[p].ls].r=mid;
	if(!t[p].rs)
		t[p].rs=++num,t[t[p].rs].l=mid+1,t[t[p].rs].r=r;
	t[t[p].ls].sum+=t[p].tag*(t[t[p].ls].r-t[t[p].ls].l+1);
	t[t[p].ls].tag+=t[p].tag;
	t[t[p].rs].sum+=t[p].tag*(t[t[p].rs].r-t[t[p].rs].l+1);
	t[t[p].rs].tag+=t[p].tag;
}
void Add(int p,int l,int r,int v){
	if(l<=t[p].l&&t[p].r<=r){
		t[p].sum+=v*(t[p].r-t[p].l+1);
		t[p].tag+=v;
		return;
	}
	pushdown(p,t[p].l,t[p].r);
	if(l<=t[t[p].ls].r)
		Add(t[p].ls,l,r,v);
	if(t[t[p].rs].l<=r)
		Add(t[p].rs,l,r,v);
	t[p].sum=t[t[p].ls].sum+t[t[p].rs].sum;
}
signed main(){
	n=read();
	for(int i=1;i<=n;++i){
		a[i]=read(),b[i]=read(),c[i]=read(),d[i]=read();
		N[i]=ask({b[i],a[i],c[i],1});
		N[i+n]=ask({d[i]+1,a[i],c[i],-1});
	}
	sort(N+1,N+2*n+1);
	num=1,t[1].l=1,t[1].r=inf;
	for(int i=1;i<=2*n;++i){
		ans+=t[1].sum*(N[i].p-N[i-1].p);
		Add(1,N[i].l,N[i].r,N[i].v);
	}
	printf("%lld\n",ans);
	return 0;
}
2022/12/17 15:22
加载中...