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
Source
BestCoder Round #29
Recommend
hujie | We have carefully selected several similar problems for you: 5173 5169 5168 5165 5164
如果一个区间里是一个[1, … , r – l + 1]的排列，那么首先，区间和是
x * (x + 1) / 2， –>前缀和处理
其次每一个数都不同，预处理每一个数上一次出现的位置pre，然后求出区间里pre的最大值，如果最大的pre小于左端点且区间和是 x * (x + 1) / 2，那么输出YES，否则NO，这里可以用线段树解决
注意判断时，最好先判断区间和，如果这