（在网吧做 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);
}

Posted by xiaodao
Category: Codeforces