[CF1450D] Rating Compression

[CF1450D] Rating Compression

Description

给定序列，问长度为 (k) 的滑动窗口最小值是否构成排列

Solution

(k=1) 的情况特判掉

用双端队列，初态为 ([a_1,a_2,...,a_n])

从 (1) 到 (n) 枚举 (c) 的长度 (i)

若数 (i) 没有出现，则长度 (ge i) 的都废了

若数 (i) 出现了，则长度 (=i) 的活了

若数 (i) 出现在当前剩余部分的头尾，那么删掉他并继续

若数 (i) 出现在当前剩余部分的中间，或者出现次数大于 (1)，那么长度 (>i) 的都死了

#include <bits/stdc++.h>
using namespace std;

#define int long long

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 2);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    vector<int> ans(n + 2);
    vector<int> cnt(n + 2);
    for (int i = 1; i <= n; i++)
        cnt[a[i]]++;
    if (*max_element(&cnt[1], &cnt[n + 1]) == 1)
        ans[1] = 1;
    deque<int> que;
    for (int i = 1; i <= n; i++)
        que.push_front(a[i]);
    for (int i = 1; i < n; i++)
    {
        if (cnt[i] == 0)
            break;
        ans[n - i + 1] = 1;
        if (que.front() == i)
            que.pop_front();
        else if (que.back() == i)
            que.pop_back();
        else
            break;
        if (cnt[i] > 1)
            break;
    }
    for (int i = 1; i <= n; i++)
        cout << ans[i];
    cout << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
}