题目是扫描线,看清月的博客学习的。为什么MLE了5个点,样例还没输出???求助,谢谢。
#include<bits/stdc++.h>
#define lson id<<1
#define rson id<<1|1
#define mid (l+r)>>1
using namespace std;
struct edge{
int left,right,height,flag;
}e[100005];
struct segtree{
int sum,num,len;
bool lflag,rflag;
}tree[1000010];
int n,max_=-2147483647,min_=2147483647,cnt,ans,last;
void add1(int l,int r,int h,int f){
e[++cnt].left=l;
e[cnt].right=r;
e[cnt].height=h;
e[cnt].flag=f;
}
bool cmp(edge x,edge y){return x.height<y.height||x.height==y.height&&x.flag>y.flag;}
void pushup(int id,int l,int r){
if(tree[id].sum)
{
tree[id].num=1;
tree[id].len=r-l+1;
tree[id].lflag=tree[id].rflag=1;
}
else if(l==r)
{
tree[id].len=0;
tree[id].num=0;
tree[id].lflag=tree[id].rflag=0;
}
else
{
tree[id].len=tree[lson].len+tree[rson].len;
tree[id].num=tree[lson].num+tree[rson].num;
if(tree[lson].rflag&&tree[rson].lflag)tree[id].num--;
tree[id].lflag=tree[lson].lflag;
tree[id].rflag=tree[rson].rflag;
}
}
void add2(int id,int l,int r,int from,int to,int value)
{
if(l>=from&&r<=to)
{
tree[id].sum+=value;
pushup(id,l,r);
return;
}
if(from<=mid) add2(lson,l,mid,from,to,value);
if(to>mid) add2(rson,mid+1,r,from,to,value);
pushup(id,l,r);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
max_=max(max_,max(x1,x2));min_=min(min_,min(x1,x2));
add1(x1,x2,y1,1);add1(x1,x2,y2,-1);
}
if(min_<=0){
for(int i=1;i<=cnt;i++){
e[i].left+=-min_+1;e[i].right+=-min_+1;}
max_-=min_;
}
sort(e+1,e+cnt+1,cmp);
for(int i=1;i<=cnt;i++){
add2(1,1,max_,e[i].left,e[i].right-1,e[i].flag);
while(e[i].height==e[i+1].height&&e[i].flag==e[i+1].flag)
{i++;add2(1,1,max_,e[i].left,e[i].right-1,e[i].flag);}
ans+=abs(tree[1].len-last);
last=tree[1].len;
ans+=tree[1].num*2*(e[i+1].height-e[i].height);
}
printf("%d\n",ans);
return 0;
}