洛谷P2667 [TJOI2012] 防御题解

题目链接：P2667 [TJOI2012] 防御

题意：

在一个塔防小游戏中，有很多防线。每条防线由一排 \(n\) 个独立的防御体 \([1 : n]\) 进行防御。

游戏过程中，会不断有敌人对防线进行攻击，每次攻击会指定防御体 \([l : r]\) 进行攻击力为 \(a\) 的攻击。第一防线具有护甲，护甲承受攻击后，对应的防御体所受到的伤害为攻击力，但护甲承受的伤害总量到达一定程度后就会破碎，此时防御体所受的伤害加倍。目前第一防线的力量充足，玩家致力于对后面的防线的建设，不过为确认游戏进度和第一防线的情况，玩家会不时地将鼠标移动到第一防线的某个防御体上，以查看其所受到的伤害。

输入格式：

第一行，两个整数 \(n\) 和 \(q\)，分别表示防御体个数以及攻击和查询的总数。

第二行，\(n\) 个数，表示每个防御体护甲的承受能力 \(p_i\) 。

接下来 \(q\) 行，每行可能具有如下形式：

A l r a 表示对防御体 \(l,l+1,\cdots,r\) 进行攻击力为 \(a\) 的攻击；

Q x 表示查询防御体 \(x\) 目前所受到的伤害，初始时伤害为 \(0\) 。

输出格式：

一行，一个整数，表示所有查询结果之和对 \({10}^9+9\) 取模的余数。

\(100 \%\) 的数据，\(1 \le n \le 10^5\)，\(1 \le q \le 10^5\)，\(0 \le p_i \le 10^6\)，\(0 \le a \le 10^4\)。

注意到 \(p_i\) 的范围不大，并且每个位置只可能被打爆一次。

因此我们可以维护区间内的护盾最小值，然后暴力更新护盾是否被打爆。

这道题维护区间和不太方便，因此我们可以直接维护区间的增量，类似与区间和的lazytag。

时间复杂度 \(\mathcal{O}(n \log nV)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9 + 9;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))
#define ls(at) ((at) << 1)
#define rs(at) ((at) << 1 | 1)

int n, res, a[N]; char boom[N];
struct node { int mn, tag, val; } tr[N * 4];
void push_up(int at) {
    down(tr[at].mn = tr[ls(at)].mn, tr[rs(at)].mn);
}
void push_down(int at)
{
    if(!tr[at].tag) return;
    if(tr[ls(at)].mn != INF) tr[ls(at)].mn -= tr[at].tag;
    if(tr[rs(at)].mn != INF) tr[rs(at)].mn -= tr[at].tag;
    tr[ls(at)].tag += tr[at].tag; tr[rs(at)].tag += tr[at].tag; 
    tr[at].tag = 0;
}
void build(int l = 1, int r = n, int at = 1)
{
    if(l == r) { tr[at].mn = a[l] ? a[l] : INF; return; }
    int mid = (l + r) >> 1;
    build(l, mid, ls(at)); build(mid + 1, r, rs(at)); push_up(at);
}
void proc(int l, int r, int at, int k)
{
    if(l == r) {
        a[l] = a[l] - tr[at].mn + k;
        tr[at].mn = INF; boom[l] = true; return;
    }
    push_down(at); int mid = (l + r) >> 1;
    if(tr[ls(at)].mn <= k) proc(l, mid, ls(at), k);
    if(tr[rs(at)].mn <= k) proc(mid + 1, r, rs(at), k);
    push_up(at);
}
void update(int nl, int nr, int k, int l = 1, int r = n, int at = 1)
{
    if(nl <= l && r <= nr)
    {
        tr[at].val += k;
        if(tr[at].mn <= k) proc(l, r, at, k);
        if(tr[at].mn != INF) { tr[at].mn -= k, tr[at].tag += k; }
        return; 
    }
    push_down(at); int mid = (l + r) >> 1;
    if(nl <= mid) update(nl, nr, k, l, mid, ls(at));
    if(nr > mid) update(nl, nr, k, mid + 1, r, rs(at));
    push_up(at);
}
int query(int x, int l = 1, int r = n, int at = 1)
{
    if(l == r) return tr[at].val;
    push_down(at); int mid = (l + r) >> 1;
    if(x <= mid) return tr[at].val + query(x, l, mid, ls(at));
    else return tr[at].val + query(x, mid + 1, r, rs(at));
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int q; cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(build(); q--; ) {
        char op; cin >> op;
        if(op == 'A') {
            int l, r, k; cin >> l >> r >> k; update(l, r, k);
        }else if(op == 'Q') {
            int x; cin >> x;
            if(boom[x]) {
                res = (res + query(x) * 2 - a[x]) % mod;
            }else res = (res + query(x)) % mod;
        }
    }
    cout << (res + mod) % mod << '\n';
    return 0;
}