Jan 4, 2019

[TIOJ][1909] 勇者出征

題目

原題目連結據說是 2015TOI 三模的題目簡單來說，就是給定一數列代表一排石柱，並且任意石柱 $A$ 可以到達的石柱有：

從 $A$ 左邊第一個比 $A$ 高的石柱 $B$ ，以及從 $A$ 往右找的第一個比 $A$ 高的石柱 $C$ ，其中高度比較低的石柱，其中如果 $B$ 或 $C$ 其中一個不存在，則連結到存在的那一個
假設 $D$ 可以連結到 $A$ 的話（ $D的高度 \lt A$ ），那麼 $A$ 也可以到 $D$

求所有石柱中，被最多條簡單路經過的石柱，其被走過的次數及編號如果有多組解，輸出編號最小的

解法

我們先來釐清一下什麼是簡單路徑好了所謂的簡單路徑，就是起點終點不重複，且路徑上經過的點不重複的路徑

建圖

看到路徑，我第一個想到的是圖論我們先想一下，要怎麼把圖建出來

暴力 $O ( N^2 )$

$N^2$ 就爆搜啊，按照題目寫的，往左往右找比他大的然後做比較

#define UNI(u,v,edge) edge[u].pb ( v ), edge[v].pb ( u )
for ( int i = 0 ; i < n ; i++ ){
    int l = -1, r = n;
    for ( int j = i - 1 ; j >= 0 ; j-- )
        if ( data[j] > data[i] ){
            l = j;
            break;
        }
    for ( int j = i + 1 ; j < n ; j++ )
        if ( data[j] > data[i] ){
            r = j;
            break;
        }
    if ( l == -1 && r == n )
        continue;
    if ( l == -1 ){
        UNI ( r, i, edges );
        continue;
    }
    if ( r == n ){
        UNI ( l, i, edges );
        continue;
    }
    UNI ( ( data[l] < data[r] ? l : r ), i, edges );
}

線段樹 $O ( NlogN )$

然後我就想到線段樹了 $index$ 是做離散化後的數字， $value$ 是編號然後就可以開兩顆線段樹，一顆紀錄左手邊的最大值，一邊紀錄右邊最小值一開始右手邊的最小值線段樹，裡面有 $N$ 個點每處理完一個點，就把這個點拔掉丟到左邊去 code大概像這樣

#define UNI(u,v,edge) edge[u].pb ( v ), edge[v].pb ( u )
#define INF 0x3f3f3f3f

// function
// 線段樹1是紀錄最小值、右手邊的線段樹
// 而線段數2是紀錄最大值、左手邊的線段樹
int seg1[maxN << 2], seg2[maxN << 2];
void update1 ( int l, int r, int index, int value, int n );
int query1 ( int l, int r, int nowL, int nowR, int n );
void update2 ( int l, int r, int index, int value, int n );
int query2 ( int l, int r, int index, int value, int n );

// lib是已經做完離散化的數列
memset ( seg1, INF, sizeof seg1 );
memset ( seg2, -1, sizeof seg2 )
for ( int i = 0 ; i < n ; i++ )
    update1 ( 0, n, i, lib[i], 1 );

for ( int i = 0 ; i < n ; i++ ){
    int l = query2 ( lib[i] + 1, n, 0, n, 1 );
    int r = query1 ( lib[i] + 1, n, 0, n, 1 );
    if ( l == -1 && r == INF )
        continue;
    if ( l == -1 ){
        UNI ( i, r, edges );
        continue;
    }
    if ( r == INF ){
        UNI ( i, l, edges );
        continue;
    }
    UNI ( i, ( data[l] < data[r] ? l : r ), edges );

    update1 ( 0, n, INF, lib[i], 1 );
    update2 ( 0, n, i, lib[i], 1 );
}

單調列隊優化 $O ( N )$

關於單調列隊優化的介紹可以看這份建中講義第二頁這邊

根據單調列隊的特性，我們可以保證現在在 deque 中的數字是遞減的

那麼假設要插入一個數字呢？假設現在這個數字比最後一個還要大，那麼我們就不斷的拔拔到最後一個數字比現在要插入的數字 $A$ 還要大的時候接著把這些拔掉的數字與 $A$ 做連接

不過為什麼是跟 $A$ 做連結而不是另一邊比較大的數字呢？因為他是說兩邊第一個比她大的數字的 min 既然兩邊都比他大，那麼當然選小的啊

最後這個 deque 會保證遞減那麼就是把這個 deque 最後一個數字 $L$ 與最後一個數字 $L'$ 做連結直到這個 deque 清空為止

不過因為只需要從後端做操作所以用 stack 就可以了

詳細的 code 請看這

typedef pair < int, int > pii;
#define F first
#define S second
#define UNI(u,v,edge) edge[u].pb ( v ), edge[v].pb ( u )

// data 是原數列
stack < pii, vector < pii > > st;
// stack 小技巧，stack 原本是用 deque 實作，可以自行更換為較快速的 vector （只有從後端操作）
pii swp;
st.push ( pii ( data[0], 0 ) );
for ( int i = 1 ; i < n ; i++ ){
    while ( !st.empty() && data[i] > st.top().F ){
        swp = st.top();
        st.pop();
        if ( EMP ( st ) )
            UNI ( swp.S, i, edges );
        else
            UNI ( ( st.top().F < data[i] ? st.top().S : i ), swp.S, edges );
    }
    st.push ( pii ( data[i], i ) );
}
swp = st.top();
st.pop();
while ( !st.empty() ){
    UNI ( swp.S, st.top().S, edges );
    swp = st.top();
    st.pop();
}

