K-Bag

题目大题：K—Bag：数组是由若干个长度为k的全排列组成的，然后在开头和结尾都可以删去位置连续的若干个元素。
最后要你判断是否是K-Bag

我们定义一种边（u, v)；
若u=1 或v=n+1，则要求a[u],a[u+1],..,a[v-1]都是由不同的数字组成的
反之，我们要求 v-u == k, 并且要求a[u],a[u+1],..,a[v-1]恰好是一个全排列

至于为什么要这样定义。仔细想想就好了，每个边其实都代表下标[u,v)之间其实都是不悖于条件的，要么是完整的一个全排列，要么可能是被删去了一部分的全排列。

最后我们判断是否可以由1到达n+1, 若可以则输出YES，反之NO。

注意实现的细节。对于u=1 或 v=n+1， 我们可以特判，由于数字可能会很大，我们可以用set

  unordered_set<int> se;
  for(int i; i <= n; i++) {
    if(a[i] > k) break;
    if(se.find(a[i]) != se.end()) break;
    add(1, i+1);
    se.insert(a[i]);
  } 
  se.clear();
  for(int j = n; j >= 1; j--) {
    if(a[i] > k) break;
    if(se.find(a[j]) != se.end()) break;
    add(j, n+1);
    se.insert(a[j]);
  } 

然后对于另外一种边，我们可以用滑动窗口，至于为什么终点要多加一。自然是为了能让图连上啦。
vi数组用于判断是否出现。当然我们也可以发现只有n<=k的时侯才会出现这种边

int l = 1, cnt = 0;
  if(k <= n)
  for(int i = 1; i <= n; i++) {
    if(a[i] > k) break;
    if(vi[a[i]]) {
      while(l < i && a[l] != a[i]) vi[a[l++]] = 0, cnt--;
      if(l < i) l++;
      if(cnt == k) add(l, i+1);
    } 
    else { 
      cnt++;
      vi[a[i]] = 1;
      if(cnt == k) add(l, i+1);
    }  
  }

然后我们就可以开开心心的用bfs来判断是否可以到达n+1。
我的渣渣代码。
注意初始化！！！

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const double Pi = acos(-1);
namespace {
  template <typename T> inline void read(T &x) {
    x = 0; T f = 1;char s = getchar();
    for(; !isdigit(s); s = getchar()) if(s == '-') f = -1;
    for(;  isdigit(s); s = getchar()) x = (x << 3) + (x << 1) + (s ^ 48);
    x *= f;
  }
}
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define _for(n,m,i) for (register int i = (n); i < (m); ++i)
#define _rep(n,m,i) for (register int i = (n); i <= (m); ++i)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define lowbit(x) x & (-x)
#define pii pair<int,int>
#define fi first
#define se second
vector<int> v[500005];
bool vis[500005];
queue<int> q;
int p, n, a[500005];
void add(int l, int r) {
  v[l].push_back(r);
}
bool dij() {
  while(!q.empty()) q.pop();
  q.push(1);
  while (!q.empty()) {
    p = q.front();
    q.pop();
    if(vis[n+1]) break;
    if(vis[p]) continue;
    vis[p] = 1;
    for(auto it : v[p]) {
      if(!vis[it])
      q.push(it);
    }
  }
  return vis[n+1] == 1;
}
bool vi[500005];
void init() {
  int k; read(n); read(k);
  _rep(1, n, i) read(a[i]), vis[i] = 0, v[i].clear(), vi[i] = 0;
  v[n+1].clear(); vis[n+1] = 0;
  unordered_set<int> se;
  for(int i; i <= n; i++) {
    if(a[i] > k) break;
    if(se.find(a[i]) != se.end()) break;
    add(1, i+1);
    se.insert(a[i]);
  }
  se.clear();
  for(int j = n; j >= 1; j--) {
    if(a[j] > k) break;
    if(se.find(a[j]) != se.end()) break;
    add(j, n+1);
    se.insert(a[j]);
  }
  se.clear();
  int l = 1, cnt = 0;
  if(k <= n)
  for(int i = 1; i <= n; i++) {
    if(a[i] > k) break;
    if(vi[a[i]]) {
      while(l < i && a[l] != a[i]) vi[a[l++]] = 0, cnt--;
      if(l < i) l++;
      if(cnt == k) add(l, i+1);
    }
    else {
      cnt++;
      vi[a[i]] = 1;
      if(cnt == k) add(l, i+1);
    } 
  }
}
int main() {
  int t; read(t);
  while(t--) {
    init();
    if(dij()) cout << "YES" << endl;
    else cout << "NO" << endl;
  }
}