[TIOJ 1645] 電路啟動方案

作法：

n<=200000，一看覺得這真是太噁爛了，兩種最小生成樹的作法都會直接噴射。但如果考慮 Kruskal ，仔細想想其實會有很多邊是無用的，如果只把有用的邊拿去作 Kruskal 應該有辦法過。我一開始的想法是，如果有三個點 ( x1,y1 ) , ( x2,y2 ) , ( x3,y3 ) 滿足 x1 < x2 < x3 且 y1 < y2 < y3 ，那麼 ( x1,y1 ) 連 ( x3,y3 ) 這條邊就廢掉了，因為我把他改成 ( x1,y1 ) 連 ( x2,y2 ) 加上 ( x2,y2 ) 連 ( x3,y3 ) 會讓這顆 spanning tree 更好( 因為改完之後會出現環，並且保持連通性，而隨便把一個環上的邊拔掉就會讓新的解更好 )。但這個觀察在最壞情形下需要考慮的邊數也會到O(n^2) ，例如考慮長的像這樣的點集：

就會輕鬆讓邊數衝到O(n^2) 。

但觀察上面那個例子，會發現對於一個點 P，我們考慮了一大堆在P右上方的點，但實際上在這個例子裡太浪費了，感覺上P在MST中頂多只會連到一個在他右上方的點，那麼就來看看 P 如果在MST中連到了兩個在他右上方的點 Q 和 R 的話，能不能推出矛盾之類的東西。

設 PQ向量 = ( x1 , y1 ) ，PR向量 = ( x2 , y2 ) ，並且可以設 x1 > x2 且 y1 < y2 ( 由前面的結論 )，如果PQ和PR都出現在MST裡面，並且一定要出現，那麼就必須要有 d( Q,R ) > d( P,Q ) 且 d( Q,R ) > d( P,R ) ( 這裡的 d 是題目中定義的距離 ) ，因為如果其中一個不滿足，那就可以把 PQ ( 或PR ) 換成QR ，並且讓這顆生成樹不會更差。這會等價於：

y1 + 2 * x2 < x1
x2 + 2 * y1 < y2

這告訴我們 x1 會比 y1 大蠻多的，還有 y2 會比 x2 大蠻多的，也就是如果以P為中心沿 45 度的線切下去的話， Q會落在右半邊，R會落在左半邊，所以我們得到的結論其實是：每個45度的區域內最多只有一個點和P在MST中相連！( 上面只證了在右上角的情形，但其他情形一魔一樣 )，這樣就可以把邊數降到 4*n 條了！ ( 對每個點都只要考慮他右邊的四個 1/8 區塊 )

但問題還沒結束，還必須知道 P 到底要和哪個點連起來比較好。假設現在我們要找以P為中心的第一象限的左半部分中，哪個點連P是我們唯一要考慮的邊，直覺上會選和P距離( 題目定的 )最近的點是最好的，而證明也不難證。假設 Q 和 R 是兩個落在上述區域的點，並且滿足 d( P,Q ) <= d( P,R ) ，且 PR 是 MST上的一條邊，我們要證明把 PR 換掉會更好。而當我們在MST中拔掉 PR 這條邊時，整個圖會被分成兩部分，如果 Q 和 P 不在同一個連通分量中，那就連 PQ ，否則連 QR ，這樣由於 Q 和 R 都在這個 1/8 區域中，用簡單的不等式就可以得到新的MST不會更差。

所以對於每個P右邊的四個 1/8 區塊，都只要找到一個離他最近的點就好了，但這問題似乎沒有那麼單純。首先一樣只看第一象限部分的左區塊，設 P 的座標為 ( x , y ) ，那麼我們要找的點 ( x1 , y1 ) 必須滿足： x1 >=x , y1 >=y , y1 - y >= x1 - x ，並且讓 ( x1 - x ) + ( y1 - y ) 越小越好。注意到 ( x1 - x ) + ( y1 - y ) 其實只和 x1 + y1 有關( 因為 P 是固定的 )，所以等於是要找讓 x1 + y1 最小的點。

