主要思路
我靠这是真的难，对着 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;
}
orz