某島

… : "…アッカリ~ン . .. . " .. .
March 23, 2020

Codeforces Global Round 7

E

哇,這個 rmq 還是有點巧妙的。。。

給定一個排列 P,排列的某些位置放有炸彈。我們按照順序把排列 P 的元素插入集合,如果當前插入的位置有炸彈,就在插入之後刪除集合中最大的元素。
對於一組炸彈分布情況,它的得分是集合中最後剩下來最大的元素(如果不是所有位置都有炸彈的話)。現在給定另一個排列 Q,對於每一個 i,輸出當炸彈分布為 Q[0..i-1] 時的得分。
顯然結果單調遞減。沒有炸彈的時候答案肯定是 n,然後我們觀察第一個不是 n 的解出現在哪裡,這個只要找到第一個把 n 炸掉的炸彈即可,似乎可以用 rmq 來統計。
但是我們發現隨著時間的推進,由於後面的炸彈在序列中更靠前的位置插入,前面的炸彈影響的位置可能會變。

進一步思考,我們把增加炸彈看成攻擊,減小答案看成防禦(增加擋板,有了更多的緩衝),
當前狀態不合法,當且僅當對於所有位置,它的防禦值(右邊的擋板)都不多於它的攻擊值(右邊的炸彈)。
這個時候所有的擋板都被炸毀,我們需要放寬限制,以增加更多的擋板。於是就變成了一個支持前綴加減,以及全局詢問最值的 rmq 問題。
(啊。。這個類比。。不禁讓我想起了 CF #87 的 E 題

const int N = int(3e5) + 9;

int P[N], Q[N], pos[N], n;

namespace SGT{
#define lx (x<<1)
#define rx (lx|1)
#define ml (l+r>>1)
#define mr (ml+1)
#define lc lx, l, ml
#define rc rx, mr, r
#define root 1, 1, n

    int T[N*4], D[N*4];
    int a, b, d;

    void upd(int x) {
        T[x] = max(T[lx], T[rx]);
    }

    void add(int x, int d) {
        T[x] += d; D[x] += d;
    }

    void rls(int x) {
        if (D[x]) {
            add(lx, D[x]); add(rx, D[x]);
            D[x] = 0;
        }
    }

    void Modify(int x, int l, int r){
        if (r < a || b < l) return;
        if (a <= l && r <= b){
            add(x, d);
        } else {
            rls(x);
            Modify(lc); Modify(rc);
            upd(x);
        }
    }
} using namespace SGT;

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
   // freopen("out.txt", "w", stdout);
#endif

    while (~scanf("%d", &n)) {
        REP_1(i, n) pos[RD(P[i])] = i;
        REP_1(i, n) RD(Q[i]);

        RST(T); RST(D);

        int z = n; a = 1; b = pos[n]; d = 1; Modify(root);

        REP_1(i, n-1) {
            printf("%d ", z);
            a = 1; b = Q[i]; d = -1; Modify(root);

            while (T[1] <= 0) {
                a = 1; b = pos[--z]; d = 1; Modify(root);
            }
        }
        printf("%d\n", z);
    }
}

F

暴力 DP 的話在 TSP 的基礎上再狀壓一維,記錄路徑的 01 值。
但是這樣就要壓兩個集合,你甚至開不下那麼大的數組,(小數據範圍就 MLE 了)。
一個簡單易懂的時間換空間策略是 DP 一半,然後拼起來。事實上我猜測小數據就是這麼過的。

雖然,比賽時我 死活卡不過去。。。由於我的代碼實在很優雅,我一直沒能放棄這個思路推倒重來!。。。
(後來看一下 Tourist 的代碼,先再外面枚舉了一下左邊的一半子集,就輕輕鬆鬆的卡過去了啊!! Orz)。

考慮更優的解法。繼續看 Tourist 的代碼。我們略微修改狀態的定義,現在 1 表示聯通,而 0 表示可聯通可不聯通,那麼顯然我們最後可以容斥得到原問題的解。
關鍵是,通過這樣修改狀態的定義之後,我們發現 dp[s] 的值,只和 s 的劃分有關!!這樣就可以搜索劃分就可以了。實現是需要用各種位運算的技巧優化常數。