Hands that shed innocent blood

摘要： 最容易想到的思路就是從左往右遍歷，遍歷的過程中，如果當前劍長不等於0，就從當前位置往左，把劍長範圍內的人都+1，表示被砍到1次。時間複雜度$O(n^2)$ 上面的解法很明顯會超時，正確解法應該是線段樹，或者差分加字首和 如果用線段樹做就是裸體，沒什麼好說的，這裡說一下用差分加...

最容易想到的思路就是從左往右遍歷，遍歷的過程中，如果當前劍長不等於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);
}
}