2020 우 객 여름 다 교 훈련소 (6 차 전) K - Bag [슬라이딩 창]

제목 링크:https://ac.nowcoder.com/acm/contest/5671/K
제목
k - bag 를 1 ~ k 로 정의 하 는 여러 개의 전체 배열 로 구 성 된 서열, part - k - bag 는 k - bag 의 연속 서브 서열 입 니 다.지금 은 길이 가 n 인 서열 을 드 리 고 파 트 - k - bag 인지 아 닌 지 를 판단 합 니 다.
사고의 방향
part - k - bag 의 특징 은 중간 에 몇 개의 완전한 1 ~ k 전체 배열 이 고 왼쪽 과 오른쪽 에 k 보다 작은 전체 배열 이 존재 할 수 있 습 니 다.
우선, 렌 [i] 을 구하 면 i 를 종점 으로 하고 i 이전 (i 포함) 에는 최대 몇 개의 다른 숫자 가 있 었 는 지 나타 낸다.미끄럼 창 을 구 하 는 것 과 유사 한 방법 으로 len [i] 을 구 합 니 다.
그리고 마지막 전체 k - bag 의 종점 을 매 거 합 니 다. j = i 부터 len [j] 길 이 를 앞으로 이동 할 때마다 j > = k 시 len [j]! =k, 혹은 j
AC 코드

#include 
using namespace std;
const int N=5e5+10;
deque<int>q;
int T,n,k,a[N];
unordered_map<int,int>vis;
int len[N];
bool solve()
{
    vis.clear();
    while(!q.empty())q.pop_back();
    for(int i=1;i<=n;i++)
    {
        if(a[i]>k)return 0; //   
        q.push_back(a[i]);
        if(!vis[a[i]])
        {
            vis[a[i]]=1;
            len[i]=q.size();
        }
        else
        {
            while(!q.empty()&&vis[a[i]])
            {
                vis[q.front()]=0;
                q.pop_front();
            }
            vis[a[i]]=1;
            len[i]=q.size();
        }
    } // get every len[i]
    int ex=max(n-k+1,n-len[n]); 
    for(int i=n;i>=ex;i--) //         k-bag   
    {
        bool flag=1;
        for(int j=i;j>0;j-=len[j])
            if(len[j]!=k&&j>=k||len[j]!=j&&j<k){flag=0;break;}
        if(flag)return 1; //            
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>T;
    while(T--)
    {
        cin>>n>>k;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        int ans=solve();
        if(ans)printf("YES
");
        else printf("NO
");
    }
    return 0;
}
/*
100

6 5
1 2 1 2 1 2
NO

5 100
1 2 3 1 2
YES
len:1 2 3 3 3

5 100
2 2 2 2 2
NO
len:1 1 1 1 1

5 2
1 2 3 1 2
NO

4 2
1 1 2 2
YES

5 3
1 2 3 1 2
YES

5 3
1 2 2 2 1
NO

3 3
1 2 3
YES

4 3
1 2 2 1
YES

3 3
2 1 2
YES

9 3
3 2 1 3 3 1 2 2 1
YES

6 3
3 2 1 1 2 3
YES

5 3
1 3 2 2 1
YES

5 3
1 3 2 3 1
YES

13 4
3 1 2 4 1 2 3 4 2 1 3 2 3
YES

7 3
1 2 1 2 3 3 2
YES

2 3
1 2
YES
*/