导弹防御[差分]

Solution

因为B的防护罩开启时间上的区间已经确定, 所以只需要考虑A防护时间上的区间即可
因为只需考虑A受到的伤害, 所以开始时将所有可能对A造成伤害的导弹保存, 其余不管
现在手上就有了一个导弹序列, 那该怎么处理呢?

对于一个即将击中A的导弹, 想要拦截它, 必须使用防御区间覆盖其所有落在A的时间点
(由于导弹会反弹, 所以一个导弹可能会多次光临)

暂且称导弹到达A的时刻为危险时刻

可以使A的保护区间左端点从最早危险时刻至最晚危险时刻遍历
每次计算该区间拦截成功的导弹伤害, 用总伤害减去减免伤害即为受到的伤害

此过程可以使用差分维护
具体分两种情况讨论

设该导弹到达的时刻为 $u$ , 导弹伤害为 $w$ , 导弹速度为 $v$ , 差分数组 $C$

反弹一次成功击中B, 此时只需要防御区间覆盖一个危险时刻 $u$ 即可, $l = m a x {0, u - T A}$
反弹多次成功击中B, 此时需要防御区间覆盖这个导弹的危险时刻 $u$ 及衍生出的所有危险时刻, 可以 $O (1)$ 计算出最后一个危险时刻为 $T e m p = (⌊ \frac{X + T B - u - v}{2 v} ⌋ + 1) * 2 v + u$ , 于是 $l = m a x {0, T e m p - T A}$

如图, $P = ⌊ \frac{X + T B - (u + v)}{2 v} ⌋ * 2 v$ ,
$T e m p = P + 2 v + u = (⌊ \frac{X + T B - u - v}{2 v} ⌋ + 1) * 2 v + u$

对于上方所有的 $l, u$ , 都采取操作 $C [l] + = w, C [u + 1] - = w$ , 最后 $O (N)$ 扫, 取最大减免伤害即可.

Code

#include<bits/stdc++.h>
#define reg register

const int maxn = 10005;
typedef long long ll;

int TA;
int TB;
int X;
int N;
int M;
int cnt;

struct Attack{
        int v, tim, w;
        Attack(int v=0, int tim=0, int w=0):v(v), tim(tim), w(w) {}
} Atk[maxn << 2];

struct Cha{ int tim, w; } C[maxn<<2];

bool cmp(Cha a, Cha b){ return a.tim==b.tim?a.w<b.w:a.tim<b.tim; }

void Work(){
        cnt = 0;
        scanf("%d%d%d", &X, &N, &M);
        int u, v, w;
        for(reg int i = 1; i <= N; i ++){
                scanf("%d%d%d", &u, &v, &w);
                if(u+v < X || u+v > X+TB) continue ;
                Atk[++ cnt] = Attack(v, u+(v<<1), w);
        }
        for(reg int i = 1; i <= M; i ++){
                scanf("%d%d%d", &u, &v, &w);
                Atk[++ cnt] = Attack(v, u+v, w);
        }
        int tot = 0;
        int sum = 0;
        for(reg int i = 1; i <= cnt; i ++){
                v = Atk[i].v, u = Atk[i].tim, w = Atk[i].w;
                sum += w;
                int l;
                if(u+v < X || u+v > X+TB) l = std::max(0, u-TA);
                else{
                        int Temp = ((X+TB-u-v)/v/2 + 1) * 2*v + u;
                        l = std::max(0, Temp-TA);
// int t = (X+TB-u-v)/v/2;
// l = std::max(u+v*2*(t+1)-TA, 0);
                }
                if(l > u) continue ;
                C[++ tot] = (Cha){ u+1, -w };
                C[++ tot] = (Cha){ l, w };
        }
        int Ans = 0, temp = 0;
        std::sort(C+1, C+tot+1, cmp);
        for(reg int i = 1; i <= tot; i ++){
                temp += C[i].w;
                Ans = std::max(temp, Ans);
        }
        if(sum < Ans) printf("Yes\n");
        std::cout << sum - Ans << std::endl;
// printf("%lld\n", sum - Ans);
}

int main(){
        freopen("missile.in", "r", stdin);
        freopen("missile.out", "w", stdout);
        while(~scanf("%d%d", &TA, &TB)) Work();
        return 0;
}
/* 2 2 2 1 0 1 1 10 4 5 3 2 2 1 2 10 1 5 7 1 3 2 0 4 8 */