蒟蒻
查看原帖
蒟蒻
479448
fire_and_sweets楼主2022/6/30 18:31

我很是个蒟蒻! 这题好难(大佬勿喷),我看不出来错在哪里...

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
#define LCD (rt<<1)
#define RCD ((rt<<1)|1)
#define MID (l+r)>>1
int n,m; //m -> 新的n 
const int N=1000111;
const int M=2000111;
struct xd{
	int x,l,r;
	int t,newl,newr;
} LSH[N];
bool cmp(xd xd1, xd xd2){
	if(xd1.x!=xd2.x) return xd1.x<xd2.x;
	else return xd1.t>xd2.t;
}
struct node{ //st表 
	int minn, minn_num,tag;
	int len,L;	
} st[M];
double nums[M];
inline int read(){
	int FF=1,RR=0;
	char ch=getchar();
	while(!isdigit(ch)){
		FF=(ch=='-'?-1:1);
		ch=getchar();
	}
	while(isdigit(ch)){
		RR=(RR<<1)+(RR<<3)+(ch^48);
		ch=getchar();
	}
	return FF*RR;
}
void pushdown(int rt){
	int d=st[rt].tag;
	st[rt].tag=0;
	st[LCD].tag+=d;
	st[RCD].tag+=d;
	st[LCD].minn+=d;
	st[RCD].minn+=d;
}
void update(node *s1,node s2,node s3){ //刷新一下 
	s1->minn=min(s2.minn,s3.minn);//指针写法 
	s1->minn_num=0;
	if(s1->minn==s2.minn) s1->minn_num+=s2.minn_num;
	if(s1->minn==s3.minn) s1->minn_num+=s3.minn_num;
}
void build(int rt,int l,int r){
	st[rt].tag=0;
	if(l==r){
		st[rt].len=0;
		st[rt].minn=0;
		st[rt].minn_num=nums[l+1]-nums[l];
		st[rt].L=nums[l+1]-nums[l];
		return;
	}
	int mid=MID;
	build(LCD,l,mid);
	build(RCD,mid+1,r);
	st[rt].L=st[LCD].L + st[RCD].L;
	update(&st[rt],st[LCD],st[RCD]);
}
void modify(int rt,int l,int r,int x,int y,int d){
	if(x<=l&&r<=y){
		st[rt].minn+=d;
		st[rt].tag+=d;
		return;
	}
	pushdown(rt);
	int mid=MID;
	if(x<=mid)modify(LCD,l,mid,x,y,d);
	if(y>mid)modify(RCD,mid+1,r,x,y,d);
	update(&st[rt],st[LCD],st[RCD]);
}
int ans(){
	for(int i=1;i<=n;i++){
		int X1,Y1,X2,Y2;
		scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2);
		LSH[i*2-1]=(xd){X1,Y1,Y2,1};
		LSH[i*2]=(xd){X2,Y1,Y2,-1};
		nums[i*2-1]=Y1;//左儿子 
		nums[i*2]=Y2;//右儿子 
	}
	sort(nums+1,nums+1+2*n);
	m=unique(nums+1,nums+1+2*n)-nums-1;//去重 
	for(int i=1;i<=2*n;i++){
		LSH[i].newl=lower_bound(nums+1,nums+m+1,LSH[i].l)-nums;
		LSH[i].newr=lower_bound(nums+1,nums+m+1,LSH[i].r)-nums;
	} 
	sort(LSH+1,LSH+1+2*n,cmp);//命令数组排序 
	m = m - 1;//点 -> 线+1
	build(1,1,m); //建树
	
	int ret=0;
	for(int i=1;i<=2*n;i++){
		int d=LSH[i].x-LSH[i-1].x;
		if(st[1].minn==0)
			ret+=d*(st[1].L-st[1].minn_num); 
		else ret+=d*st[1].L;//minn_num -> minn出现的个数
		modify(1,1,m,LSH[i].newl,LSH[i].newr-1,LSH[i].t); //区间修改 
	}
	return ret; 
}
signed main(){
	n=read();
	cout<<ans()<<endl;
	return 0;
}

样例输出了21810316375480060,为什么?

2022/6/30 18:31
加载中...