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.

代码

/*
* 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;
for (int i = 0; i < n; ++i)
for (int i = 0; i < m; ++i)
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;
}

418 I'm a teapot