P6968 [NEERC2016]Expect to Wait

Elma_ · 2022-09-28 19:21:36 · 题解

判断无解是容易的，不妨只考虑有解的情况。以时间为横轴、车数为纵轴画出一条折线，可以发现所有人的等待时间之和恰好是折线在横轴下方的部分和横轴围成的图形的面积。

考虑如何处理多次询问：先算出 b_i =0 时的答案，此时折线在横轴下方的部分和横轴所围成的图形可以拆分成若干高度不同的矩形。当 b_i > 0 时我们需要维护这些矩形向上平移 b_i 后的答案，将矩形按高度排序，询问按 b_i 排序后用指针维护一下即可。视 n,q 同阶，则时间复杂度为 O(n \log n)。

/*
最黯淡的一个　梦最为炽热
万千孤单焰火　让这虚构灵魂鲜活
至少在这一刻　热爱不问为何
存在为将心声响彻
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 2e5 + 5;

struct node {
    int x, id;
    bool operator < (const node &b) const {
        return x < b.x;
    }
} p[N];
int n, m, q, a[N], s[N], t[N]; 
int vr[N], bak; 
LL s1, s2, ans[N];

signed main(void) {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        char ch;
        cin >> ch >> t[i] >> a[i];
        a[i] *= (ch == '+' ? 1 : -1);
    }
    for (int i = 1; i <= n; i++) {
        s[i] = s[i - 1] + a[i];
        if (i < n) t[i] = t[i + 1] - t[i];
    }
    for (int i = 1; i <= n; i++) if (s[i] < 0) {
        vr[++bak] = i;
        s1 += 1ll * t[i] * (-s[i]);
        s2 += t[i];
    }  
    sort(vr + 1, vr + bak + 1, [&](const int &i, const int &j) {
        return s[i] > s[j];
    });
    for (int i = 1; i <= q; i++) cin >> p[i].x, p[i].id = i;
    sort(p + 1, p + q + 1);
    int j = 1;
    for (int i = 1; i <= q; i++) {
        while (j <= bak && -s[vr[j]] <= p[i].x) {
            s1 -= 1ll * t[vr[j]] * -s[vr[j]];
            s2 -= t[vr[j]];
            j++;
        }
        ans[p[i].id] = (s[n] + p[i].x < 0 ? -1 : s1 - 1ll * p[i].x * s2); 
    }
    for (int i = 1; i <= q; i++)
        ans[i] == -1 ? puts("INFINITY") : printf("%lld\n", ans[i]);
    return 0;   
}