bzoj 5209: [Tjoi2012]防御

题意：

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

题解：

护甲破碎后伤害加倍，相当于给护甲的伤害附加到防御体上，所以我们可以在护甲破碎后继续维护它受到的伤害，询问的时候加起来就好了。还有一个问题，就是当护甲破碎的时候，这一次给防御体的伤害还是一倍的，所以护甲破碎后承受的伤害（这一次中）不会记到防御体上，也就是说，当护甲破碎的时候，如果它这一次额外受到了伤害我们要手动把它清掉。因为每个护甲只会破一次，所以我们把操作离线下来，然后把每个A操作当成一个线段，然后从$1$到$n$扫过去，二分一下每个点的护甲什么时候破，记下每个时间哪些节点的护甲会破。后面做的时候暴力修改就好了。

代码：

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

const int MOD = 1000000009;
int n, q, m = 0, p[100010], ans = 0;
struct th
{
    int op, l, r, x;
} c[100010];
struct mod
{
    int x, t;
};
vector<mod> mo[100010];
vector<int> t[100010];
struct BIT
{
    int n;
    long long s[100010];
    int lb(int x) { return x & -x; }
    void add(int x, int y)
    {
        for (int i = x; i <= n; i += lb(i))
            s[i] += y;
    }
    long long get(int x)
    {
        long long ans = 0;
        for (int i = x; i > 0; i -= lb(i))
            ans += s[i];
        return ans;
    }
} a, b, d;

int main()
{
    scanf("%d%d", &n, &q);
    a.n = b.n = n;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &p[i]);
        a.add(i, p[i] - p[i - 1]);
    }
    for (int i = 1; i <= q; i++)
    {
        char op[5];
        scanf("%s", op);
        if (op[0] == 'A')
        {
            c[i].op = 0;
            scanf("%d%d%d", &c[i].l, &c[i].r, &c[i].x);
            mo[c[i].l].push_back((mod){c[i].x, i});
            mo[c[i].r + 1].push_back((mod){-c[i].x, i});
        }
        else
        {
            c[i].op = 1;
            scanf("%d", &c[i].x);
        }
    }
    d.n = q;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < mo[i].size(); j++)
            d.add(mo[i][j].t, mo[i][j].x);
        int l = 0, len = q + 1;
        while (len)
        {
            int md = l + (len >> 1);
            if (d.get(md) < p[i])
            {
                l = md + 1;
                len = len - (len >> 1) - 1;
            }
            else
                len >>= 1;
        }
        t[l].push_back(i);
    }/*
    for (int i = 1; i <= q; i++)
    {
        printf("i: %d\n", i);
        for (int x : t[i])
            printf("%d ", x);
        puts("");
    }
    for (int i = 1; i <= n; i++)
        printf("%lld %lld\n", a.get(i), b.get(i));
    puts("");*/
    for (int i = 1; i <= q; i++)
    {
        if (c[i].op == 0) // A
        {
            a.add(c[i].l, -c[i].x);
            a.add(c[i].r + 1, c[i].x);
            b.add(c[i].l, c[i].x);
            b.add(c[i].r + 1, -c[i].x);
            for (int j = 0; j < t[i].size(); j++)
            {
                int hh = a.get(t[i][j]);
                a.add(t[i][j], -hh);
                a.add(t[i][j] + 1, hh);
            }
        }
        else
        {
            int x = c[i].x;
            long long aa = a.get(x), bb = b.get(x);
            // printf("%lld\n", aa < 0 ? bb - aa : bb);
            (ans += (aa < 0 ? bb - aa : bb) % MOD) %= MOD;
        }/*
        for (int i = 1; i <= n; i++)
            printf("%lld %lld\n", a.get(i), b.get(i));
        puts("");*/
    }
    printf("%lld\n", ans);
}