社区讨论

逻辑上不应出现的WA求解答

lluanXiPing_AKed_IOI
P5785[SDOI2012] 任务安排参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mmgc8jhl
此快照首次捕获于
2026/03/07 21:07
16 小时前
此快照最后确认于
2026/03/08 09:20
4 小时前
查看原帖
本人使用李超线段树通过此题（已通过李超线段树模板），遇到如下问题：
  • 查询 fif_i 时询问下标 ∑ai+s\sum a_i+s 的下凸壳对应值，插入过点 (∑ai,fi)(\sum a_i,f_i) 的直线，获得 9595 分。
  • 查询 fif_i 时询问下标 ∑ai\sum a_i 的下凸壳对应值，插入过点 (∑ai−s,fi)(\sum a_i-s,f_i) 的直线，获得 100100 分。
附代码：
CPP
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
namespace pnl {
    typedef long long lnt;
    typedef long double louble;
    constexpr lnt N = 400100, M = 5000100;
    constexpr louble EPS = 0.00000001, HLF = 0.5;
    lnt n, o = 0, t;
    lnt a[N], b[N], f[N];
    int lsn[M << 2], rsn[M << 2], val[M << 2];
    louble c[N], p[N], q[N];
    inline int cpy(int &__k) {
        if (__k)
            return __k;
        return __k = ++o;
    }

    inline louble clc(const int __x, const louble __y) { return p[__x] + q[__x] * (__y - c[__x]); }

    inline int upd(const int __x, const int __y, const int __z) {
        louble dif = clc(__x, __z) - clc(__y, __z);
        if (fabs(dif) <= EPS)
            return min(__x, __y);
        if (dif > 0)
            return __y;
        else
            return __x;
    }

    inline void chg(const int __x, const int __y, const int __k, const int __l, const int __r, int __v) {
        if (__l <= __x && __y <= __r) {
            int mid = (__x + __y) >> 1;
            if (clc(val[__k], mid) > clc(__v, mid))
                swap(val[__k], __v);
            if (__x == __y)
                return;
            if (clc(val[__k], __x - HLF) > clc(__v, __x - HLF))
                chg(__x, mid, cpy(lsn[__k]), __l, __r, __v);
            if (clc(val[__k], __y + HLF) > clc(__v, __y + HLF))
                chg(mid + 1, __y, cpy(rsn[__k]), __l, __r, __v);
            return;
        }

        int mid = (__x + __y) >> 1;
        if (__l <= mid)
            chg(__x, mid, cpy(lsn[__k]), __l, __r, __v);
        if (mid + 1 <= __r)
            chg(mid + 1, __y, cpy(rsn[__k]), __l, __r, __v);
        return;
    }

    inline int fnd(const int __x, const int __y, const int __k, const int __l) {
        if (__l <= __x && __y <= __l)
            return val[__k];
        int mid = (__x + __y) >> 1;
        int res = val[__k];
        if (__l <= mid)
            res = upd(res, fnd(__x, mid, cpy(lsn[__k]), __l), __l);
        if (mid + 1 <= __l)
            res = upd(res, fnd(mid + 1, __y, cpy(rsn[__k]), __l), __l);
        return res;
    }

    int _00() {
        scanf("%lld%lld", &n, &t);
        for (int i = 1; i <= n; ++i) {
            scanf("%lld%lld", &a[i], &b[i]);
            a[i] += a[i - 1];
            b[i] += b[i - 1];
        }

        c[0] = 0;
        p[0] = 0x1f3f3f3f3f3f3f3f;
        q[0] = 0;
        for (int i = 1; i <= n; ++i) {
            f[i] = (a[i] + t) * b[n];
            f[i] = min(f[i], (lnt)clc(fnd(-700000000, 700000000, 1, a[i] + t), a[i] + t));
            c[i] = a[i];
            p[i] = f[i];
            q[i] = b[n] - b[i];
            chg(-700000000, 700000000, 1, -700000000, 700000000, i);
        }

        printf("%lld\n", f[n]);
        return 0;
    }
}

int main() {
    // Audaces fortuna iuvat
    pnl::_00();
    return 0;
}
CPP
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
namespace pnl {
    typedef long long lnt;
    typedef long double louble;
    constexpr lnt N = 400100, M = 5000100;
    constexpr louble EPS = 0.00000001, HLF = 0.5;
    lnt n, o = 0, t;
    lnt a[N], b[N], f[N];
    int lsn[M << 2], rsn[M << 2], val[M << 2];
    louble c[N], p[N], q[N];
    inline int cpy(int &__k) {
        if (__k)
            return __k;
        return __k = ++o;
    }

    inline louble clc(const int __x, const louble __y) { return p[__x] + q[__x] * (__y - c[__x]); }

    inline int upd(const int __x, const int __y, const int __z) {
        louble dif = clc(__x, __z) - clc(__y, __z);
        if (fabs(dif) <= EPS)
            return min(__x, __y);
        if (dif > 0)
            return __y;
        else
            return __x;
    }

    inline void chg(const int __x, const int __y, const int __k, const int __l, const int __r, int __v) {
        if (__l <= __x && __y <= __r) {
            int mid = (__x + __y) >> 1;
            if (clc(val[__k], mid) > clc(__v, mid))
                swap(val[__k], __v);
            if (__x == __y)
                return;
            if (clc(val[__k], __x - HLF) > clc(__v, __x - HLF))
                chg(__x, mid, cpy(lsn[__k]), __l, __r, __v);
            if (clc(val[__k], __y + HLF) > clc(__v, __y + HLF))
                chg(mid + 1, __y, cpy(rsn[__k]), __l, __r, __v);
            return;
        }

        int mid = (__x + __y) >> 1;
        if (__l <= mid)
            chg(__x, mid, cpy(lsn[__k]), __l, __r, __v);
        if (mid + 1 <= __r)
            chg(mid + 1, __y, cpy(rsn[__k]), __l, __r, __v);
        return;
    }

    inline int fnd(const int __x, const int __y, const int __k, const int __l) {
        if (__l <= __x && __y <= __l)
            return val[__k];
        int mid = (__x + __y) >> 1;
        int res = val[__k];
        if (__l <= mid)
            res = upd(res, fnd(__x, mid, cpy(lsn[__k]), __l), __l);
        if (mid + 1 <= __l)
            res = upd(res, fnd(mid + 1, __y, cpy(rsn[__k]), __l), __l);
        return res;
    }

    int main() {
        scanf("%lld%lld", &n, &t);
        for (int i = 1; i <= n; ++i) {
            scanf("%lld%lld", &a[i], &b[i]);
            a[i] += a[i - 1];
            b[i] += b[i - 1];
        }

        c[0] = 0;
        p[0] = 0x1f3f3f3f3f3f3f3f;
        q[0] = 0;
        for (int i = 1; i <= n; ++i) {
            f[i] = (a[i] + t) * b[n];
            f[i] = min(f[i], (lnt)clc(fnd(-700000000, 700000000, 1, a[i]), a[i]));
            c[i] = a[i] - t;
            p[i] = f[i];
            q[i] = b[n] - b[i];
            chg(-700000000, 700000000, 1, -700000000, 700000000, i);
        }

        printf("%lld\n", f[n]);
        return 0;
    }
}

int main() {
    // Audaces fortuna iuvat
    pnl::main();
    return 0;
}

回复

共 0 条回复，欢迎继续交流。

正在加载回复...