但我們要考慮的區塊是一個 1/8 區塊，45度是個很難搞的東西，而利用座標變換可以把他轉換成 90 度角的區塊。例如我們考慮 ( x , y ) -> ( u , v ) 的變換，其中 u = x , v = y - x ，那麼原來在 xy 平面上滿足「 x>=0 , y>=0 , y>=x 」 的這個 1/8 區塊就會被變換到 uv 平面上的滿足「 u>=0 , v>=0 」 的區塊，也就是變回90度了，( 註：事實上，若 P 的坐標是 ( x0 , y0 ) ，那麼新的區塊其實是滿足 u >= x0 和 v >= y0 - x0 的，但這邊我們只關心區塊的形狀，所以可以不妨設 P 在原點。 )  而經過坐標變換之後，我們要 minimize 的函數就變成了 2 * u + v ，這個 2 是哪招!? 如果變成 u + v 不是更好看嗎(?) ，所以如果我們考慮的變換是 u = 2 * x , v = y - x ，就可以成功的讓新的座標系中我們需要 minimize 的函數變成了 u+v 了！所以這樣就可以按照 x 坐標從大到小作， 一樣時 y 從大到小作，維護一個二元組( X , Y ) 的 set ，其中第一個存的是點的 y 坐標，第二個存的是點的 x +y 的值，並且滿足當 y 坐標值遞增時 x +y 也是遞增的 ( 因為如果有一個點，他的 y 值比較小 ，x +y 值卻比較大，那我們永遠不會選到這個點，也就是他廢掉了 )，就可以在 O( nlogn ) 的時間內算出新的問題中每個點的「在他右上方且 x + y 最小」的點了( 不要忘了我們已經坐標變換過了 )。

而上面的變換是第一象限左半邊的，對於第一象限右半邊、第四象限右半邊和第四象限左半邊，分別可以用 ( u , v ) = (  2 * y , x - y ) , ( -2 * y , x +y ) , ( 2 * x , - x - y ) 的變換轉換為一樣的問題( 要注意到如果正在考慮第四象限的點，那麼需要 minimize 的函數會變成 x - y ，轉換後還是 u +v )，至於這是怎麼生出來的，其實湊一下就湊的出來了(?) XD

打完題解才發現，其實也沒必要讓函數是 u + v 阿，反正我們要 minimize 的函數都會被放在 set 裡二元組的第二個位子，所以其實沒差嘛XD

code :

#include<bits/stdc++.h>
#define LL long long
#define INF 2100000000
using namespace std;
const int maxn=200000+10 ;
 
struct pt
{
    int x,y,id ;
    bool operator < (const pt &rhs) const
    {
        return x==rhs.x ? y>rhs.y : x>rhs.x ;
    }
};
 
struct P
{
    int y,val,id ;
    bool operator < (const P &rhs) const
    {
        return y==rhs.y ? val>rhs.val : y<rhs.y ;
    }
};
 
struct edge
{
    int x,y,dis ;
    bool operator < (const edge &rhs) const
    {
        return dis<rhs.dis ;
    }
};
 
void get_pt(pt p0,pt &np,int t)
{
    int x=p0.x , y=p0.y ;
    if(t==1) np=(pt){2*x,y-x,0} ;
    if(t==2) np=(pt){2*y,x-y,0} ;
    if(t==3) np=(pt){-2*y,x+y,0} ;
    if(t==4) np=(pt){2*x,-x-y,0} ;
}
 
int fa[maxn] ;
int getfa(int x)
{
    return fa[x]==x ? x : fa[x]=getfa(fa[x]) ;
}
 
int n ;
pt p[maxn],q[maxn] ;
 
vector<edge> E ;
LL Kruskal()
{
    for(int i=1;i<=n;i++) fa[i]=i ;
    LL ret=0LL ;
    sort(E.begin(),E.end()) ;
    for(auto i : E)
    {
        int x=getfa(i.x) , y=getfa(i.y) ;
        if(x!=y) fa[x]=y , ret+=i.dis ;
    }
    return ret ;
}
 
set<P> st ;
void Insert(const P &np)
{
    st.insert(np) ; auto it=st.find(np) ;
 
    bool keep=1 ;
    it++ ;
    if(it!=st.end() && np.val >= it->val)
        keep=0 ;
    it-- ;
    if(!keep) { st.erase(it) ; return ; }
 
    while(it!=st.begin())
    {
        auto it2=it ; it2-- ;
        if(it2->val >= np.val) st.erase(it2) ;
        else break ;
    }
}
 
void cal()
{
    st.clear() ;
    for(int i=1;i<=n;i++)
    {
        auto it=st.lower_bound((P){q[i].y,INF,0}) ;
        if(it!=st.end())
        {
            int from=q[i].id , to=it->id ;
            int dis=it->val - q[i].x - q[i].y ;
            E.push_back((edge){from,to,dis}) ;
        }
        Insert((P){q[i].y,q[i].x+q[i].y,q[i].id}) ;
    }
}
 
main()
{
    int N,M ; scanf("%d%d%d",&N,&M,&n) ;
    for(int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y) ;
    for(int i=1;i<=4;i++)
    {
        for(int j=1;j<=n;j++) get_pt(p[j],q[j],i) , q[j].id=j ;
        sort(q+1,q+n+1) ;
        cal() ;
    }
    printf("%lld\n",Kruskal()) ;
}