【扫描线,线段树】样例RE求助
查看原帖
【扫描线,线段树】样例RE求助
481330
sunyizhe还是MC大佬楼主2023/2/21 21:37
//程序算法:线段树,扫描线
//-std=c++14 -O2 -Wall
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;

int n,l,r,tot,x[N];//tot记录去重后的线段数量,x记录所有点的x坐标 
struct Line{
	int l,r;
}line[N*2];//左右两条线,数组范围*2。 

struct Node{
	int l,r,cnt,len;
	//[l,r]区间;
	//cnt:被完全覆盖的次数; 
	//len:[l,r]区间cnt>0的数量;
}t[N*4];

//初始化cnt和len都为0.
void build(int rt,int l,int r)
{
    t[rt].l=l,t[rt].r=r;
	if(l==r)return;
	
	int mid=(l+r)>>1;
	build(rt*2,l,mid);
	build(rt*2,mid+1,r);	
}

//向上更新len。 
inline void pushup(int rt)
{
    if(t[rt].cnt)t[rt].len=x[t[rt].r+1]-x[t[rt].l];
    else if(t[rt].l==t[rt].r)t[rt].len=0;
    else t[rt].len=t[rt*2].len+t[rt*2+1].len;
} 

//将[l,r]加上v。 
void modify(int rt,int l,int r,int v)
{
	if(t[rt].l>=l&&t[rt].r<=r)
	{
		t[rt].cnt+=v;
		pushup(rt);
		return;
	}
	
	int mid=(l+r)>>1;
	if(l<=mid)modify(rt*2,l,r,v);
	if(r>mid)modify(rt*2+1,l,r,v);
	pushup(rt); 
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d %d",&l,&r);
		
		//入边扫描线
		x[++tot]=l;
		line[tot].l=l,line[tot].r=r;
		
		//出边扫描线
		x[++tot]=r;
		line[tot].l=l,line[tot].r=r; 
	}
	
	n=tot;
	sort(x+1,x+n+1);
	tot=unique(x+1,x+n+1)-x-1;
	
	build(1,1,tot-1);
	for(int i=1;i<=n;i++)
	{
		int l=lower_bound(x+1,x+tot+1,line[i].l)-x;
		line[i].l=l;
		int r=lower_bound(x+1,x+tot+1,line[i].r)-x;
		cout<<l<<' '<<r<<endl;
		line[i].r=r;
		modify(1,l,r-1,1);//问题:modify(后面的cout不执行了,此处RE)
		cout<<"-----"<<endl;
	}
	
	int ans=-114514;
	for(int i=1;i<=n;i++)
	{
		int l=line[i].l,r=line[i].r;
		modify(1,l,r-1,-1);
		ans=max(ans,t[1].len);
		modify(1,l,r-1,1);
	}
	printf("%d\n",ans);
	return 0;
}
2023/2/21 21:37
加载中...