[COCI2017-2018#3] Programiranje
题意翻译
Little Leticija 正在准备编程考试。虽然她已经解决了很多任务,但还有一个任务尚未解决,于是她向你寻求帮助。
有一个单词 $S$ 和 $Q$ 次询问。在每次询问中,给出正整数 $A$、$B$、$C$ 和 $D$。假设单词 $X$ 由单词 $S$ 中位置 $A$ 和 $B$ 及其之间的字母组成,而单词 $Y$ 由位置 $C$ 和 $D$ 及其之间的字母组成。您需要回答是否能以某种方式**重新排列单词 $Y$ 中的字母得到单词 $X$**。
**【输入格式】**
第一行输入包含单词 $S$($1\le\lvert S\rvert\le50000$)。$\lvert S\rvert$ 表示单词 $S$ 中的字符数。$S$ 完全由英文小写字母组成。
第二行输入包含正整数 $Q$($1\le Q\le50000$)。
以下 $Q$ 行中的每一行包含四个整数 $A$、$B$、$C$ 和 $D$($1\le A\le B\le\lvert S\rvert$ 且 $1\le C\le D\le\lvert S\rvert$)。
**【输出格式】**
对于每次询问,如果可能,输出`DA`(即克罗地亚语的“是”),如果不可能,则输出`NE`(克语的“否”)。
**【说明/提示】**
对于 $50\%$ 的测试点,有 $1\le\lvert S\rvert\le1000$ 且 $1\le Q\le1000$。
对于 $100\%$ 的测试点,有 $1\le\lvert S\rvert\le50000$,$1\le Q\le50000$,$1\le A\le B\le\lvert S\rvert$ 且 $1\le C\le D\le\lvert S\rvert$。
样例 #3 的解释:在第一次询问中,$X=\tt vovo$,$Y=\tt devo$。在第二次询问中,$X=\tt odev$,$Y=\tt devo$。
题目描述
Little Leticija is preparing for a programming exam. Even though she has solved a lot of tasks, there’s one still left unsolved, so she is asking you for help. You are given the word S and Q queries. In each query, you are given positive integers A, B, C and D. Let’s say that word X consists of letters between positions A and B in word S, and word Y from letters between positions C and D in word S. For each query, you must answer if it is possible to somehow rearrange the letters in word Y and obtain word X.
输入输出格式
输入格式
The first line of input contains the word S (1 ≤ |S| ≤ 50 000). |S| denotes the number of characters in word S, which consists of lowercase letters of the English alphabet. The second line of input contains the positive integer Q (1 ≤ Q ≤ 50 000).
Each of the following Q lines contains four integers A, B, C i D (1 ≤ A ≤ B ≤ |S| and 1 ≤ C ≤ D ≤ |S| ) from the task.
输出格式
For each query, output “DA” (Croatian for yes) if it is possible, and “NE” (Croatian for no) if it is not.
输入输出样例
输入样例 #1
kileanimal
2
2 2 7 7
1 4 6 7
输出样例 #1
DA
NE
输入样例 #2
abababba
2
3 5 1 3
1 2 7 8
输出样例 #2
DA
DA
输入样例 #3
vodevovode
2
5 8 3 6
2 5 3 6
输出样例 #3
NE
DA
说明
In test cases worth 50% of total points, it will hold: 1 ≤ |S| ≤ 1000 and 1 ≤ Q ≤ 1000.
**Clarification of the third test case:**
In the first query, X=”vovo”, and Y=”devo”. In the second query, X=”odev”, and Y=”devo”.