「JOISC 2017 Day 2」门票安排 – 题解

主要思路

我靠这是真的难,对着 pty 的题解傻看了一下午。

首先考虑把这个环变成一条链。对于 \(m\) 个区间,满足 \(a_i > b_i\) 的区间可以先直接翻转成 \([1, a_i) \cup [b_i, n]\)。我们现在需要最小化被覆盖的次数。

考虑一下二分答案,然后怎么搞?

首先有个结论,如果两个区间是没有交集的,那么他们不会同时翻转。翻转了之后答案肯定会变大,这个是显然的。

那么反过来说,这些同时翻转的区间肯定是有公共部分的,我们可以找一个公共点 \(t\),做一个贪心:我们从 \(1\) 往 \(t – 1\) 扫,每次扫到一个线段的左端点,就把右端点和 \(c\) 扔到大根堆里面去。扫的过程中,如果该点本身的被覆盖次数就超过了 \(ans\),那么我们就选堆顶的区间进行反转。

然而有个问题,这个翻转并不是无后效性的。我们只能保证左端点在 \(t\) 的左边,但是会存在后面的翻转让当前的覆盖次数重新大于答案的情况。我们需要预先知道总的翻转次数,这样我们就可以算出来如果进行反转,那么该点的终态到底是怎样的。显然,如果满足以下条件,则需要进行反转:

\[ now – x + cnt – x > ans \]

其中,\(x\) 为当前反转的线段个数,前面被覆盖的次数为 \(now\),剩下的次数为 \(cnt\)。

接下来有几个性质:

性质一:设反转区间的交集为 \([l, r)\),找到 \(t \in [l, r)\) 使得 \(b_t\) (翻转后的覆盖次数)最大。满足 \(b_t = \max(b_i)\) 或 \(b_t = \max(b_i) – 1\)。

证明一:反证,如果最大值不在 \([l, r)\) 内,我们考虑把被反转的右端点最左的、左端点最右的取消反转,外面的最大值并不会增加,且所有位置依然合法,且 \(b_t\) 变大了,所以 \(b_t\) 一定最大。所以翻转次数存在 \(cnt = ans – a_t, cnt = ans – a_t + 1\) 两种情况。

性质二:\(t\) 满足 \(a_t = \max(a_i)\)。

证明二:继续反证,如果不满足,存在一个 \(a_i > a_t, i \not \in [l, r)\),那么至少有一个翻转区间是不包含 \(i\) 的,也就是说 \(b_i – a_i > b_t – a_t\)。但是也存在 \(b_i > b_t + 1\),这样就假了。

然后这个 \(t\) 你可以取极左、极右点做检测即可。

代码

// LOJ2393.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5 + 200;

typedef long long ll;
typedef pair<int, ll> pil;

int n, m;
ll ai[MAX_N], bi[MAX_N];
vector<pil> tags[MAX_N];

struct segment
{
    int l, r, c;
} segs[MAX_N];

bool judge(ll threshold, int pos, ll rev_cnt)
{
    if (threshold < rev_cnt)
        return false;
    priority_queue<pil> pq;
    for (int i = 1; i <= n; i++)
        bi[i] = 0, tags[i].clear();
    for (int i = 1; i <= m; i++)
        if (segs[i].l <= pos && pos < segs[i].r)
            tags[segs[i].l].push_back(make_pair(segs[i].r, segs[i].c));
    ll curt = 0;
    for (int i = 1; i <= pos; i++)
    {
        for (pil v : tags[i])
            pq.push(v);
        while (ai[i] - curt + rev_cnt > threshold)
        {
            if (pq.empty())
                return false;
            pil u = pq.top();
            pq.pop();
            ll crev = min(u.second, (ai[i] - curt + rev_cnt - threshold + 1) >> 1);
            curt += crev, rev_cnt -= crev, bi[u.first] += (crev << 1);
            if (u.second != crev)
                pq.push(make_pair(u.first, u.second - crev));
        }
    }
    bi[pos + 1] -= curt;
    for (int i = pos + 1; i <= n; i++)
    {
        bi[i] += bi[i - 1];
        if (bi[i] + ai[i] > threshold)
            return false;
    }
    return true;
}

bool check(ll threshold, int pos)
{
    return judge(threshold, pos, ai[pos] - threshold) || judge(threshold, pos, ai[pos] - threshold + 1);
}

int main()
{
    // freopen("02-06.in", "r", stdin);
    scanf("%d%d", &n, &m);
    ll l = 0, r = 0, res = 0;
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &segs[i].l, &segs[i].r, &segs[i].c);
        if (segs[i].l > segs[i].r)
            swap(segs[i].l, segs[i].r);
        ai[segs[i].l] += segs[i].c, ai[segs[i].r] -= segs[i].c;
        r += segs[i].c;
    }
    for (int i = 1; i <= n; i++)
        ai[i] += ai[i - 1];
    int lpt = 0, rpt = 0;
    for (int i = 1; i <= n; i++)
    {
        if (ai[i] > ai[lpt] || lpt == 0)
            lpt = i;
        if (ai[i] >= ai[rpt])
            rpt = i;
    }
    while (l <= r)
    {
        ll mid = (l + r) >> 1;
        if (check(mid, lpt) || check(mid, rpt))
            r = mid - 1, res = mid;
        else
            l = mid + 1;
    }
    printf("%lld\n", res);
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注