P11262 [COTS 2018] 题日 Zapatak

译自 [Izborne Pripreme 2018 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2018/) D1T2。$\texttt{1s,1G}$。 关于题目名：原文如此（「题目」的克罗地亚语是「zadatak」）。

定义长度均为 $k$ 的数列 $[a_1,a_2,\ldots,a_k]$ 和 $[b_1,b_2,\ldots,b_k]$ **几乎相等**，当且仅当存在**恰好一个** $1\le p\le k$，使得 $a_p\neq b_p$。 定义长度均为 $k$ 的数列 $[a_1,a_2,\ldots,a_k]$ 和 $[b_1,b_2,\ldots,b_k]$ **相似**，当且仅当可以通过重排使得 $a,b$ **几乎相等**。 给定长度为 $n$ 的数列 $[a_1,a_2,\ldots,a_n]$。$m$ 次询问，每次询问给定 $l_1,r_1,l_2,r_2$，问 $[a_{l_1},a_{{l_1}+1},\ldots,a_{r_1}]$ 与 $[a_{l_2},a_{{l_2}+1},\ldots,a_{r_2}]$ 是否相似。

第一行，两个正整数 $n,m$。 第二行，$n$ 个非负整数 $a_1,a_2,\ldots,a_n$。 接下来 $m$ 行，每行四个正整数 $l_1,r_1,l_2,r_2$，描述一次询问。保证 $r_1-l_1=r_2-l_2$。

对于每个询问，输出一行： 如果答案为是的话，输出 $\texttt{DA}$（克罗地亚语「是」）； 否则输出 $\texttt{NE}$（克罗地亚语「否」）。

对于 $100\%$ 的数据，保证： - $1\le n,m\le 10^5$； - $0\le a_i\le 10^9$； - $1\le l_1\le r_1\le n$，$1\le l_2\le r_2\le n$； - $r_1-l_1=r_2-l_2$。 | 子任务编号 | $n\le $ | $m\le $ | $a_i\le$ | 得分 | | :--: | :--: | :--: | :--: | :--: | | $ 1 $ | $ 1\, 000 $ | $1\, 000$ | $ 10^9$ | $ 10 $ | | $ 2 $ | $ 5\times 10^4 $ | $5\times 10^4$ | $30$ | $ 15 $ | | $ 3 $ | $ 10^5$ | $10^4$ | $10^9$ | $ 30 $ | | $ 4 $ | $ 10^5$ | $10^5$ | $10^9$ | $ 45 $ |