题解 - Little Pony and Lord Tirek

Macesuted QWQ LV 8 SU @ 2022-3-25 7:30:24

Statement

有 $n$ 匹魔法小马，第 $i$ 匹小马在初始时具有 $s_i$ 的魔法值，每秒钟回复 $r_i$ 魔法值，魔法值上限为 $m_i$ 。

你会进行 $q$ 次操作，每次操作在 $t_i$ 时刻会将 $l_i$ 到 $r_i$ 范围内的所有小马的魔法值吸走，吸走后此范围内小马魔法值归零，请你求出每次操作吸走的魔法值总和。

$1 \le n,q \le 10^5$

Solution

对于有区间归零操作的问题，我们的常用方法是记录每个位置上次被清零的时间。考虑一个最简单的简化问题版本：所有操作均为全局操作（即 $l_i = 1,~r_i = n$ ）。此时每次询问时所有位置离上次清零的时间均相同，令该时间为 $t$ ，我们发现所有 $\frac {m_i} {r_i} \le t$ 的小马的魔法值都会达到上限 $m_i$ ，其他小马的魔法值则为 $r_i \times t$ 。因此我们可以将所有小马按照 $\frac {m_i} {r_i}$ 排序，二分找到序列中 $\le t$ 的最大位置 $p$ ，则 $\sum_{1 \le i \le p} m_i + t \times (\sum_{p < i \le n} r_i)$ 即为答案。

考虑在清零操作为全局而询问操作为区间时该怎么做，即想要求得 $i \in [l,~r],~\frac {m_i} {r_i} \le t$ 的所有元素的 $m_i$ 和与 $r_i$ 和。经典的静态二维数点问题，为降低复杂度可以在 $\frac {m_i} {r_i}$ 一维上进行可持久化。具体的，将所有小马的 $\frac {m_i} {r_i}$ 排序，可持久化线段树的第 $i$ 个版本中插入排序后的前 $i$ 个元素。则二维数点问题转换为在排序后的数组上二分找到最大的 $\le t$ 的位置，在其对应的版本上询问 $[l,~r]$ 区间信息，复杂度 $O(\log n)$ 。

再考虑原问题，若全局的清零时间不同时应该怎么做。发现使用珂朵莉树维护每个连续清零时间相同的连续段即可。因为每次修改后会将区间内的所有元素的清零时间归零，每次询问时暴力扫描的每一块在询问后会被合并为一块，因此全局暴力扫描的时间复杂度为珂朵莉上块数的总和，而每次操作最多只会新建两个块，因此复杂度得以保证。对于珂朵莉树上的每个连续段，由于段内清零时间相同，做上述的可持久化线段树上查询即可。

另外，一个比较好的处理初始值 $s_i$ 的方法是将第 $i$ 个小马的初始上次清零时间设为 $- \frac {s_i} {r_i}$ 。

总时间复杂度 $O((n + q) \log n)$ 。

Code

View on GitHub

Code

/**
 * @file 453E.cpp
 * @author Macesuted (i@macesuted.moe)
 * @date 2022-03-20
 *
 * @copyright Copyright (c) 2022
 *
 */

#include <bits/stdc++.h>
using namespace std;

namespace IO {
const int SIZE = 1 << 20;
char Ibuf[SIZE], *Il = Ibuf, *Ir = Ibuf, Obuf[SIZE], *Ol = Obuf, *Or = Ol + SIZE - 1, stack[32];
char isspace(char c) { return c == ' ' || c == '\t' || c == '\n' || c == '\v' || c == '\f' || c == '\r'; }
void fill(void) { return Ir = (Il = Ibuf) + fread(Ibuf, 1, SIZE, stdin), void(); }
void flush(void) { return fwrite(Obuf, 1, Ol - Obuf, stdout), Ol = Obuf, void(); }
char buftop(void) { return Ir == Il ? fill(), *Il : *Il; }
char getch(void) { return Il == Ir ? fill(), Il == Ir ? EOF : *Il++ : *Il++; }
void putch(char x) { return *Ol++ = x, Ol == Or ? flush() : void(); }
template <typename T>
T read(void) {
    T x = 0, f = +1;
    char c = getch();
    while (c < '0' || c > '9') c == '-' ? void(f = -f) : void(), c = getch();
    while ('0' <= c && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getch();
    return x * f;
}
template <typename T>
void write(T x) {
    if (!x) putch('0');
    if (x < 0) putch('-'), x = -x;
    int top = 0;
    while (x) stack[top++] = (x % 10) ^ 48, x /= 10;
    while (top) putch(stack[--top]);
    return;
}
string getstr(const string& suf = "") {
    string s = suf;
    while (isspace(buftop())) getch();
    while (Il != Ir) {
        char* p = Il;
        while (Il < Ir && !isspace(*Il) && *Il != EOF) Il++;
        s.append(p, Il);
        if (Il < Ir) break;
        fill();
    }
    return s;
}
void putstr(string str, int begin = 0, int end = -1) {
    if (end == -1) end = str.size();
    for (int i = begin; i < end; i++) putch(str[i]);
    return;
}
struct Flusher_ {
    ~Flusher_() { flush(); }
} io_flusher_;
}  // namespace IO
using IO::getch;
using IO::getstr;
using IO::putch;
using IO::putstr;
using IO::read;
using IO::write;

bool mem1;

#define maxn 100005

typedef pair<long long, long long> pll;

class SegmentTree {
   private:
    struct Node {
        Node *l, *r;
        long long sumR, sumM;
        Node(void) { l = r = NULL, sumR = sumM = 0; }
    };

