[WC2012]记忆中的水杉树

https://www.luogu.org/problemnew/show/P4125

题解

首先一开始所有的线段互不相交。

那么对于第二问来说，一定存在一种方法使得所有线段都朝着一个方向动。

比如说我们要让所有线段从上往下走。

那么上面的线段得向下面的线段连边。

这是一个\(DAG\)，考虑怎么建出来。

我们可以先用扫描线,还是因为线段互不相交，所以在扫描线移动的过程中，当前所有线段的相对位置是不变的，所以我们可以把每条线段用斜截式表示，然后用set维护他们的关系，每次插入一条线段就和前驱后继连边就可以了。

然后因为一些恶心的原因得把坐标表示为\((x+1,y)\)。

然后再去考虑第一问，如果直接做的话，感觉需要用数据结构去维护\(DAG\)。

然后我们考虑把操作序列反过来，这样的话删线段就变成了加线段。然后考虑什么情况下加入是不合法的。

比如我们从下往上加线段，设这个线段的横坐标区间为\((l,r)\)，那么如果不合法，那么当且仅当这个区间内有在它下面的线段，用上我们刚刚求的拓扑序就是这个线段的拓扑序比较小。

判断的话就线段树维护区间最小值就好了。

因为有四个方向，所以我们还得横纵各做一次扫描线，线段树维护最大值和最小值。

代码

#include<bits/stdc++.h>

#define N 200009

#define inf 2e9

using namespace std;

typedef long long ll;

queue<int>q;

int du[N],tot,head[N],n,xx[N],yy[N],ans[N],_xx[N],_yy[N],tag1[N],tag2[N],c[N],ans2,ans1[N];

ll nowx,b[N<<1];

inline ll rd(){

	ll x=0;char c=getchar();bool f=0;

	while(!isdigit(c)){if(c=='-')f=1;c=getchar();}

	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}

	return f?-x:x;

}

struct node{int a,b;}mu[N];

struct edge{int n,to;}e[N<<2];

inline void add(int u,int v){e[++tot].n=head[u];e[tot].to=v;head[u]=tot;du[v]++;}

struct point{double x,y;};

struct line{

	point x,y;int id;

	double k,b;

	inline bool operator ==(const line &b)const{

		return id==b.id;

	}

	inline bool operator <(const line &other)const{

		return nowx*k+b<nowx*other.k+other.b;

	}

}a[N];

struct segment_tree_t{

	int mi[N<<2],ma[N<<2],trmi[N<<2],trma[N<<2];

	segment_tree_t(){memset(mi,0x3f,sizeof(mi));memset(trmi,0x3f,sizeof(trmi));}

	inline void pushdown(int cnt){

		mi[cnt<<1]=min(mi[cnt<<1],mi[cnt]);

		ma[cnt<<1]=max(ma[cnt<<1],ma[cnt]);

		trmi[cnt<<1]=min(trmi[cnt<<1],mi[cnt]);

		trma[cnt<<1]=max(trma[cnt<<1],ma[cnt]);

		mi[cnt<<1|1]=min(mi[cnt<<1|1],mi[cnt]);

		ma[cnt<<1|1]=max(ma[cnt<<1|1],ma[cnt]);

		trmi[cnt<<1|1]=min(trmi[cnt<<1|1],mi[cnt]);

		trma[cnt<<1|1]=max(trma[cnt<<1|1],ma[cnt]);

		ma[cnt]=0;mi[cnt]=inf;

	}

	inline void ins(int cnt,int l,int r,int L,int R,int x){

		if(l>=L&&r<=R){

			ma[cnt]=max(ma[cnt],x);

			mi[cnt]=min(mi[cnt],x);

			trma[cnt]=max(trma[cnt],x);

			trmi[cnt]=min(trmi[cnt],x);

			return;

	    }

	    int mid=(l+r)>>1;

	    pushdown(cnt);

	    if(mid>=L)ins(cnt<<1,l,mid,L,R,x);

	    if(mid<R)ins(cnt<<1|1,mid+1,r,L,R,x);

	    trmi[cnt]=min(trmi[cnt<<1],trmi[cnt<<1|1]);

	    trma[cnt]=min(trma[cnt<<1],trma[cnt<<1|1]);

	}

	inline int querymin(int cnt,int l,int r,int L,int R){

		if(l>=L&&r<=R)return trmi[cnt];

		int mid=(l+r)>>1,ans=inf;

		pushdown(cnt);

		if(mid>=L)ans=min(ans,querymin(cnt<<1,l,mid,L,R));

		if(mid<R)ans=min(ans,querymin(cnt<<1|1,mid+1,r,L,R));

		return ans;

	}

	inline int querymax(int cnt,int l,int r,int L,int R){

		if(l>=L&&r<=R)return trma[cnt];

		int mid=(l+r)>>1,ans=0;

		pushdown(cnt);

		if(mid>=L)ans=max(ans,querymax(cnt<<1,l,mid,L,R));

		if(mid<R)ans=max(ans,querymax(cnt<<1|1,mid+1,r,L,R));

		return ans;

	}

}X,Y;

set<line>s;

set<line>::iterator its;

vector<int>vec[N],anti_vec[N];

vector<int>::iterator it;

