【题意转化+线段树】L - GTY‘s gay friends
程序员文章站
2022-03-22 16:25:28
题面http://acm.hdu.edu.cn/showproblem.php?pid=5172题意给你n个数,m次查询,每次询问一个区间【l,r】,问这个区间【l,r】是否满足【l,r】之间的数是【1,r-l+1】的一个排列思路1:题意转化+线段树对于一个区间,我们可以把它【1,r-l+1】的排列转化成满足以下两个条件:【l,r】的区间和为len*(len+1)/2,其中len=r-l+1对于【l,r】中的每个数,他的前一次出现必须在l这个位置之前对于第一个问题来说,我们可以直接用前缀和...
题面
http://acm.hdu.edu.cn/showproblem.php?pid=5172
题意
给你n个数,m次查询,每次询问一个区间【l,r】,问这个区间【l,r】是否满足【l,r】之间的数是【1,r-l+1】的一个排列
思路1:题意转化+线段树
对于一个区间,我们可以把它【1,r-l+1】的排列转化成满足以下两个条件:
-
【l,r】的区间和为len*(len+1)/2,其中len=r-l+1
-
对于【l,r】中的每个数,他的前一次出现必须在l这个位置之前
-
对于第一个问题来说,我们可以直接用前缀和o(1)来实现
-
而第二个问题我们可以处理一个pre数组出来,表示上一个出现相同数的位置,我们只要保证所有【l,r】位置上的数的pre都在l这个位置之前,这个的实现思想上有一点像序列自动机的处理,然后我们只需要查询【l,r】最大的那个pre,判断其是否小于l,就知道是否满足条件了,这个操作可以用线段树来实现
(理论上主席树和st表都能做,但是空间开不下)
代码
#include <bits/stdc++.h>
#define ls k<<1
#define rs k<<1|1
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
typedef unsigned long long ull;
const int maxn=1e6+100;
int node[maxn<<2],pre[maxn],pla[maxn];
ull sum[maxn];
int n,m;
void build(int k,int l,int r)
{
if(l==r)
{
node[k]=pre[l];
return ;
}
int mid=l+r>>1;
build(ls,l,mid);
build(rs,mid+1,r);
node[k]=max(node[ls],node[rs]);
}
int query(int k,int ql,int qr,int l,int r)
{
if(ql<=l&&r<=qr)
return node[k];
int mid=l+r>>1;
int ans=0;
if(ql<=mid)
ans=max(ans,query(ls,ql,qr,l,mid));
if(qr>mid)
ans=max(ans,query(rs,ql,qr,mid+1,r));
return ans;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(pla,0,sizeof(pla));
memset(sum,0,sizeof(sum));
for(int i=1,x;i<=n;i++)
{
scanf("%d",&x);
sum[i]=sum[i-1]+x;
pre[i]=pla[x];
pla[x]=i;
}
build(1,1,n);
while(m--)
{
int l,r;
scanf("%d%d",&l,&r);
int len=r-l+1;
if(sum[r]-sum[l-1]==1ll*len*(len+1)/2&&query(1,l,r,1,n)<l)
printf("YES\n");
else
printf("NO\n");
}
}
return 0;
}
本文地址:https://blog.csdn.net/qq_46129590/article/details/111014144