本文主要是介绍hdu5172 GTY's gay friends，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：一个数列，有m组询问l,r，需回答l-r是否为一个1-r-l+1的排列。
分析：n个数为1-n的一个排列需满足两个条件，1.和为(n+1)*n/2，2.所有数不相同。1预处理前缀和即可，2先需处理每个数左边与其最近的相同数的位置pre[i]，用线段树维护区间l-r各个数pre[i]的最大值mx，若mx<l则满足条件。
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<map>
#include<algorithm>
#include<queue>
#include<set>
#define inf 10000000
#define pi acos(-1.0)
#define eps 1e-8
#define seed 131
using namespace std;
typedef pair<int,int> pii;
typedef unsigned long long ULL;
typedef long long LL;
const int maxn=1000005;
int d[maxn];
int n,m;
LL tot[maxn];
int pre[maxn];
int pos[maxn];
int tr[maxn<<2];
void pushup(int l,int r,int rt)
{tr[rt]=max(tr[rt<<1],tr[rt<<1|1]);return;
}
void build(int l,int r,int rt)
{if(l==r){tr[rt]=pre[l];return;}int m=(l+r)>>1;build(l,m,rt<<1);build(m+1,r,rt<<1|1);pushup(l,r,rt);
}
int query(int L,int R,int l,int r,int rt)
{int ans=0;if(L<=l&&R>=r){ans=max(ans,tr[rt]);return ans;}int m=(l+r)>>1;if(L<=m){ans=max(ans,query(L,R,l,m,rt<<1));}if(R>m){ans=max(ans,query(L,R,m+1,r,rt<<1|1));}return ans;
}
int main()
{while(~scanf("%d%d",&n,&m)){for(int i=1;i<=n;i++)scanf("%d",&d[i]);tot[0]=0;for(int i=1;i<=n;i++){tot[i]=tot[i-1];tot[i]+=d[i];}memset(pos,0,sizeof(pos));for(int i=1;i<=n;i++){pre[i]=pos[d[i]];pos[d[i]]=i;}build(1,n,1);int a,b;for(int i=0;i<m;i++){scanf("%d%d",&a,&b);LL u=tot[b]-tot[a-1];LL c=(LL)((b-a+2))*(b-a+1)/2;if(u==c){int k=query(a,b,1,n,1);if(k<a)printf("YES\n");elseprintf("NO\n");}elseprintf("NO\n");}}return 0;
}这篇关于hdu5172 GTY's gay friends的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