int main(){

	n=rd();

	for(int i=1;i<=n;++i){

		a[i].x.x=rd();a[i].x.y=rd();a[i].y.x=rd();a[i].y.y=rd();

		if(a[i].x.x>a[i].y.x)swap(a[i].x,a[i].y);

		if(a[i].x.x!=a[i].y.x){

			a[i].k=(a[i].y.y-a[i].x.y)/(a[i].y.x-a[i].x.x);

			a[i].b=a[i].y.y-a[i].y.x*a[i].k;

		}

		else a[i].b=a[i].y.y;

		b[++b[0]]=a[i].x.x+1;b[++b[0]]=a[i].y.x;

	}

	sort(b+1,b+b[0]+1);

	b[0]=unique(b+1,b+b[0]+1)-b-1;

	for(int i=1;i<=n;++i){

		xx[i]=lower_bound(b+1,b+b[0]+1,a[i].x.x+1)-b;

		yy[i]=lower_bound(b+1,b+b[0]+1,a[i].y.x)-b;

		a[i].id=i;

		vec[xx[i]].push_back(i);

		anti_vec[yy[i]].push_back(i);

	}

	for(int i=1;i<=b[0];++i){

		nowx=b[i];

		for(it=vec[i].begin();it!=vec[i].end();++it){

			line now=a[*it];

			its=s.insert(now).first;

			++its;

			if(its!=s.end()){

				add(now.id,its->id);

			}

			--its;

			if(its!=s.begin()){

				its--;

				add(its->id,now.id);

			}

		}

		for(it=anti_vec[i].begin();it!=anti_vec[i].end();++it){

			line now=a[*it];

			s.erase(now);

		}

		vec[i].clear();anti_vec[i].clear();

	}

	for(int i=1;i<=n;++i)if(!du[i])q.push(i);

	while(!q.empty()){

		int u=q.front();q.pop();ans[++ans[0]]=u;tag1[u]=ans[0];

		for(int i=head[u];i;i=e[i].n){

			int v=e[i].to;

			if(!--du[v])q.push(v);

		}

	}

	memset(head,0,sizeof(head));tot=0;

	for(int i=1;i<=n;++i){

		if(a[i].x.y>a[i].y.y)swap(a[i].x,a[i].y);

		if(a[i].x.y!=a[i].y.y){

			a[i].k=(a[i].y.x-a[i].x.x)/(a[i].y.y-a[i].x.y);

			a[i].b=a[i].y.x-a[i].y.y*a[i].k;

		}

		else a[i].k=0,a[i].b=a[i].y.x;

		c[++c[0]]=a[i].x.y+1;;c[++c[0]]=a[i].y.y;

	}

	sort(c+1,c+c[0]+1);

	c[0]=unique(c+1,c+c[0]+1)-c-1;

	for(int i=1;i<=n;++i){

		_xx[i]=lower_bound(c+1,c+c[0]+1,a[i].x.y+1)-c;

		_yy[i]=lower_bound(c+1,c+c[0]+1,a[i].y.y)-c;

		a[i].id=i;

		vec[_xx[i]].push_back(i);

		anti_vec[_yy[i]].push_back(i);

	}

	for(int i=1;i<=c[0];++i){

		nowx=c[i];

		for(it=vec[i].begin();it!=vec[i].end();++it){

			line now=a[*it];

			its=s.insert(now).first;

			++its;

			if(its!=s.end()){

				add(now.id,its->id);

			}

			--its;

			if(its!=s.begin()){

				its--;

				add(its->id,now.id);

			}

		}

		for(it=anti_vec[i].begin();it!=anti_vec[i].end();++it){

			line now=a[*it];

			s.erase(now);

		}

	}

	for(int i=1;i<=n;++i)if(!du[i])q.push(i);

	while(!q.empty()){

		int u=q.front();q.pop();ans1[++ans1[0]]=u;tag2[u]=ans1[0];

		for(int i=head[u];i;i=e[i].n){

			int v=e[i].to;

			if(!--du[v])q.push(v);

		}

	}

	for(int i=1;i<=n;++i){

		mu[i].a=rd();mu[i].b=rd();

	}

	for(int i=n;i>=1;--i){

		int id=mu[i].a;

		if(mu[i].b==0){

			if(Y.querymin(1,1,c[0],_xx[id],_yy[id])<tag2[id]){

				ans2=i;

		    }

		}

		if(mu[i].b==1){

			if(X.querymax(1,1,b[0],xx[id],yy[id])>tag1[id]){

				ans2=i;

			}

		}

		if(mu[i].b==2){

			if(Y.querymax(1,1,c[0],_xx[id],_yy[id])>tag2[id]){

				ans2=i;

			}

		}

		if(mu[i].b==3){

			if(X.querymin(1,1,b[0],xx[id],yy[id])<tag1[id]){

				ans2=i;

			}

		}

		X.ins(1,1,b[0],xx[id],yy[id],tag1[id]);

		Y.ins(1,1,c[0],_xx[id],_yy[id],tag2[id]);

	}

	printf("%d\n",ans2);

	for(int i=1;i<=n;++i)printf("%d %d\n",ans[i],3);

	return 0;

}

巴特西

[WC2012]记忆中的水杉树

题解

代码

最新文章

热门文章