火焰冲击 题解

题意简述

在一个 $P\times Q$ 的二维平面上有若干怪兽，每只怪兽有坐标、血量和击杀分数。两种技能分别对某段连续 $x$ 坐标区间或某段连续 $y$ 坐标区间内的怪兽造成 $1$ 点伤害；怪兽血量降到 $0$ 时死亡并获得分数。期间还会不断加入新怪兽。需要实时输出每次事件后的总分数。

一维问题的做法（势能线段树）

先考虑只有 $x$ 坐标的一维情形：所有怪兽排在一维坐标上，每次操作是对区间 $[l,r]$ 内的怪兽集体 $-1$，并删除血量降到 $0$ 的怪兽。

用线段树维护区间内血量的最小值：

• 区间整体 $-1$ 时直接打懒标记（区间最小值也 $-1$）；
• 若当前区间最小值 $>0$，说明没有怪兽死亡，无需下钻；
• 若最小值 $=0$，则递归到叶子，把该叶子（坐标）上血量最小的怪兽删除，并重新取该叶子的最小值。

每个叶子节点用一个 set（或小根堆）按血量维护该坐标上的所有怪兽。由于每个怪兽只会被删除一次，总删除次数是 $O(\text{怪兽总数})$；每次删除/插入/区间减都是 $O(\log P)$ 或 $O(\log Q)$。总复杂度 $O((N+M)\log N)$。

二维问题的关键 trick

二维时，一只怪兽同时受"水平攻击"（按 $x$ 坐标）和"垂直攻击"（按 $y$ 坐标）两类操作的影响，无法只靠一棵线段树维护。

核心 trick：把血量"拆"到两棵线段树上。

设怪兽当前血量为 $H$。我们在 $x$ 线段树（位于坐标 $x$）和 $y$ 线段树（位于坐标 $y$）上分别放入一个血量为 $\left\lceil\frac H2\right\rceil$ 的副本：

• 水平攻击只会打到 $x$ 线段树上的副本；
• 垂直攻击只会打到 $y$ 线段树上的副本。

性质：当两个副本都还活着（血量 $>0$）时，原怪兽一定没死。

证明：$x$ 副本还活着说明水平攻击次数 $<\lceil H/2\rceil$，$y$ 副本还活着说明垂直攻击次数 $<\lceil H/2\rceil$。总伤害 $\le 2\lceil H/2\rceil - 2 \le H - 1 < H$，故怪兽未死。

反之，当某个副本死亡时，原怪兽的血量至少减半：因为那个方向已经承受了至少 $\lceil H/2\rceil$ 次攻击，剩余血量 $\le H - \lceil H/2\rceil \le \lfloor H/2\rfloor$。

因此流程为：

1. 每只怪兽初始在两个副本中分别放入 $\lceil H/2\rceil$ 血量；
2. 攻击时，对相应线段树区间 $-1$；
3. 若某线段树最小值降到 $0$，找到对应怪兽，同时从两棵线段树中取出该怪兽的两个副本，据此精确算出它当前的真实剩余血量（见下）；
4. 若真实血量为 $0$，怪兽死亡，加分；否则它的血量已至少减半，重新用新的 $\lceil H/2\rceil$ 血量插入两个副本。

由于每次"副本死亡"怪兽血量至少减半，每只怪兽至多经历 $O(\log H)$ 次这样的重构；而 $H\le 10^5$，故每只怪兽至多 $O(\log H)\approx 17$ 次。

精确计算剩余血量

设某怪兽当前记录的血量为 $H$（它对应的两个副本各为 $\lceil H/2\rceil$）。当其中一个副本死亡时，我们需要算出它实际剩余血量：

• 原来两个副本的总血量 = $2\cdot\lceil H/2\rceil$；
• 从 $x$ 线段树删除副本时，返回该副本当前剩余血量（即 $\lceil H/2\rceil$ 减去它承受的水平攻击次数）；
• 同理从 $y$ 线段树删除副本，返回其剩余血量。

于是"已经承受的总伤害" = 副本初始总血量 − 两个副本当前剩余血量之和。用它更新真实血量 $H$，若 $H=0$ 则死亡，否则重新 add。

算法总结

• 开两棵线段树，分别按 $x$ 坐标和 $y$ 坐标维护，叶子用 set 存该坐标上的怪兽副本（键为副本血量）。
• 线段树支持：单点插入/删除（set 操作）、区间减 $1$（懒标记）、查询全局最小值。
• 每个事件：
  • 类型 1/2：解密出 $l,r$，对相应线段树区间减 $1$，然后 while 全局最小值 $=0$，取出该怪兽、从两棵树删除副本、重算真实血量、决定死亡加分或重新插入。
  • 类型 3：插入新怪兽（初始血量 $H$，两棵树各放 $\lceil H/2\rceil$）。
