题解 P5302 【[GXOI/GZOI2019]特技飞行】

这道题显然是由三个部分组成的： 1. 找到所有的直线交点 2. 统计每一个点是否被矩形覆盖 3. 决定【擦身而过】特技的最多次数 首先是部分一，容易观察到$y_{x,1}$数组的每一个逆序对对应一个交点。所以只要CDQ或者set求出所有的逆序对，然后写一个直线求交点即可。直接上计算几何板子即可。由于此题中的斜率不会是$\infty$，所以也可以解析暴力。 然后是部分二，这里不需要kd-tree或者树套树。可以先把坐标系转$45\degree$，即$(x,y)\rightarrow(x+y,y-x)$，然后就变成了矩形加单点求和。可以差分，就变成了单点加矩形求和。于是可以离线+扫描线，用一个线段树或BIT维护即可。此处要注意实数坐标的精度误差。 最后是部分三，首先可以注意到，每次两条航线相交就相当于交换一个排列中的相邻两个数。所以可以把所有交点按照从左往右顺序写成一个序列，比如$[(1,2),(2,3),(3,4),(2,3),(1,2)]$。我首先想到的是一个假算法，把每个数对的第一次出现当成左括号，第二次当成右括号，比如刚才的序列就写成`([{])`。然后消去尽量多构成合法括号序列的括号对。可惜这样做是有反例的，比如下面的图。  交点序列是$[(1,2),(2,3),(3,4),(1,2),(4,5),(2,3),(1,2),(3,4),(2,3)]$，然而最优解是消去$[(1,2),(2,3),(1,2),(2,3),(1,2),(2,3)]$。 就在手工模拟这个反例的时候，我发现了一些规律：貌似**左侧最上方的点和右侧最上方的点之间的折线最多只会有两段**。于是我可以把这两段消去，把剩下的半段折线强行掰直。比如上面的图第一次消去之后是这样的  每次掰直一段折线时，【对向交换】的次数加1。然后似乎贪心的递归下去做就是对的了。**本人无法证明其正确性。** 代码如下： ```cpp #include<bits/stdc++.h> #define eps 1e-12 using namespace std; using ll=long long; const int maxn=1<<20; struct point{double x,y;}; point operator-(point a,point b){return{a.x-b.x,a.y-b.y};} point operator+(point a,point b){return{a.x+b.x,a.y+b.y};} point operator*(double a,point b){return {b.x*a,b.y*a};} double operator*(point a,point b){return a.x*b.y-a.y*b.x;} point jd(point a,point b,point c,point d){ return a+((c-a)*(d-c))/((b-a)*(d-c))*(b-a); } struct segTree{ int a[1<<24],L[1<<24],R[1<<24],tot,rt; void ins(int x,int v,int&p,int tl=-2e8,int tr=2e8){ if(!p)p=++tot; if(tl==tr){a[p]+=v;return;} int mid=tl+tr>>1; if(x<=mid)ins(x,v,L[p],tl,mid);else ins(x,v,R[p],mid+1,tr); a[p]=a[L[p]]+a[R[p]]; } int qry(int l,int r,int p=1,int tl=-2e8,int tr=2e8){ if(l<=tl&&tr<=r)return a[p]; int mid=tl+tr>>1,re=0; if(l<=mid)re=qry(l,r,L[p],tl,mid); if(r>mid)re+=qry(l,r,R[p],mid+1,tr); return re; } }tr; int n,A,B,C,x0,x1,k,Y0[maxn],m,rnk[maxn],sa[maxn]; ll ans; struct st{int v,id;}a[maxn],b[maxn]; struct ev{double x,y;int tp,vl;};vector<ev> e; void cdq(int l,int r){ if(l==r)return; int mid=l+r>>1; cdq(l,mid),cdq(mid+1,r); int i=l,j=mid+1,k=0; while(i<=mid||j<=r) if(j>r||i<=mid&&a[i].v<a[j].v){ for(int t=mid+1;t<j;t++,m++){ point p=jd({x0,Y0[a[i].id]},{x1,a[i].v}, {x0,Y0[a[t].id]},{x1,a[t].v}); e.push_back({p.x+p.y,p.y-p.x,1,0}); } b[++k]=a[i++]; }else b[++k]=a[j++]; copy(b+1,b+1+k,a+l); } int main(){ scanf("%d%d%d%d%d%d",&n,&A,&B,&C,&x0,&x1); for(int i=1;i<=n;i++)scanf("%d",Y0+i),sa[i]=i; for(int i=1,x;i<=n;i++)scanf("%d",&x),a[i]={x,i}; sort(sa+1,sa+1+n,[](int x,int y){return a[x].v<a[y].v;}); for(int i=1;i<=n;i++)rnk[sa[i]]=i; scanf("%d",&k); while(k--){ int p,q,r;scanf("%d%d%d",&p,&q,&r); e.insert(e.end(),{ {p+q-r-eps,q-r-p,0,1},{p+q-r-eps,q+r-p,0,-1}, {p+q+r+eps,q-r-p,0,-1},{p+q+r+eps,q+r-p,0,1}}); } cdq(1,n); sort(e.begin(),e.end(),[](ev a,ev b){return a.x<b.x;}); for(ev&x:e)if(!x.tp)tr.ins(x.y,x.vl,tr.rt);else if(tr.qry(-2e8,floor(x.y-eps)))ans+=C; //此处必须要floor，因为把double转成int默认是向零取整 ll x=1ll*m*A+ans;int cnt=0; for(int i=1;i<=n;i++){ int p=rnk[i],q=sa[i]; if(p!=i){ sa[p]=q,rnk[q]=p; cnt++; } } ll y=1ll*cnt*A+1ll*(m-cnt)*B+ans; printf("%lld %lld\n",min(x,y),max(x,y)); return 0; } ```