Luogu4064 [JXOI2017]加法

发布于 16 天前  48 次阅读


Link

Sol

总结:对于一类用贪心解决选一些区间来覆盖点(对点经行操作)的问题,可以贪心地考虑选的区间尽量往右边多贡献一点。

现在的问题就是,给你了一些区间[l_i,r_i] 和一个增加值 val,每个区间仅可以被选择一次,每次操作都选定一个区间并在序列上对这个区间内的数都加上val,现在要操作后的序列的最小值尽可能的大。只可以操作k

首先看到最大化最小值这种字眼,就要二分一下这个答案。最优化问题改成判定性问题很常见。

还是对给你的区间按照左端点排序。那么现在从左往右操作。我们希望每次选定的区间右端点尽可能靠右,所以就吧区间加入一个大根堆里面,按照右端点排序即可。

特别注意的是,判定的时候一个点它可能加一次还是不满足,但是它有可能被多个区间覆盖。那么就while下去就可以了(这个bug我改了很久。

Code

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 4e5 + 5;
const int inf = 0x7f7f7f7f;

int T, n, m, k, p;
int a[SIZE], tree[SIZE];

struct node {
    int l, r;
    bool operator< (const node &a) const {
        return r == a.r ? l < a.l : r < a.r;
    }
} ;

struct seg {
    int l, r;
    bool operator< (const seg &a) const {
        return l == a.l ? r < a.r : l < a.l;
    }
} b[SIZE];

namespace ae86 {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using ae86::read;

#define lowbit(x) (x & (-x))

void modify(int pos, int val) {
    for ( ; pos <= n; pos += lowbit(pos)) tree[pos] += val;
}

int query(int pos) {
    int ans = 0;
    for ( ; pos; pos -= lowbit(pos)) ans += tree[pos];
    return ans;
}

int judge(int x) {
    std::priority_queue < node > q;
    memset(tree, 0, sizeof(tree));
    while (!q.empty()) q.pop();
    for (int i = 1; i <= n; ++ i) modify(i, a[i]), modify(i + 1, -a[i]);
    int cnt = 0;
    for (int i = 1, j = 1; i <= n; ++ i) {
        while (j <= m && b[j].l <= i) q.push((node) {b[j].l, b[j].r}), ++ j;
        while (query(i) < x) { // 特别注意这里是while
            if (q.empty()) return 0;
            node tmp = q.top(); q.pop();
            if (tmp.r < i) return 0;
            modify(tmp.l, p); modify(tmp.r + 1, -p); ++ cnt;
            if (cnt > k) return 0;
        }
    }
    return 1;
}

int main() {
    // freopen("code.in", "r", stdin);
    // freopen("code.out", "w", stdout);
    T = read();
    while (T --) {
        int l = inf, r = 0, mid = 0, ans = 0;
        n = read(), m = read(), k = read(), p = read();
        memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b));
        for (int i = 1; i <= n; ++ i) a[i] = read();
        for (int i = 1; i <= m; ++ i) b[i].l = read(), b[i].r = read();
        for (int i = 1; i <= n; ++ i) l = std::min(l, a[i]);
        std::sort(b + 1, b + m + 1);
        r = l + k * p;
        while (l <= r) {
            mid = (l + r) >> 1;
            if (judge(mid)) ans = std::max(ans,mid), l = mid + 1;
            else r = mid-1;
        }
        printf("%d\n", ans);
    }
    return 0;
}

学会生存 学会关心