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;

。。。并查集需要增加 l 和 r 两个域。。用以记录集合所代表的区间。
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:

Posted by xiaodao
Category: Codeforces
Tags: 数据结构, 斜率优化