扫描线模板,我的写法应该已经是正解了,可是3-10全部TLE,是因为常熟太大,还是存在更优解?求助
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1000005;
int n;
long long x1,x2,y1,y2;
int X[maxn<<1];
long long ans;
inline int read(){
int ret=0;
int f=1;
char c=getchar();
while(c<'0' || c>'9'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0' && c<='9'){
ret=ret*10+c-'0';
c=getchar();
}
return ret*f;
}
struct scan_line{
long long l,r,y; //扫描线的左端点、右端点和纵坐标
int val; //扫描线的权值(1/-1)
}l[maxn<<1];
struct segment_tree{
int l,r;
int sum;
long long len;
}t[maxn<<2];
bool cmp(scan_line x,scan_line y){
return x.y<y.y;
}
void push_up(int pos){
int l=t[pos].l,r=t[pos].r;
if(t[pos].sum){
t[pos].len=X[r+1]-X[l];
}
else{
t[pos].len=t[pos<<1].len+t[pos<<1|1].len;
}
}
void build(int pos,int l,int r){
t[pos].l=l; t[pos].r=r;
if(l==r) return;
int mid=(l+r)/2;
build(pos<<1,l,mid);
build(pos<<1|1,mid+1,r);
push_up(pos);
}
void modify(int pos,int x,int y,int delta){
int l=t[pos].l,r=t[pos].r;
int xl=X[l],xr=X[r+1];
if(xr<=x || y<=xl) return;
if(x<=xl && xr<=y){
t[pos].sum+=delta;
push_up(pos);
}
modify(pos<<1,x,y,delta);
modify(pos<<1|1,x,y,delta);
push_up(pos);
}
int main(){
n=read();
for(int i=1;i<=n;i++){
x1=(long long)(read()); y1=(long long)(read()); x2=(long long)(read()); y2=(long long)(read());
X[2*i-1]=x1; X[2*i]=x2;
l[2*i-1]=scan_line{x1,x2,y1,1};
l[2*i]=scan_line{x1,x2,y2,-1};
}
n<<=1;
sort(l+1,l+n+1,cmp);
sort(X+1,X+n+1);
int k=unique(X,X+n+1)-X-1;
build(1,1,k-1);
for(int i=1;i<n;i++){
modify(1,l[i].l,l[i].r,l[i].val);
ans+=t[1].len*(l[i+1].y-l[i].y);
}
printf("%lld\n",ans);
return 0;
}