Solution [WC2012]记忆中的水杉树

听取WA声一片 一开始所有的线段互不相交。 对于第二问来说,一定存在一种方法使得所有线段都朝着一个方向动。比如说我们要让所有线段从上往下走。那么上面的线段得向下面的线段连边。 这是一个 \texttt{DAG},考虑怎么建出来: 我们可以先用扫描线,还是因为线段互不相交,所以在扫描线移动的过程中,当前所有线段的相对位置是不变的,所以我们可以把每条线段用斜截式表示,然后用 set 维护他们的关系,每次插入一条线段就和前驱后继连边就可以了。 然后将坐标表示为 (x+1,y)。 再去考虑第一问,如果直接做的话,感觉需要用数据结构去维护 \texttt{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 Read more…