首先给出结论：对于一个数列，某一个数字\(i\)的个数有\(cnt[i]\)个，那么此数字可以覆盖一个区间\([i-cnt[i]+1,i]\)，遍历每一个数字并记录每个区间，最后答案就是没有被覆盖到的数字的个数
证明：任意修改一个数字，会使一个\(cnt\)减一（这至多会产生一个没有被覆盖的数），另一个\(cnt\)加一（这至多会让一个原来没有被覆盖的数被覆盖）
而一个数列能被删除，当且仅当\([1,n]\)中每一个数字都被覆盖了一遍，而且只被覆盖了一遍（想下为什么？）
所以我们最少要让所有没被覆盖到的数字都被覆盖到
那么我们接下来构造一个方法来达到这个下界
由于\(cnt\)的和为\(n\)且原数列长为\(n\)，如果有数字没有被覆盖，那么证明就会有一些数字被重复覆盖或者说某一个数字产生的区间的左边界小于\(1\)，而且没被覆盖的数字的个数与后两者个数之和是相等的，我们每次操作从后两者中的某一个修改（让被重复覆盖的数字被覆盖的次数减一或者让产生区间左边界小于\(1\)的数字的个数减少一个），然后放到某一个空位上，每一次都这么干。最后刚好达到下界
证毕
那么考虑修改，对整个数列加一或者减一，就是让所有产生的区间往旁边移动一位，我们采用相对性的思路，让查询区间往旁边移动一位，这样就可以极大降低复杂度
但是随之产生一个问题，在查询区间移动的过程中，可以回出现某一个\(i\)小于区间左端点或者大于区间右端点，这时候是否对我们的结论有所影响？
当某一个\(i\)小于区间左端点的时候是没什么影响的，但大于区间右端点的时候是有影响的
因为每次修改操作会使某一个数的\(cnt\)减一，但是这个数产生的区间的右端点并没有改变，而是左端点加一
所以对一个大于查询区间右端点的数，我们肯定要把所有的这个数都修改掉（不然肯定无法删除），而每次只能让其产生的区间的左端点加一，所以我们不妨一次性让其\(cnt\)变为0（这与一次次修改没什么区别），即不算这一个点对查询区间的贡献，再按原结论做就没事了
这里线段树维护要用到类似扫描线的方法
标签：cnt,洛谷,数字,覆盖,一个,删数,5324,端点,区间 From： https://www.cnblogs.com/dingxingdi/p/17743578.html