Codeforces Round #189

Problem C. Kalila and Dimna in the Logging Industry

Brief description:

。。給定一列樹 A[]。。每顆樹有一個相關的代價 B[]。。
。。你有一個電鋸。。。每次你可以用這個電鋸把一棵樹的高度鋸 1.。之後你需要花費一個代價去 Recharge。。。
。。每當你把一個樹的全鋸掉之後。。你就可以用這棵樹上所標記的代價去替換你當前的 Recharge 代價。。。
。。。樹的高度遞增。。代價遞減。。第一樹的高度是 1,最後一棵樹的代價是 0。。。。
。。。最小化把所有樹都鋸掉的總代價。。。

Analysis:

先搞出 DP 方程。。。

...
    FOR_1(i, 2, n){
        f[i] = INFF;
        FOR(j, 1, i) checkMin(f[i], f[j] + a[i]*b[j]);
    }

。。很明顯這是一個斜率 DP。。。
https://gist.github.com/lychees/5853543

Problem E. Ping-Pong

Brief description:

動態維護一組區間,支持以下操作:

  • 1 l r:插入一個新區間 [l, r]
  • 2 l r:詢問是否可以從第 l 次插入的區間到達第 r 次插入的區間。

存在一條從 [a, b][c, d] 的有向邊的條件是。。交叉或者被包含。。
。。也就是。這樣這樣 [(]) 互相可達。。[()] 的話只能從 () -> []。。
。。(總操作數 ≤ 10^5, 且區間的長度按照時間順序嚴格遞增。)

Analysis:

… 如果是互相圖的話那麼大家都會搞。。並查集維護一下就行了。。。
。。於是唯一的問題就是在於如何利用 “長度遞增” 這個條件了。。。

We define that intervels in the same set can go to each other in the same set. So the interval in set i can go to ( MAXL[i], MAXR[i] ).
(a,b) and (c,d) is in the same set if only if a < c < b < d or c < a < d < b. >> The length of the new interval is guaranteed to be strictly greater than all the previous intervals.

So the new interval will only connected the intervals, it won’t be full coverd by any other we had added. We can used segment tree to do this, union the sets, extend MAXL, MAXR of the set. For querys, if the query intervals (a, b) are in the same set, the answer is YES. Else, we knowed that b can be range ( MAXL[i], MAXR[i] ), just check if a is in that range or not.

。。。群里的 wuyiqi 神牛 Gtalks 上問了 hanhan0912 。。。 昨天下午貼到群里。。我才想清楚。。。。。實在是智商低的不能多說。。。。
。。大意就是每個並查集。。相當於所有集合中的區間所組成的一個大的區間。。。。。那麼如果不在同一個並查集里。。則只要檢查 出發區間 是否被目標區間所在的並查集所表示的區間 包含 就可以了。。。

為什麼這樣做是正確的。。。

。。因為如果 (){} 包含。。。要麼是。。{ [ ( ] ) } 。。。要麼是。。{ [ ( ) ] }
。。前一種情況說明存在一個屬於 {}[]() 相交。。。此時即可說明可達。。。。。
。。而後一種情況不存在。。。

—————— 構思程序。。。

struct Query{
    int id, t, l, r;
    void input(int);
    void process();
} Q[N];

首先先定義一個 Query 類。。先聲明 input()process() 兩個方法。。留到下面寫。。
然後是並查集。。

namespace DSU{ // Disjoint Set Union
    int P[N], R[N], l[N], r[N], n;
    inline void Make(int x){
        P[x] = x, R[x] = 0;
    }
    inline int Find(int x){
        return P[x] == x ? x : P[x] = Find(P[x]);
    }
    inline void Unionn(int x, int y){
        if (R[x] == R[y]) ++R[x];
        else if (R[x] < R[y]) swap(x, y);
        P[y] = x;
        checkMin(l[x], l[y]);
        checkMax(r[x], r[y]);
    }
    inline void Union(int x, int y){
        x = Find(x), y = Find(y), Unionn(x, y);
    }
    inline void Init(){
        REP_1(i, n) Make(i);
    }
} //using namespace DSU;

。。。並查集需要增加 lr 兩個域。。用以記錄集合所代表的區間。
Unionn(x, y) 合併表示合併前 x, y 就已經是根結點了。。(習慣雙寫末尾字母表示一個相關的東西。。比如計算幾何里我經常用 dett() 表示 det() 後取 sgn()。。。可以理解成 Union'det'

然後我們還需要一個線段樹去維護這個並查集。。。

namespace SGT{ // Segment Tree

#define lx (x<<1)
#define rx (lx|1)
#define mid (l + r >> 1)
#define lc lx, l, mid
#define rc rx, mid+1, r
#define root 1, 0, SZ(grid)-1

    const int N = ::N*8;
    VI T[N]; int id, a, b;

    void _Insert(int x, int l, int r){

        if (r < a || b < l) return;

        if (a <= l && r <= b){
            T[x].PB(id);
        }
        else{
            _Insert(lc);
            _Insert(rc);
        }
    }

    void _Extend(int x, int l, int r){

        if (r < a || a < l) return;

#define del(A, i) swap(A[i], A.back()), A.pop_back(), --i;

        REP(i, SZ(T[x])){
            int t = DSU::Find(T[x][i]);
            if (t != T[x][i]){ // 小優化...
                del(T[x], i);
            }
            else if (DSU::l[t] < a && a < DSU::r[t]){
                DSU::Unionn(t, id);
                id = DSU::Find(id);
                del(T[x], i);
            }
        }

        if (l < r){
            _Extend(lc);
            _Extend(rc);
        }
    }

    void Insert(int _id){
        id = _id, a = DSU::l[id], b = DSU::r[id], _Extend(root), a = b, _Extend(root);
        a = DSU::l[id], b = DSU::r[id], _Insert(root);
    }

    void Build(){
        UNQ(grid);
    }
} //using namespace SGT;

線段樹的每個結點存一個 Vector 以任意順序列舉所有相關集合。。插入區間前首先需要執行擴展。。。

  • _Extend()。。檢查所有可以覆蓋當前區間某個端點的區間。。並擴展當前區間。。。
  • _Insert()。。插入擴展後的區間。。。

。。。補上其他部分就行了。。

void Query::input(int i){
    if (RD(t) == 1){
        grid.PB(RDD(l)), grid.PB(RDD(r)); // 離散化準備。
        DQ[id = ++DSU::n] = i; // 建立映射
    }
    else{
        RD(l, r);
    }
}

void Query::process(){
    if (t == 1){
        DSU::l[id] = l = BSC(grid, l), DSU::r[id] = r = BSC(grid, r);
        SGT::Insert(id);
    }
    else{
        l = DQ[l], r = DSU::Find(r);
        puts(DSU::l[r] <= Q[l].l && Q[l].r <= DSU::r[r] ? "YES" : "NO");
    }
}

int main(){

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

    REP_1_C(i, RD(n)) Q[i].input(i);
    DSU::Init(), SGT::Build();
    REP_1(i, n) Q[i].process();
}

https://gist.github.com/lychees/5855251

— 補充
。。。。這個版本的程序雖然是 AC 的。。… 但是交換 Union() 兩個參數的順序就會 WA on 5。。
。。。這類錯誤非常隱蔽不宜察覺。。程序里最好不要依賴於這種東西。。。

External link: