UVa 11994. Happy Painting!

Brief description :

… 給定一棵 N 個結點的有根樹森林,邊上有一個顏色,需要支持下面這 3 個操作。

  • Query(x, y) 如果 x 和 y 在同一棵子樹中,則詢問路徑上邊的數目、和顏色的種類數。
  • Paint(x, y, c) 如果 x 和 y 在同一棵子樹中,則將經過的路徑上所有邊染色為 c。
  • Link(x, y, c) 如果 x 和 y 在同一個子樹中,且 x 不為 y 的祖先,那麼切斷 x 同其父親的聯繫,之後用一條顏色為 c 的邊連接 x、y。

(.. N = 50, 000 ..)

ゆっくり読んでください …

SRM 518 .. .

.. .
xiaodao: How to solve 900pt ..
xiaodao: Is it a combinatorics problem? ..
writer> xiaodao: my solution first computes a table for factors that only contain primes 2 and 3
xiaodao:.@
writer> xiaodao: and then you patch in the other factors : )
xiaodao:.@
.

這盤 一房間若菜。。
先開 900 。。感覺是個矩陣 + 二維分拆數。。想的不是很清楚。。(後來 writer 告訴我說是 dp ..枚舉 2 和 3 因子,然後補丁到其他位置。。)
。。。沒有辦法了。。只好開 600 。。。。然後發現這不是 hl 和 fgd 的神題么。。。


(。最後 900 的人全掛了。。shi 哥很華麗的依靠手速和直感登了頂。。。。。
其實應該考慮 cha 下面那個 900 的 ..)
最後 rank 30– …

Codeforces Beta Round #87.. .

(在網吧做 CF 的寂寞你們不懂!!!)

這盤是 TC 題媽 dolphinigle 的場。。

A 開始沒有注意 p[i] > i 的情況。。耽擱了一些時間在調試上。
B 略。。

之後先讀了 D,是一個給定一個表達式,問加括弧數目的題目,
對於普通的情況,我們知道解是 Catalan 序列,但是這題中有
+-+- A +-+- B
類似這樣的表達式存在,影響了我作出判斷,想了 12 分鐘沒有什麼有意義的結果於是跳。。

C 是一個插頭DP,但是感覺對我可能是個坑。。於是再看了一下 E。。

E 是說給定一個長度為 N 的賽道(數軸),以及 M 場比賽,
每場比賽佔用一段連續的區間,每個單位賽道如果要使用的話,有一個修復的代價,每場比賽有一個收益,最大化收益。。

目測了一下準備上最大權閉合子圖,但是有一個問題。。

。。N 和 M 都等於 2 * 10^5,這樣如果每場比賽都依賴整段區間的話,邊可能存不下。想了一下優化建圖。。或者能不能離散掉什麼的,但是沒有什麼結果。。
於是我賭它不稠密。。。。
(中間果然被 cha 了)

在 E 被 cha 這前我 yy 了一下 D。。。。
最後 C 的沒調出來。。

——
解題報告出來了。。D, E 都掛了。。。等下次吧。。。

———-
補:
好吧。。首先 C 只有 那 4 種插頭。。於是只是一道找 Invariants 的題目。。
。。。然後補一下 E 。。目前知道三種作法。。其中網路流的方法仍然有問題。。但我認為應該以後可以想出改進的辦法。。

首先是動態規劃。。

。。我們用 dp[i] 表示 到前 i 個位置為止所能取得的最大收益,第 i 個位置可以修也可以不修。

那麼 dp[i] = max{dp[j] + w(j, i)} | j < i} 其中 w(j, i) 表示及所有日程包含於 [j, i] 這段的賽事所能取得的收益和 減去 修復這段路的代價。 。。這是 第 i 個位置必須要修德,所以再 checkMax(dp[i], dp[i-1]) .. . 這個轉移方程的複雜度似乎是 O(n2) 而且看起來得到 w() 也不是很好寫。。 。。正確的做法是,將 w() 函數連同 dp[] 一起放到線段樹中維護,於是得到一個 O(nlogn) 的方法。 。。。然後。。這題還有一種貪心方法 Orz。 。貼在 Editorial 下面了。。

(據說這個題是出到 今年 IOI 然後被 Ban 掉了。。因為。。 IOI 不喜歡純數值輸出的題目。。)

/* .................................................................................................................................. */

const int N = 200009;
int C[N], L[N], R[N], V[N];
VI events[N];

LL key[4 * N], delay[4 * N];
int a, b; LL v;
int n, m; LL res;

#define root 1, 0, n
#define lx (x << 1)
#define rx (lx + 1)
#define lc lx, l, m
#define rc rx, m+1, r

void Inc(int x, LL d){
    key[x] += d, delay[x] += d;
}

void Release(int x){
    if (delay[x] != 0){
        key[lx] += delay[x], key[rx] += delay[x];
        delay[lx] += delay[x], delay[rx] += delay[x];
        delay[x] = 0;
    }
}

void Update(int x){
    key[x] = max(key[lx], key[rx]);
}

void Insert(int x, int l, int r){
    if (a <= l && r <= b){
        Inc(x, v);
    }
    else {
        Release(x);
        int m = ((l + r) >> 1);
        if (a <= m) Insert(lc);
        if (m < b) Insert(rc);
        Update(x);
    }
}

int main(){

    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    RD(n, m); REP_1(i, n) RD(C[i]);
    REP_1(i, m) RD(L[i], R[i], V[i]), events[R[i]].PB(i);

#define it events[i][j]

    REP_1(i, n){
        REP(j, SZ(events[i])){
            a = 0, b = L[it] - 1, v = V[it];
            Insert(root);
        }

        a = 0, b = i - 1, v = -C[i];
        Insert(root);

        checkMax(res, key[1]);
        a = i, b = i, v = res;
        Insert(root);
    }

    OT(res);
}

/* .................................................................................................................................. */

const int N = 200009;

int Lef[N], Rgt[N], Def[N];
int Att[N]; VI events[N];
int n, m; LL res;

struct comp{
    bool operator() (const int &lhs, const int &rhs) const{
        return Rgt[lhs] > Rgt[rhs];
    }
};

priority_queue<int, vector<int>, comp > Q;

int main(){
    RD(n, m); REP_1(i, n) RD(Att[i]);
    REP_1(i, m) RD(Lef[i], Rgt[i], Def[i]), events[Lef[i]].PB(i);

#define it events[i][j]

    REP_1(i, n){
        while (!Q.empty() && Rgt[Q.top()] < i) res += Def[Q.top()], Q.pop();
        REP(j, SZ(events[i])) Q.push(it);

        while (!Q.empty() && Att[i]){
            int delta = min(Att[i], Def[Q.top()]);
            Att[i] -= delta, Def[Q.top()] -= delta;
            if (!Def[Q.top()]) Q.pop();
        }
    }
    while (!Q.empty()) res += Def[Q.top()], Q.pop();

    OT(res);
}