#P7769. 「CGOI-1」大师选徒

「CGOI-1」大师选徒

题目背景

最近有好多人来丑国学习 bc。bc 大师 ac 和 mc 要从所有学生选出一些来传授 bc 技艺。

2021.8.29:添加了一组 hack

题目描述

nn 个学生站成一排,每个学生有一个丑值 aia_i。现在 ac 和 mc 要各自从学生中选取连续的一段传授 bc。

由于 ac 和 mc 关系很♂好,所以两人选出的学生必须人数相同,并且对应位置上的学生丑值之和均为 ss

(比方说,如果 ac 选第 112233 号学生,mc 选 334455 号学生,必须满足 a1+a3=a2+a4=a3+a5=sa_1+a_3=a_2+a_4=a_3+a_5=s

但 ac 并不知道 mc 所选的学生以及 ss 是多少,所以他会给出若干个询问。对于每个询问,你需要回答对于特定的 ss 以及 mc 选出的一段学生,ac 是否可以选出另一段学生满足上述要求。

简化版题意:

给出 nnnn 个整数 a1,a2,,ana_1,\,a_2,\,\dots,\,a_n

qq 次询问,每次给出 s,l,rs,l,r,问是否存在 bb,满足 k[0,rl]\forall k \in [0, r-l]al+k+ab+k=sa_{l+k}+a_{b+k}=s

输入格式

第一行输入两个整数 n,qn,\,q,分别表示学生的人数与询问的个数。

第二行输入 nn 个整数,第 ii 个数 aia_i 表示第 ii 个学生的丑值。

接下来 qq 行,每行输入三个整数 s,l,rs,\,l,\,r,分别表示丑值之和,mc 所选的第一个学生的下标和最后一个学生的下标。

输出格式

对于每一个询问,如果可以选出符合条件的学生,输出 Yes,否则输出 No。每个输出占一行。

6 4
1 1 3 4 2 1
4 3 3
1 2 2
5 4 6
2 1 2
Yes
No
Yes
Yes
6 4
4 2 2 2 2 1
6 1 1
5 5 6
4 3 5
5 2 2
Yes
No
Yes
No

提示

样例说明:

对于样例 1:

第一个询问,mc 选择的是第三个学生,ac 可以选择第一个学生。

第二个询问,mc 选择的第二个学生丑值为 11,而总和也为 11,但不存在丑值为 00 的学生,故不能满足条件。

第三个询问,mc 选择的是第四个到第六个,那么 ac 选择第二个到第四个,对应位置的学生丑值之和 a2+a4=a3+a5=a4+a6=5a_2+a_4=a_3+a_5=a_4+a_6=5,满足条件。

第四个询问,mc 选择第一个和第二个,那么 ac 也选择第一个和第二个,满足条件。


数据范围:

本题采用捆绑测试。

对于全部数据,有 1n,q4×1051\le n,\,q\le 4\times10^51ain1\le a_i \le n1s2n1\le s\le 2n1lrn1\le l\le r\le n

  • Subtask 0(10 points):n,q500n,\,q\le 500
  • Subtask 1(20 points):n,q8×103n,\,q\le 8\times10^3
  • Subtask 2(20 points):保证所有 ss 相同。
  • Subtask 3(50 points):无特殊限制。