P1315题解

· · 题解

不是你们都是怎么贪心的？我怎么一个都看不懂？

不难发现，答案为以下式子：

\begin{align*} ans &= \displaystyle\sum_{i=2}^{n} (tim_i \times cnt_i) + \displaystyle\sum T_i\text{。} \end{align*}

其中，tim_i 表示车到第 i 个站的时间，cnt_i 表示在第 i 个站下车的人数。

我们再来推一波 tim 的式子，设 be_i 为从 i 出发的时间，则：

\begin{align*} tim_i &= be_{i-1} + d_{i-1}\text{。} \end{align*}

其中 d 就是题目给出的 D，为了好看我用的小写。

再推 be 的式子，设 la_i 为第 i 个站最后一个乘客到达的时间，则：

\begin{align*} be_i = \max(la_i, be_{i-1}+d_{i-1})\text{。} \end{align*}

发现这是一个递推式，拆开得到：

\begin{align*} be_i = \max(la_i, \max(la_{i-1}+d_{i-1}, be_{i-2}+d_{i-2}+d_{i-1}))\text{，} \end{align*}

通过瞪眼法不难得到最终的式子是：

\begin{align*} be_i=\max(la_i, \displaystyle\max_{1 \le j \le i-1}( la_j + \displaystyle\sum_{j \le k \le i-1}d_k))\text{。} \end{align*}

把 d 的求和写成前缀和的形式，令 pre_i = \displaystyle\sum_{1 \le j \le i-1}d_j，则有：

\begin{align*} be_i&=\max(la_i, \displaystyle\max_{1 \le j \le i-1}( la_j - pre_j)+ pre_i )\\ &=\max(la_i - pre_i, \displaystyle\max_{1 \le j \le i-1}( la_j - pre_j))+ pre_i\\ &=\displaystyle\max_{1 \le j \le i}(la_j - pre_j) + pre_i\text{。} \end{align*}

再将式子合并到答案的式子中：

\begin{align*} ans &= \displaystyle\sum_{i=2}^{n} (tim_i \times cnt_i) + \displaystyle\sum T_i\\ &= \displaystyle\sum_{i=2}^{n} \left( (be_{i-1}+d_{i-1})\times cnt_i\right) +\displaystyle\sum T_i\\ &= \displaystyle\sum_{i=2}^{n}\left(\left(\displaystyle\max_{1 \le j \le i-1}(la_j - pre_j) + pre_{i-1}+d_{i-1}\right)\times cnt_i\right)+\displaystyle\sum T_i \\ &= \displaystyle\sum_{i=2}^{n}\left(\left(\displaystyle\max_{1 \le j \le i-1}(la_j - pre_j) + pre_{i}\right)\times cnt_i\right)+\displaystyle\sum T_i\text{。} \end{align*}

然后他们就开始贪心了。但是我没看懂，所以我只能分析这个式子。

我们现在能修改的是从 i 到 n 的 pre，i 可以自选。修改为 pre_{i \to n} \leftarrow pre_{i\to n}-1，然后再 d_{i-1} \leftarrow d_{i-1}-1。修改只能在 d_{i-1} > 0 时发生。

观察 ans 的最终式子，我们假设 la_j - pre_j 就是 \max 选的值，当前选择修改的是 k，考虑对 i 的贡献的影响。原贡献为 (la_j-pre_j+pre_i) \times cnt_i，现有以下三种情况：

现在很清楚了，我们只需要选在 i 前面的 la-pre 最大的那个点以后，且在 i 前面的数即可使 i 的贡献变小。原理是：若 la_j-pre_j 变，就会加上一个数，而 pre_i 也会减小同一个数，这时不变；使 la_j-pre_j 不变，而使 pre_i 减小一个数，则贡献就可以减小。

这时再贪心的想，我们对 j+1 这个点进行修改，则贡献会减小的点一定是最多的，会一直到下一个 la-pre 比 la_j-pre_j 大的这个点。这样就很清楚了，相当于一个点能影响后面连续一段 la-pre 比它小的点，也可以影响第一个比它大的点。我们将一个点和它能影响的点框成一个区间，然后只需要维护 la-pre 即可。用线段树维护。

一个线段被修改是不是优的，就取决于它除了左端点以外的点的 cnt 的和的大小。按照这个为关键字，将线段存到一个优先队列中即可确定操作顺序。

然后就是修改时的细节了。修改一个线段后，由于不会修改线段的左端点，线段中有一个点（不是右端点，因为右端点本来就比左端点大）可能比左端点大，那么我们就在那个点对线段分割。而当线段左端点的 d 被剪到 0 时，这就不能再减了，我们将左端点向右移动以为。由于要记录左端点的大小，而此时左端点被移动了，因此需要记录一个线段原始的左端点在哪里。

具体实现看代码吧。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 5e6+5;

inline ll max(ll a, ll b) { return a > b ? a : b; }

struct Node
{
    ll maxn; int maxpos; ll lazy;
    Node friend operator+(const Node &a, const Node &b)
    {
        Node res;
        res.maxpos = (a.maxn >= b.maxn ? a.maxpos : b.maxpos);
        res.maxn = max(a.maxn, b.maxn);
        res.lazy = 0;
        return res;
    }
};

