3806. [JZOI 2022 day3]索引

【题目描述】

给定一个由 $n$ 个不同整数组成的严格递增的数组 $A[1 … n]$，请问是否存在一个索引 $i$ 使得 $A[i] = i$ 成立。

一共有 $K$ 次询问。从第二次询问开始，第 $t$ 次询问会在第 $t − 1$ 次询问的数组 $A_{t−1}$ 的基础上进⾏一次区间修改。每次修改给出三个整数 $L (1\ ≤\ L\ ≤\ n), R\ (L\ ≤\ R\ ≤\ n), C$ ，则

• $i\ \in\ [L,\ R]\ :\ A_t[i]\ =\ A_{t-1}[i]\ +\ C$
• $i\ \notin\ [L,\ R]\ :\ A_t[i]\ =\ A_{t-1}[i]$

【输入格式】

第一⾏两个整数 $K, n$，表示询问次数和数组⻓度。

第二⾏ $n$ 个整数，代表 $A_1[1 … n]$。

之后 $K − 1$ ⾏每⾏三个整数 $L, R, C $，表示从第二次询问起的区间修改。

【输出格式】

输⼊数据保证每次询问的数组都满⾜元素严格递增，且修改前后数组中元素的值在 $32$ 位有符号整数范围内。

【样例输入】

3 4
1 2 3 4
2 4 1
1 1 1

【样例输出】

YES
YES
NO

【样例1说明】

对于原始的数组，四个位置都满⾜，所以输出 $YES$ 。

修改得到的第 $2$ 组数组为 $1, 3, 4, 5，$第一个位置满足，所以输出 $YES$ 。

修改得到的第 $3$ 组数组为 $2, 3, 4, 5，$所有位置的元素都不满足 $A[i] = i$，所以输出 $NO$ 。

【数据规模与约定】

提示：输⼊输出量较⼤，建议使⽤输⼊输出优化。

对于其中 $70\%$ 的数据，保证 $K ⋅ n ≤ 10^8$；

对于其中 $100\%$ 的数据，保证 $1\ ≤\ K\ ≤\ 1000，1\ ≤\ n\ ≤\ 10^7$；

【来源】