K K-Bag

题目链接：https://ac.nowcoder.com/acm/contest/5671/K
题目大意：
一个由一些1-n的排列组成的数列称为k-bag。比如1，2，3，2，1，3，3，2，1就是一个k-bag。部分k-bag是k-bag的一个子串，现在给一个长度为n的数列，判断是否是一个部分k-bag。
解题思路：
参考sunsetcolors的解法：https://blog.nowcoder.net/n/1cf39334dfea43339767441bc1e836b6
跟据题意能想到，满足条件的序列，我们不管头和尾，中间一定要是几个k排列摆放的过程。
但是我们并不清楚，头和尾在什么位置结束。
因此我们考虑一种尺取+dp的策略，首先在序列开头只要不出现重复的元素，那么很明显这些位置都可以作为头部结束的位置，我们将这些位置的dp[i]都设为true，然后我们通过尺取法，快速找到序列里所有满足k排列的哪些区间的结束位置，因为如果我们头部从一个位置pos结束，要是序列符合条件的话必须满足pos+k+k+k...这样的形式，这里面的每个k都是满足条件的k排列区间，假设r是现在一个排列区间的结尾，存在这样的一个转移dp[r]=dp[r-k].
这样实际上我们就是处理出了从头部起，所有符合条件的区间能到达的位置，然后我们再从尾部出发，如果能找到一个尾部开始的位置，和这些从头部起满足条件的位置连接起来，则说明这个数列是一个k-bag的子串。
代码：

#include<bits/stdc++.h>
#pragma GCC optimize(3)

using namespace std;
#define IO std::ios::sync_with_stdio(false); cin.tie(0)

const int maxn = 5e5+7;
int a[maxn];
bool dp[maxn];
unordered_map<int,int> memo;
unordered_set<int> st;
int n, k;

signed main()
{
    IO;
    int T; cin >> T;
    while(T--)
    {
        cin >> n >> k;
        memo.clear(); st.clear();
        for(int i = 1; i <= n; i++) cin >> a[i], dp[i] = 0;
        int pos;
        for(pos = 1; pos <= n; pos++){
            if(memo[a[pos]]) break;
            memo[a[pos]] = 1; st.insert(a[pos]);
        }
        for(int i = 1; i < pos; i++) dp[i] = true;
        for(int i = pos; i <= min(n,k); i++) {
            memo[a[i]]++; st.insert(a[i]);
        }
        for(int r = k + 1; r <= n; r++) {
            int l = r - k;            //在[l,r]这段区间尺取 
            memo[a[l]]--;
            if(!memo[a[l]]) st.erase(a[l]);
            memo[a[r]]++;
            st.insert(a[r]);
            if(st.size() == k) dp[r] |= dp[l];
        }
        memo.clear();
        bool v = true;
        for(pos = n; pos >= 1; pos--) {
            if(dp[pos]) break;        //相接了，说明 
            if(memo[a[pos]]) {
                v = false; break;
            }
            memo[a[pos]] = 1;
        }
        if(v) cout << "YES" <<endl;
        else cout << "NO" << endl;
    }
    return 0;
}