struct Pas
{
    int tim, l, r;
} pas[MAXN];
int la[MAXN];
int pre[MAXN];
int d[MAXN];
int cnt[MAXN];
ll sum[MAXN];
int n, m, k;
ll T;

struct SegmentTree
{
    #define lp (p<<1)
    #define rp (p<<1|1)
    Node tree[MAXN<<2];
    void push_up(int p)
    {
        tree[p] = tree[lp] + tree[rp];
    }
    void push_down(int p)
    {
        if(!tree[p].lazy) return;
        tree[lp].lazy += tree[p].lazy;
        tree[rp].lazy += tree[p].lazy;
        tree[lp].maxn += tree[p].lazy;
        tree[rp].maxn += tree[p].lazy;
        tree[p].lazy = 0;
    }
    void build(int s, int t, int p)
    {
        if(s == t)
        {
            tree[p].maxn = la[s] - pre[s];
            tree[p].maxpos = s;
            return;
        }
        int mid = (s + t) >> 1;
        build(s, mid, lp);
        build(mid+1, t, rp);
        push_up(p);
    }
    void add(int l, int r, int s, int t, int p, int x)
    {
        if(l <= s && t <= r)
        {
            tree[p].maxn += x;
            tree[p].lazy += x;
            return;
        }
        int mid = (s + t) >> 1;
        push_down(p);
        if(l <= mid) add(l, r, s, mid, lp, x);
        if(r > mid) add(l, r, mid+1, t, rp, x);
        push_up(p);
    }
    Node query(int l, int r, int s, int t, int p)
    {
        if(l <= s && t <= r) return tree[p];
        int mid = (s + t) >> 1;
        push_down(p);
        if(r <= mid) return query(l, r, s, mid, lp);
        if(l > mid) return query(l, r, mid+1, t, rp);
        return query(l, r, s, mid, lp) + query(l, r, mid+1, t, rp);
    }
}tree;

struct seg
{
    int l, r;      // 左右端点
    ll sum, lmax;  // cnt 的和，原始左端点位置
    seg(int _l = 0, int _r = 0, ll _sum = 0, ll _vis = 0) : l(_l), r(_r), sum(_sum), lmax(_vis) {}
    bool operator<(const seg &_) const { return sum < _.sum; }
};
priority_queue<seg> q;

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i < n; i++) scanf("%d", &d[i]), pre[i+1] = pre[i] + d[i];
    for(int i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &pas[i].tim, &pas[i].l, &pas[i].r);
        la[pas[i].l] = max(la[pas[i].l], pas[i].tim);
        cnt[pas[i].r]++;
        T += pas[i].tim;
    }
    tree.build(1, n, 1);
    for(int i = 1; i <= n+1; i++) sum[i] = sum[i-1] + cnt[i];
    for(int i = 2, lst = 1, lstv = la[1] - pre[1]; i <= n; i++)
    {
        if(la[i] - pre[i] >= lstv) 
        {
            q.emplace(seg(lst, i, sum[i] - sum[lst], lst));
            lst = i;
            lstv = la[i] - pre[i];
        }
        if(i == n && lst != n) q.emplace(seg(lst, i+1, sum[i] - sum[lst], lst));
    }
    for(; k && !q.empty(); )
    {
        seg cur = q.top(); q.pop();
        if(cur.l == cur.r-1) // 特判一下
        {
            if(k <= d[cur.l]) tree.add(cur.l+1, n, 1, n, 1, k), d[cur.l] -= k, k = 0;
            else k -= d[cur.l], tree.add(cur.l+1, n, 1, n, 1, d[cur.l]), d[cur.l] = 0;
            continue;
        }
        ll lmax = max(tree.query(cur.l, cur.l, 1, n, 1).maxn, tree.query(cur.lmax, cur.lmax, 1, n, 1).maxn);
        ll maxn = tree.query(cur.l+1, cur.r-1, 1, n, 1).maxn;

        if(k > min((ll)d[cur.l], lmax - maxn))
        {
            tree.add(cur.l+1, n, 1, n, 1, min((ll)d[cur.l], lmax - maxn));
            k -= min((ll)d[cur.l], lmax - maxn);
            if(d[cur.l] > lmax - maxn)
            {
                int pos = tree.query(cur.l+1, cur.r-1, 1, n, 1).maxpos;
                if(cur.l < pos) q.emplace(seg(cur.l, pos, sum[pos] - sum[cur.l], cur.lmax));
                if(pos < cur.r) q.emplace(seg{pos, cur.r, sum[cur.r] - sum[pos], pos});
            }
            else if(cur.l+1 < cur.r) q.emplace(seg(cur.l+1, cur.r, sum[cur.r] - sum[cur.l+1], cur.lmax));
            d[cur.l] -= min((ll)d[cur.l], lmax - maxn);
            continue;
        }
        tree.add(cur.l+1, n, 1, n, 1, k);
        d[cur.l] -= k;
        k = 0;
    }

    for(int i = 1; i < n; i++) pre[i+1] = pre[i] + d[i];
    ll ans = -T;
    for(int i = 2; i <= n; i++)
    {
        ans += cnt[i] * (tree.query(1, i-1, 1, n, 1).maxn + pre[i]);
    }
    printf("%lld\n", ans);

    return 0;
}