#P11279. [COTS 2018] 题日 Zapatak

[COTS 2018] 题日 Zapatak

题目描述

定义长度均为 kk 的数列 [a1,a2,…,ak][a_1,a_2,\ldots,a_k] 和 [b1,b2,…,bk][b_1,b_2,\ldots,b_k] 几乎相等,当且仅当存在恰好一个 1≤p≤k1\le p\le k,使得 ap≠bpa_p\neq b_p。

定义长度均为 kk 的数列 [a1,a2,…,ak][a_1,a_2,\ldots,a_k] 和 [b1,b2,…,bk][b_1,b_2,\ldots,b_k] 相似,当且仅当可以通过重排使得 a,ba,b 几乎相等。

给定长度为 nn 的数列 [a1,a2,…,an][a_1,a_2,\ldots,a_n]。mm 次询问,每次询问给定 l1,r1,l2,r2l_1,r_1,l_2,r_2,问 [al1,al1+1,…,ar1][a_{l_1},a_{{l_1}+1},\ldots,a_{r_1}] 与 [al2,al2+1,…,ar2][a_{l_2},a_{{l_2}+1},\ldots,a_{r_2}] 是否相似。

输入格式

第一行,两个正整数 n,mn,m。

第二行,nn 个非负整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

接下来 mm 行,每行四个正整数 l1,r1,l2,r2l_1,r_1,l_2,r_2,描述一次询问。保证 r1−l1=r2−l2r_1-l_1=r_2-l_2。

输出格式

对于每个询问,输出一行:

如果答案为是的话,输出 DA\texttt{DA}(克罗地亚语「是」);

否则输出 NE\texttt{NE}(克罗地亚语「否」)。

输入输出样例 #1

输入 #1

6 4
1 3 2 3 1 2
1 1 2 2
2 3 3 4
2 3 4 5
1 3 2 4

输出 #1

DA
NE
DA
DA

输入输出样例 #2

输入 #2

10 5
3 3 3 1 2 2 1 2 2 1
2 3 5 6
9 10 5 6
5 6 4 5
5 8 3 6
3 7 5 9

输出 #2

NE
DA
DA
DA
NE

说明/提示

对于 100%100\% 的数据,保证:

  • 1≤n,m≤1051\le n,m\le 10^5;
  • 0≤ai≤1090\le a_i\le 10^9;
  • 1≤l1≤r1≤n1\le l_1\le r_1\le n,1≤l2≤r2≤n1\le l_2\le r_2\le n;
  • r1−l1=r2−l2r_1-l_1=r_2-l_2。
子任务编号 n≤n\le m≤m\le ai≤a_i\le 得分
1 1 1 000 1\, 000 1 0001\, 000 109 10^9 10 10
2 2 5×104 5\times 10^4 5×1045\times 10^4 3030 15 15
3 3 105 10^5 10410^4 10910^9 30 30
4 4 10510^5 45 45