GTY has nn 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 aiai , 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][l,r] . Because of GTY's strange hobbies, he wants there is a permutation [1..r−l+1][1..r−l+1] in [l,r][l,r]. You need to let him know if there is such a permutation or not.
InputMulti test cases (about 3) . The first line contains two integers n and m ( 1≤n,m≤10000001≤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 ithith number aiai ( 1≤ai≤n1≤ai≤n ) indicates GTY's ithith 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≤n1≤l≤r≤n ), indicating the query range.OutputFor each query, if there is a permutation [1..r−l+1][1..r−l+1] in [l,r][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 题意 给出一个数列，询问连续的从l开始到r为止的数是否刚好能够组成从1开始到r-l+1的数列 第一个判断用前缀和求和，然后就是查重
用线段树维护每一个数它上一次出现的地方，
如果这个区间里面所有的数上一次出现的最大值小于了a 那就是符合条件的了
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <algorithm>
#include <set>
#include <iostream>
#include <map>
#include <stack>
#include <string>
#include <vector>
#define pi acos(-1.0)
#define eps 1e-6
#define fi first
#define se second
#define rtl rt<<1
#define rtr rt<<1|1
#define bug printf("******\n")
#define mem(a,b) memset(a,b,sizeof(a))
#define name2str(x) #x
#define fuck(x) cout<<#x" = "<<x<<endl
#define f(a) a*a
#define sf(n) scanf("%d", &n)
#define sff(a,b) scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define sffff(a,b,c,d) scanf("%d %d %d %d", &a, &b, &c, &d)
#define pf printf
#define FRE(i,a,b) for(i = a; i <= b; i++)
#define FREE(i,a,b) for(i = a; i >= b; i--)
#define FRL(i,a,b) for(i = a; i < b; i++)+
#define FRLL(i,a,b) for(i = a; i > b; i--)
#define FIN freopen("in.txt","r",stdin)
#define gcd(a,b) __gcd(a,b)
#define lowbit(x) x&-x
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int mod = 1e9 + ;
const int maxn = 1e6 + ;
const int INF = 0x3f3f3f3f;
const LL INFLL = 0x3f3f3f3f3f3f3f3fLL;
int n, m, x, vis[maxn];
LL sum[maxn];
struct node {
int l, r, num;
int mid() {
return ( l + r ) >> ;
}
} tree[maxn << ];
void pushup ( int rt ) {
tree[rt].num = max ( tree[rtl].num, tree[rtr].num );
}
void build ( int l, int r, int rt ) {
tree[rt].l = l, tree[rt].r = r;
if ( l == r ) {
tree[rt].num = ;
return ;
}
int m = ( l + r ) >> ;
build ( l, m, rtl );
build ( m + , r, rtr );
}
void update ( int pos, int key, int rt ) {
if ( tree[rt].l == tree[rt].r ) {
tree[rt].num += key;
return ;
}
int m = tree[rt].mid();
if ( pos <= m ) update ( pos, key, rtl );
else update ( pos, key, rtr );
pushup ( rt );
}
int query ( int L, int R, int rt ) {
if ( L <= tree[rt].l && tree[rt].r <= R ) return tree[rt].num;
int m = tree[rt].mid();
if ( L > m ) return query ( L, R, rtr );
else if ( R <= m ) return query ( L, R, rtl );
else return max ( query ( L, m, rtl ), query ( m + , R, rtr ) );
}
int main() {
while ( ~sff ( n, m ) ) {
mem ( vis, );
build ( , n, );
for ( int i = ; i <= n ; i++ ) {
sf ( x );
sum[i] = sum[i - ] + x;
if ( vis[x] ) update ( i, vis[x], );
vis[x] = i;
}
while ( m-- ) {
int a, b;
sff ( a, b );
// fuck(sum[b] - sum[a - 1]),fuck(( b - a + 1 ) * ( b - a + 2 ) / 2)
if ( sum[b] - sum[a - ] == ( b - a + ) * ( b - a + ) / && query ( a, b, ) < a ) printf ( "YES\n" );
else printf ( "NO\n" );
}
}
return ;
}