我很是个蒟蒻! 这题好难(大佬勿喷),我看不出来错在哪里...
#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,为什么?