题目名称 3806. [JZOI 2022 day3]索引
输入输出 jzoi2022_index.in/out
难度等级 ★★☆
时间限制 2000 ms (2 s)
内存限制 512 MiB
测试数据 1
题目来源 Gravataryuan 于2022-11-24加入
开放分组 全部用户
提交状态
分类标签
二分法
查看题解 分享题解
通过:1, 提交:1, 通过率:100%
Gravataryuan 100 0.000 s 0.00 MiB C++
关于 索引 的近10条评论(全部评论)

3806. [JZOI 2022 day3]索引

★★☆   输入文件:jzoi2022_index.in   输出文件:jzoi2022_index.out   简单对比
时间限制:2 s   内存限制:512 MiB

【题目描述】

给定一个由 $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$;

【来源】

焦作一中 NOIP 2022 模拟赛2022.11.24 pro2