    vector<Node*> roots;
    int n;

    Node* newRoot(void) { return roots.push_back(roots.back()), roots.back(); }
    void exist(Node*& p, Node* o) {
        if (p != o && p != NULL) return;
        return p = new Node(), *p = *o, void();
    }
    void pushUp(Node* p) {
        p->sumR = p->sumM = 0;
        if (p->l != NULL) p->sumR += p->l->sumR, p->sumM += p->l->sumM;
        if (p->r != NULL) p->sumR += p->r->sumR, p->sumM += p->r->sumM;
        return;
    }
    pll merge(pll a, pll b) { return {a.first + b.first, a.second + b.second}; }
    void insert(Node*& p, Node* o, int l, int r, int qp, int vr, int vm) {
        if (o == NULL) p = o = new Node();
        exist(p, o);
        if (l == r) return p->sumR = vr, p->sumM = vm, void();
        int mid = (l + r) >> 1;
        qp <= mid ? insert(p->l, o->l, l, mid, qp, vr, vm) : insert(p->r, o->r, mid + 1, r, qp, vr, vm);
        return pushUp(p);
    }
    pll query(Node* p, int l, int r, int ql, int qr) {
        if (p == NULL) return {0, 0};
        if (ql <= l && r <= qr) return {p->sumR, p->sumM};
        int mid = (l + r) >> 1;
        if (qr <= mid) return query(p->l, l, mid, ql, qr);
        if (ql > mid) return query(p->r, mid + 1, r, ql, qr);
        return merge(query(p->l, l, mid, ql, qr), query(p->r, mid + 1, r, ql, qr));
    }

   public:
    SegmentTree(void) { roots.push_back(NULL); }
    void resize(int _n) { return n = _n, void(); }
    void insert(int p, int r, int m) { return newRoot(), insert(roots.back(), roots[(int)roots.size() - 2], 1, n, p, r, m); }
    pll query(int ver, int l, int r) { return query(roots[ver], 1, n, l, r); }
} ST;

pair<double, int> t[maxn];
long long rsum[maxn];

class OldDriverTree {
   private:
    struct Node {
        int l, r;
        double tim;
        bool operator<(const Node& oth) const { return this->l < oth.l; }
    };

    set<Node> S;
    int n;

    void split(Node p, int v) {
        S.erase(p), S.insert({p.l, v, p.tim});
        if (v < p.r) S.insert({v + 1, p.r, p.tim});
        return;
    }

   public:
    void build(int _n, double b[]) {
        n = _n;
        for (int l = 1, r; l <= n; l = r + 1) {
            r = l;
            while (r < n && b[r + 1] == b[r]) r++;
            S.insert({l, r, b[l]});
        }
        return;
    }
    long long query(int T, int l, int r) {
        auto x = --S.lower_bound({l + 1, 0, 0});
        if (x->l != l) split(*x, l - 1);
        x = --S.lower_bound({r + 1, 0, 0});
        if (x->r != r) split(*x, r);
        long long ans = 0;
        for (auto i = S.lower_bound({l, 0, 0}); i != S.end() && i->r <= r; i = S.erase(i)) {
            double tim = T - i->tim;
            int p = lower_bound(t + 1, t + n + 1, make_pair(tim, 0)) - t;
            pll ret = ST.query(p - 1, i->l, i->r);
            ans += ret.second + (long long)((rsum[i->r] - rsum[i->l - 1] - ret.first) * tim + 0.5);
        }
        S.insert({l, r, (double)T});
        return ans;
    }
} ODT;

int s[maxn], m[maxn], r[maxn];
double b[maxn];

set<pll> S;

void solve(void) {
    int n = read<int>();
    for (int i = 1; i <= n; i++) {
        s[i] = read<int>(), m[i] = read<int>(), r[i] = read<int>();
        if (r[i])
            t[i] = {1. * m[i] / r[i], i}, b[i] = -1. * s[i] / r[i];
        else
            S.emplace(i, s[i]), t[i] = {1e18, i}, b[i] = 0;
    }
    for (int i = 1; i <= n; i++) rsum[i] = rsum[i - 1] + r[i];
    sort(t + 1, t + n + 1);
    ST.resize(n), ODT.build(n, b);
    for (int i = 1; i <= n; i++) ST.insert(t[i].second, r[t[i].second], m[t[i].second]);
    int q = read<int>();
    while (q--) {
        int t = read<int>(), l = read<int>(), r = read<int>();
        long long ans = ODT.query(t, l, r);
        for (auto i = S.lower_bound({l, 0}); i != S.end() && i->first <= r; i = S.erase(i)) ans += i->second;
        write(ans), putch('\n');
    }
    return;
}

bool mem2;

int main() {
    ios::sync_with_stdio(false);
#ifdef MACESUTED
    cerr << "Memory Cost: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl;
#endif

    int _ = 1;
    while (_--) solve();

#ifdef MACESUTED
    cerr << "Time Cost: " << clock() * 1000. / CLOCKS_PER_SEC << "MS" << endl;
#endif
    return 0;
}

ID

5128

时间

3000ms

内存

256MiB

难度

标签

递交数

已通过

上传者

Hydro

1 条题解

Statement

Solution

Code

Little Pony and Lord Tirek

信息

状态

开发

支持

1 条题解

Statement

Solution

Code

Little Pony and Lord Tirek

信息

状态

开发

支持

还没有账户？

登录