Problem Description GTY has
n
gay friends. To manage them conveniently, every morning he ordered all his gay friends to stand in a line. Every gay friend has a characteristic value
ai
, to express how manly or how girlish he is. You, as GTY's assistant, have to answer GTY's queries. In each of GTY's queries, GTY will give you a range
[l,r]
. Because of GTY's strange hobbies, he wants there is a permutation
[1..r?l+1]
in
[l,r]
. You need to let him know if there is such a permutation or not.
Input Multi test cases (about 3) . The first line contains two integers n and m (
1≤n,m≤1000000
), indicating the number of GTY's gay friends and the number of GTY's queries. the second line contains n numbers seperated by spaces. The
ith
number
ai
(
1≤ai≤n
) indicates GTY's
ith
gay friend's characteristic value. The next m lines describe GTY's queries. In each line there are two numbers l and r seperated by spaces (
1≤l≤r≤n
), indicating the query range.
Output For each query, if there is a permutation
[1..r?l+1]
in
[l,r]
, print 'YES', else print 'NO'.
Sample Input
8 5
2 1 3 4 5 2 3 1
1 3
1 1
2 2
4 8
1 5
3 2
1 1 1
1 1
1 2
Sample Output
YES
NO
YES
YES
YES
YES
NO
题意：给出n个数，m个询问，问你[l,r]区间内是否为1到r-l+1的全排列。 大小很容易我们通过记录前缀和很容易求出来，但是关键是去重。 考虑线段树做法，我们记录每个点的靠左最近的相同元素的位置，然后求 整个区间的最大值（即最大的前驱）如果小于l,即满足条件，输出YES。
#include
#include
#include
#include
#include
#include
#include
#include
#include