是時候來處理路徑囉

至於這個題目的另外一個部分：路徑又該怎麼處理呢？我們可以發現，這份資料轉換完之後保證是二元樹為什麼？因為他最多只會被兩個其他的點連結（左邊一個右邊一個）而自己只會連結到一個點那麼這不就是二元樹嗎？那麼，通過點 $u$ 的路徑會有三種：

$u$ 的祖先到 $u$ 的子孫的路徑
$u$ 的子孫到 $u$ 的子孫，但是有經過 $u$ 的路徑
從 $u$ 開始（或結束）的路徑

我們先定義 $dp[u] = u的子孫數目（包含 u ）$

因為是樹，所以不會有起點同終點但是路徑不同的情況發生（沒有環）因此只要計算起點終點的組合數就好了

那麼 1. 就很好算啦 $( 總點數 - dp[n] - 1 )\times ( dp[n] - 1 )$

那麼 2. 呢？上面有提到是二元樹，所以任一點最多只會有三條邊出去（兩個子孫一個祖先）所以，把祖先扣掉的那兩個 $a, b$ 的大小乘起（ $dp[a]\times dp[n]$ ）就是答案了

呃，3. 應該就不用講了吧 = = 就總點數減一啊 = =

然後有一點要注意的，因為一條路徑可以有頭尾互換（起點終點不同不能算是同一條路徑吧）

綜合一二三，所以只需要dfs一次就好了

這部分的code我放這

#define maxN 1000005
vector < int > edges[maxN];
int cnt[maxN], dp[maxN], N;
// N = 總點數 - 1

void dfs ( int n,  int p ){
    int a = -1, b = -1;
    for ( auto i: edges[n] ){
        if ( i == p )
            continue;
        if ( a == -1 )
            a = i;
        else
            b = i;
        dfs ( i, n );
        dp[n] += dp[i];
    }
    cnt[n] += ( N - dp[n] ) * dp[n]; // 祖先到子孫
    if ( deges[n].size() == 3 ) // 如果是有兩個子孫的話
        cnt[n] += dp[a] * dp[b];
    dp[n]++; // 因為包含 n ，但是前面都還要 - 1 很麻煩，所以我放到這邊才 + 1
    cnt[n] += N;
    cnt[n] <<= 1; // 記得乘二喔
}

code

綜合以上，我的code長這樣

// by. MiohitoKiri5474
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef pair < int, int > pii;
#define pb push_back
#define F first
#define S second
#define UNI(u,v,edge) edge[u].pb ( v ), edge[v].pb ( u )
#define maxN 1000005

vector < int > edges[maxN];
LL dp[maxN], N, cnt[maxN];

void dfs ( int n,  int p ){
    int a = -1, b = -1;
    for ( auto i: edges[n] ){
        if ( i == p )
            continue;
        if ( a == -1 )
            a = i;
        else
            b = i;
        dfs ( i, n );
        dp[n] += dp[i];
    }
    cnt[n] += ( N - dp[n] ) * dp[n];
    if ( edges[n].size() == 3 )
        cnt[n] += dp[a] * dp[b];
    dp[n]++;
    cnt[n] += N;
    cnt[n] <<= 1;
}


int main(){
    ios::sync_with_stdio ( false );
    cin.tie ( 0 );
    cout.tie ( 0 );

    int n, idx = -1;
    LL ma = -1;
    cin >> n;
    vector < int > data ( n );
    for ( auto &i: data )
        cin >> i;


    stack < pii, vector < pii > > st;
    pii swp;
    st.push ( pii ( data[0], 0 ) );
    for ( int i =  1 ; i < n ; i++ ){
        while ( !st.empty() && data[i] > st.top().F ){
            swp = st.top();
            st.pop();
            if ( st.empty() )
                UNI ( swp.S, i, edges );
            else
                UNI ( ( st.top().F < data[i] ? st.top().S : i ), swp.S, edges );
        }
        st.push ( pii ( data[i], i ) );
    }
    swp = st.top();
    st.pop();
    while ( !st.empty() ){
        UNI ( swp.S, st.top().S, edges );
        swp = st.top();
        st.pop();
    }

    N = n - 1;
    dfs ( 0, -1 );

    for ( int i = 0 ; i < n ; i++ ){
        if ( cnt[i] > ma )
            ma = cnt[i], idx = i;
    }

    cout << ma << ' ' << idx + 1 << '\n';
}

後記

其實這題我寫了很久因為之前一段時間都在搞特選而且我怕特選爆掉沒學校念所以我都在讀學測最近特選出來了已經沒有後顧之憂可以好好搞 TOI 了 <3 才回來鍊也是因為剛回來鍊所以手感很糟 = = 線段樹寫 query 還把查詢區間 & 總區間寫反 = = 還有忘了設定 ma = -1 然後還想說為什麼 WA Orz 這題也沒有看出來是單調列隊還傻傻花一個多小時寫線段樹 + debug 結果單調隊列快狠準 = = 我到底在幹嘛 = = 不過好險還有三個月（吧

然後這篇文章也太長 = = 這一行是第 326 行呃我是說在原始的 md 檔案上喔這邊已經 328 行了好多 = = 至少可定下心來好好練習了

[TIOJ][1909] 勇者出征

題目

解法

建圖

暴力 O(N2)O ( N^2 )O(N2)

線段樹 O(NlogN)O ( NlogN )O(NlogN)

單調列隊優化 O(N)O ( N )O(N)

是時候來處理路徑囉

code

後記

暴力 $O ( N^2 )$

線段樹 $O ( NlogN )$

單調列隊優化 $O ( N )$