Little Pony and Lord Tirek

题目描述

Lord Tirek is a centaur and the main antagonist in the season four finale episodes in the series “My Little Pony: Friendship Is Magic”. In “Twilight’s Kingdom” (Part 1), Tirek escapes from Tartarus and drains magic from ponies to grow stronger.

The core skill of Tirek is called Absorb Mana. It takes all mana from a magic creature and gives them to the caster.

Now to simplify the problem, assume you have $n$ ponies (numbered from $1$ to $n$). Each pony has three attributes:

• $s_i$: amount of mana that the pony has at time $0$;
• $m_i$: maximum mana that the pony can have;
• $r_i$: mana regeneration per unit time.

Lord Tirek will do $m$ instructions, each of them can be described with three integers: $t_i, l_i, r_i$. The instruction means that at time $t_i$, Tirek will use Absorb Mana on ponies with numbers from $l_i$ to $r_i$ (both borders inclusive). We’ll give you all the m instructions in order, count how much mana Tirek absorbs for each instruction.

题意概述

有$n$匹马，第$i$匹马初始时有$s_i$点魔法，魔法上限为$m_i$，每秒增加$r_i$点魔法。有$m$次操作，第$i$次操作在第$t_i$秒进行，将区间$[l_i, r_i]$中马的魔法清零。求每次操作清除了多少点魔法。

数据范围：$1 \le n, m \le 10^5, \ 0 \le s_i \le m_i \le 10^5, \ 0 \le r_i \le 10^5, \ 0 \le t_i \le 10^9$。

算法分析

显然，答案只与两次询问的时间差有关。

用 set 维护一些不相交的区间（它们的并是整个序列），每段区间内所有马的上次操作时间相同。每次操作就相当于切割一些区间然后合并一些区间。由于每次至多切割两个区间，因此总共操作的区间个数是$O(n)$的。

考虑区间询问。每匹马都可以表示为一个分段函数，我们用主席树来维护，第$i$棵线段树表示经过$i$秒后每匹马的函数。因为有些马有初始魔法，所以需要建两棵主席树，一棵表示第$i$匹马的初始魔法为$s_i$，另一棵表示所有马的初始魔法为$0$。

那么只要预处理出主席树，对于每次操作，在 set 中找到其对应的一些区间，在主席树上询问答案，并更新区间。

代码

/*
 * So, is the glass half empty, half full, or just twice as large as it needs to
 * be?
 */

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>

template <typename T> void read(T &n) {
  char c;
  for (; (c = getchar()) < '0' || c > '9';)
    ;
  for (n = c - '0'; (c = getchar()) >= '0' && c <= '9'; (n *= 10) += c - '0')
    ;
}

typedef long long ll;
typedef int const ic;

static ic N = 100005;
int numn, root[N << 1];
struct Pony {
  int s, m, r;
} p[N];
struct Event {
  int t, p, b;
} e[N];
struct Query {
  int t, l, r;
  bool operator<(Query const &a) const { return l < a.l; }
} q[N];
struct SegmentTree {
  int child[2];
  ll a, b;
} node[N << 6];
std::set<Query> st;

void update(ic &root) {
  if (!root)
    return;
  node[root].a = node[node[root].child[0]].a + node[node[root].child[1]].a;
  node[root].b = node[node[root].child[0]].b + node[node[root].child[1]].b;
}

void modify(int &root, ic &nl, ic &nr, ic &p, ic &a, ic &b, ic &flag) {
  if (p > nr || nl > p)
    return;
  if (flag)
    node[++numn] = node[root], root = numn;
  else if (!root)
    root = ++numn;
  if (nl == nr) {
    node[root].a = a, node[root].b = b;
    return;
  }
  ic mid = (nl + nr) >> 1;
  modify(node[root].child[0], nl, mid, p, a, b, flag);
  modify(node[root].child[1], mid + 1, nr, p, a, b, flag);
  update(root);
}

ll query(ic &root, ic &nl, ic &nr, ic &t, ic &l, ic &r) {
  if (!root || l > nr || nl > r)
    return 0;
  if (l <= nl && nr <= r)
    return node[root].a * t + node[root].b;
  ic mid = (nl + nr) >> 1;
  return query(node[root].child[0], nl, mid, t, l, r) +
         query(node[root].child[1], mid + 1, nr, t, l, r);
}

int main() {
  int n, m;
  read(n);
  for (int i = 0; i < n; ++i)
    read(p[i].s), read(p[i].m), read(p[i].r);
  read(m);
  for (int i = 0; i < m; ++i)
    read(q[i].t), read(q[i].l), read(q[i].r), --q[i].l, --q[i].r;
  for (int i = 0; i < n; ++i)
    modify(root[0], 0, n - 1, i, p[i].r, 0, 0),
        e[i] = (Event){p[i].r ? p[i].m / p[i].r + 1 : N, i, p[i].m};
  std::sort(e, e + n, [](Event const &a, Event const &b) { return a.t < b.t; });
  for (int i = 1, p = 0; i < N; ++i) {
    root[i] = root[i - 1];
    for (; p < n && e[p].t == i; ++p)
      modify(root[i], 0, n - 1, e[p].p, 0, e[p].b, 1);
  }
  for (int i = 0; i < n; ++i)
    modify(root[N], 0, n - 1, i, p[i].r, p[i].s, 0),
        e[i] = (Event){p[i].r ? (p[i].m - p[i].s) / p[i].r + 1 : N, i, p[i].m};
  std::sort(e, e + n, [](Event const &a, Event const &b) { return a.t < b.t; });
  for (int i = 1, p = 0; i < N; ++i) {
    root[N + i] = root[N + i - 1];
    for (; p < n && e[p].t == i; ++p)
      modify(root[N + i], 0, n - 1, e[p].p, 0, e[p].b, 1);
  }
  st.insert((Query){0, 0, n - 1});
  for (int i = 0; i < m; ++i) {
    auto rec = st.lower_bound((Query){q[i].t, q[i].l, q[i].r});
    if (rec == st.end())
      --rec;
    for (; rec != st.begin() && rec->r >= q[i].l; --rec)
      ;
    if (rec->r < q[i].l)
      ++rec;
    auto tmp = rec;
    Query l = (Query){rec->t, rec->l, q[i].l - 1};
    ll ans = 0;
    for (; rec != st.end() && rec->l <= q[i].r; ++rec)
      ans += rec->t ? query(root[std::min(q[i].t - rec->t, N - 1)], 0, n - 1,
                            q[i].t - rec->t, std::max(rec->l, q[i].l),
                            std::min(rec->r, q[i].r))
                    : query(root[std::min(q[i].t - rec->t, N - 1) + N], 0,
                            n - 1, q[i].t - rec->t, std::max(rec->l, q[i].l),
                            std::min(rec->r, q[i].r));
    printf("%lld\n", ans), --rec;
    Query r = (Query){rec->t, q[i].r + 1, rec->r};
    for (; tmp != st.end() && tmp->l <= q[i].r;)
      st.erase(tmp++);
    st.insert((Query){q[i].t, q[i].l, q[i].r});
    if (l.l <= l.r)
      st.insert(l);
    if (r.l <= r.r)
      st.insert(r);
  }
  return 0;
}