• 输出当前总分数。

复杂度

每只怪兽至多被"重构" $O(\log H)$ 次，每次重构涉及两棵树上的删除与插入，各 $O(\log N)$。

• 时间复杂度： $O\big((N+M)\log H\cdot \log(N+M)\big)$，其中 $\log H\le 17$。
• 空间复杂度： $O(N+M)$。

实测在 $N+M\approx 2\times 10^5$ 时运行时间约 $0.4$ 秒。

参考代码

#include <bits/stdc++.h>
const int N = 2e5 + 9;
using namespace std;
struct Seg {
    set<pair<int, int> > st[N];
    pair<int, int> sum[N << 2];
    int tag[N << 2];
    int val[N];
    inline void up(int x) { sum[x] = min(sum[x<<1], sum[x<<1|1]); }
    inline void add(int x, int y) { sum[x].first += y; tag[x] += y; }
    inline void down(int x) {
        if (!tag[x]) return;
        add(x<<1, tag[x]), add(x<<1|1, tag[x]), tag[x] = 0;
    }
    inline void modify(int x, int l) {
        sum[x] = st[l].empty() ? make_pair((int)1e9, 0) : make_pair(st[l].begin()->first + tag[x], st[l].begin()->second);
    }
    int del(int x, int l, int r, int pos, int d) {
        if (l == r) { st[l].erase({val[d], d}); modify(x, l); return val[d] + tag[x]; }
        down(x);
        int mid = l + r >> 1, ans;
        if (mid >= pos) ans = del(x<<1, l, mid, pos, d);
        else ans = del(x<<1|1, mid + 1, r, pos, d);
        up(x); return ans;
    }
    void modify(int x, int l, int r, int pos, pair<int,int> d) {
        if (l == r) { d.first -= tag[x]; val[d.second] = d.first; st[l].insert(d); modify(x, l); return; }
        down(x);
        int mid = l + r >> 1;
        if (mid >= pos) modify(x<<1, l, mid, pos, d);
        else modify(x<<1|1, mid + 1, r, pos, d);
        up(x);
    }
    void modify(int x, int l, int r, int ll, int rr) {
        if (ll <= l && r <= rr) { add(x, -1); return; }
        down(x);
        int mid = l + r >> 1;
        if (mid >= ll) modify(x<<1, l, mid, ll, rr);
        if (mid < rr) modify(x<<1|1, mid + 1, r, ll, rr);
        up(x);
    }
    void build(int x, int l, int r) {
        sum[x] = { (int)1e9, 0 };
        if (l == r) return;
        int mid = l + r >> 1;
        build(x<<1, l, mid), build(x<<1|1, mid + 1, r);
    }
} t[2];

int n, m, p, q;
int x[N], y[N], h[N], v[N];

inline void add(int i) {
    t[0].modify(1, 0, p - 1, x[i], { (h[i] + 1) / 2, i });
    t[1].modify(1, 0, q - 1, y[i], { (h[i] + 1) / 2, i });
}

int main() {
    scanf("%d%d%d%d", &n, &m, &p, &q);
    t[0].build(1, 0, p - 1), t[1].build(1, 0, q - 1);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d%d", &x[i], &y[i], &h[i], &v[i]);
        add(i);
    }
    int ans = 0;
    while (m--) {
        int opt; scanf("%d", &opt);
        if (opt == 1) {
            int l, r; scanf("%d%d", &l, &r);
            l = (l + ans) % p, r = (r + ans) % p;
            if (l > r) swap(l, r);
            t[0].modify(1, 0, p - 1, l, r);
            while (t[0].sum[1].first == 0) {
                int i = t[0].sum[1].second;
                h[i] -= ((h[i] + 1) / 2) * 2 - t[0].del(1, 0, p - 1, x[i], i) - t[1].del(1, 0, q - 1, y[i], i);
                if (h[i] == 0) ans += v[i];
                else add(i);
            }
        } else if (opt == 2) {
            int l, r; scanf("%d%d", &l, &r);
            l = (l + ans) % q, r = (r + ans) % q;
            if (l > r) swap(l, r);
            t[1].modify(1, 0, q - 1, l, r);
            while (t[1].sum[1].first == 0) {
                int i = t[1].sum[1].second;
                h[i] -= ((h[i] + 1) / 2) * 2 - t[0].del(1, 0, p - 1, x[i], i) - t[1].del(1, 0, q - 1, y[i], i);
                if (h[i] == 0) ans += v[i];
                else add(i);
            }
        } else {
            n++;
            scanf("%d%d%d%d", &x[n], &y[n], &h[n], &v[n]);
            add(n);
        }
        printf("%d\n", ans);
    }
}