Problem Description
GTY hasgay 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, 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. Because of GTY’s strange hobbies, he wants there is a permutation. 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 (), 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) indicates GTY’sgay 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 (), indicating the query range.
Output
For each query, if there is a permutation, print ‘YES’, else print ‘NO’.
Sample Input
8 52 1 3 4 5 2 3 11 31 12 24 81 53 21 1 11 11 2
Sample Output
YESNOYESYESYESYESNO
题意：给出n个数，，m个询问，问你[l,r]区间内是否为1到r-l+1的全排列。
大小很容易我们通过记录前缀和很容易求出来，但是关键是去重。
考虑线段树做法，我们记录每个点的靠左最近的相同元素的位置，然后求
整个区间的最大值（即最大的前驱）如果小于l,即满足条件，输出YES。
#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#include<string>#include<iostream>#include<queue>#include<cmath>#include<map>#include<stack>#include<bitset>using namespace std;#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )#define CLEAR( a , x ) memset ( a , x , sizeof a )typedef long long LL;typedef pair<int,int>pil;const int MOD = 10000007;const int INF=0x3f3f3f3f;const int maxn=1000000+10;int mp[maxn];int ans[maxn],pre[maxn];LL s[maxn];int num[maxn],sum[maxn<<2];int n,m;void pushup(int rs){sum[rs]=max(sum[rs<<1],sum[rs<<1|1]);}void build(int rs,int l,int r){sum[rs]=0;if(l==r) return ;int mid=(l+r)>>1;build(rs<<1,l,mid);build(rs<<1|1,mid+1,r);}void update(int x,int c,int l,int r,int rs){if(l==r){sum[rs]=c;return ;}int mid=(l+r)>>1;if(x<=mid) update(x,c,l,mid,rs<<1);else update(x,c,mid+1,r,rs<<1|1);pushup(rs);}int query(int x,int y,int l,int r,int rs){if(l>=x&&r<=y)return sum[rs];int mid=(l+r)>>1;int res=0;if(x<=mid) res=max(res,query(x,y,l,mid,rs<<1));if(y>mid) res=max(res,query(x,y,mid+1,r,rs<<1|1));pushup(rs);return res;}int main(){int x,y;while(~scanf("%d%d",&n,&m)){s[0]=0;CLEAR(mp,0);CLEAR(ans,0);REPF(i,1,n){scanf("%d",&num[i]);s[i]=s[i-1]+num[i];if(!mp[num[i]]){pre[i]=0;mp[num[i]]=i;}else{pre[i]=mp[num[i]];mp[num[i]]=i;}update(i,pre[i],1,n,1);}while(m–)//离线做法超时了{scanf("%d%d",&x,&y);LL temp=(1+y-x+1)*(y-x+1)/2;if(s[y]-s[x-1]==temp&&query(x,y,1,n,1)<x) puts("YES");else puts("NO");}}return 0;}
但一定要背上几本书，在花海里，草丛旁悠然品味，
