Hands that shed innocent blood

最容易想到的思路就是从左往右遍历，遍历的过程中，如果当前剑长不等于 0，就从当前位置往左，把剑长范围内的人都 + 1，表示被砍到 1 次。时间复杂度 $O (n^2)$

上面的解法很明显会超时，正确解法应该是线段树，或者差分加前缀和

如果用线段树做就是裸题，没什么好说的，这里说一下用差分加前缀和的做法

首先定义差分数组 $d$，初始值全部为 0，差分的性质是可以将区间修改改为单点修改，例如要将 $[L,R]$ 区间内所有值加上 $C$，相当于将差分数组中 $d [L]+=C$ 以及 $d [R+1]-=C$。差分还有一个性质是：差分序列的前缀和等于原始数组，利用这两个性质，我们就可以快速统计出整个区间每个人被砍过的次数

具体做法是，遍历剑长数组，如果不为 0，就将 $d [max (0,i - arr [i])]+=1$ 以及 $d [max (0, i - 1) + 1] -= 1$

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        long[] arr = new long[n]; // 原始数组
        long[] d = new long[n]; // 差分序列
        long[] life = new long[n]; // 生命值
        for (int i = 0; i < n; i++) {
            arr[i] = cin.nextInt();
            if (arr[i] != 0) { // 剑长不等于0才修改差分序列
                d[(int) Math.max(0, i - arr[i])] += 1; // d[L] += 1
                d[Math.max(i - 1, 0) + 1] -= 1; // d[R + 1] -= 1
            }
        }
        for (int i = 0; i < n; i++)
            life[i] = cin.nextInt();
        
        long ans = d[0] >= life[0] ? 1 : 0; // 因为差分序列的第一个值就是原始序列，所以第一个值直接结算
        for (int i = 1; i < n - 1; i++) { // 最后一个人不用考虑，因为没有人砍他
            d[i] += d[i - 1]; // 前缀和
            ans += (d[i] > life[i] ? 1 : 0);
        }
        System.out.println(n - ans);
    }
}