牛客6—— K-Bag （奇妙哈希或滑动窗口）

牛客6—— K-Bag （奇妙哈希或滑动窗口）

原题链接

题意：

定义一个特殊序列为多个1~k的排列顺序连接起来的序列，问给出的序列是不是特殊序列的连续子串。

思路：

思路一来源于铭宇巨巨，思路二来源于博客

首先可以知道，如果一个序列是特殊序列的连续子串，要么是序列是特殊序列的一部分，要么是一个特殊序列的前缀+一个特殊序列的后缀，要么就是在情况二里插入若干非零个完整的特殊序列。

那么对于一段序列我们如何判断这段序列属于特殊序列的一部分呢？比较容易想到的一种方法就是判断该序列不同数字的个数等于该序列的长度，因为特殊序列可以是1~k的任意全排列，所以这种情况一定说明该序列属于特殊序列的一部分。这种方法的缺点就在于判断完整的特殊序列时，可能要用到主席树维护，这样就显得过于复杂。博客给出了一种根据sum和xor确定某一区间的哈希方法，大体意思就是维护出序列某一区间的sum和xor值后，该区间就唯一确定了。另一种方法就是判断该序列重复数字的个数tot，如果个数为0，则说明该序列属于特殊序列的一部分。这种思路写起来比较简单！只需要先从前到后处理出能够被当做断点的点（当i<=k时，如果在[1,i]区间里的tot==0，就说明该点可以当做断点；当i>k时，如果[k,i]区间的tot==0并且i-k是断点，说明该点可以当做断点）；然后再从后向前枚举，如果说该点i的tot==0，说明[i,n]这段区间是属于特殊序列的，这时候如果i-1是断点，就符合题意了。

还有个小优化就是判断a[i]和k的大小，如果出现a[i]>k的情况，直接输出NO即可。

代码：
思路二的代码去原博客看叭

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define I_int ll
typedef pair<int,int> PII;
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
char F[200];
inline void out(I_int x) {
    if (x == 0) return (void) (putchar('0'));
    I_int tmp = x > 0 ? x : -x;
    if (x < 0) putchar('-');
    int cnt = 0;
    while (tmp > 0) {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0) putchar(F[--cnt]);
    //cout<<" ";
}
const int maxn=1e6+7;
int a[maxn],b[maxn];
int n,k,tot;
bool vis[maxn];///是否为断点
int c[maxn];///记录每个数出现的次数

void add(int x){
    if(c[x]==1) tot++;
    c[x]++;
}

void del(int x){
    if(c[x]==2) tot--;
    c[x]--;
}

int main(){
    int T=read();
    ///枚举断点 如果i是断点的话 i-k也是
    while(T--){
        n=read(),k=read();
        bool flag=1;
        for(int i=1;i<=n;i++){
            a[i]=read();
            b[i]=a[i];
            if(a[i]>k||a[i]<1) flag=0;///一定不符合题意
        }
        if(!flag){
            puts("NO");continue;
        }
        sort(b+1,b+1+n);
        int cnt=unique(b+1,b+1+n)-(b+1);///去重
        for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+cnt,a[i])-b-1;
        tot=0;///维护某段的重复的数 如果维护当前区间有多少个不同的数还要考虑区间长度
        memset(c,0,sizeof c);
        memset(vis,0,sizeof vis);
        for(int i=1;i<=n;i++){
            add(a[i]);
            if(i<=k){
                if(tot==0) vis[i]=1;
            }
            else{
                del(a[i-k]);
                if(!tot&&vis[i-k]) vis[i]=1;
            }
        }
        flag=0;tot=0;
        memset(c,0,sizeof c);
        for(int i=n;i>=1;i--){
            add(a[i]);
            if(!tot&&vis[i-1]){
                flag=1;break;
            }
        }
        if(flag) puts("YES");
        else puts("NO");
    }
    return 0;
}