2020牛客多校 6K.K

题意:

一个序列被称为k-bag,当且仅当序列由多个1到k的排列顺序连接
例如1,2,3, 2,1,3 ,3,2,1 是一个3-bag序列,因为可以拆分为{1,2,3}{2,1,3}{3,2,1}

给定长度为n的序列a,和一个整数k。
判断该序列是否可能是k-bag序列的某个子区间

数据范围:n=5e5,k=1e9,1=a(i)=1e9

解法:

设ma为序列的最大值,当mak的时候显然不是。

如果满足条件,那么这个序列一定是x p p p x的形式,其中p表示1到k的排列,x表示前后两端长度k的一段,
且前后两端的x一定没有重复数字

因为x的长度k,那么在[1,min(n,k)]范围内枚举左端x的长度,然后判断后面每一段长度为k的区间是否是排列,
以及末尾一段x是否所有数只出现一次,如果全都满足,则说明这个序列是k-bag。

那么问题就变为判断长度为k的区间是否是排列,和不满长度k的区间是否所有数只出现一次。

这个问题是经典题了,可以用last(i)表示a(i)上一次出现的位置,
对last建线段树,如果[l,r]中的最大值l,说明每种数都只出现一次。

当k=n的时,只需要查询[1,n]是否所有数只出现一次即可,只有一次查询,复杂度为log(n)
当kn的时,xpppx 一共k/n段,枚举左端x的长度次数为O(k),总查询次数为n/k*k=n,加上线段树复杂度为nlog(n)

code:
#includebits/stdc++.h
using namespace std;
const int maxm=5e5+5;
int last[maxm];
int a[maxm];
int n,k;
struct ST{
    int a[maxm2];
    void pushup(int node){
        a[node]=max(a[node*2],a[node*2+1]);
    }
    void build(int l,int r,int node){
        if(l==r){
            a[node]=last[l];
            return ;
        }
        int mid=(l+r)/2;
        build(l,mid,node*2);
        build(mid+1,r,node*2+1);
        pushup(node);
    }
    int ask(int st,int ed,int l,int r,int node){
        if(st=led=r)return a[node];
        int mid=(l+r)/2;
        int ans=0;
        if(st=mid)ans=max(ans,ask(st,ed,l,mid,node*2));
        if(edmid)ans=max(ans,ask(st,ed,mid+1,r,node*2+1));
        return ans;
    }
}t;
signed main(){
    int T;scanf("%d",T);
    while(T--){
        scanf("%d%d",n,k);
        int ma=0;
        for(int i=1;i=n;i++){
            scanf("%d",a[i]);
            ma=max(ma,a[i]);
        }
        if(mak){
            puts("NO");continue;
        }
        unordered_mapint,intpre;
        for(int i=1;i=n;i++){
            last[i]=pre[a[i]];
            pre[a[i]]=i;
        }
        t.build(1,n,1);
        int ok=0;
        for(int i=1;i=ki=n;i++){
            if(t.ask(1,i,1,n,1)=1)break;
            int okk=1;
            for(int l=i+1;l=n;l+=k){
                int r=min(l+k-1,n);
                if(t.ask(l,r,1,n,1)=l){
                    okk=0;break;
                }
            }
            if(okk){
                ok=1;break;
            }
        }
        if(ok)puts("YES");
        else puts("NO");
    }
    return 0;
}

最新回复(0)
/jishuMFiijnJ22JARYfP7sBw3gWgA_2FFk4rfBn82HtZw_3D_3D4794914
8 简首页