D2 - Queue

操作の順序は答えに関係ないので、最終的な筒、箱の状態に着目すると、「筒 : 配列 $A$ の連続部分列、箱:配列 $A$ から、最終時点の筒にあるの要素を除いたいたもの」となります。
以後、「 $f(X)$ :=配列Xの要素の種類数」とします。
問題文を言い換えると、「配列 $A$ の連続部分列のうち、$f(A) = f(B)$を満たす最長のものを求め、$n$ からその値を引いたものを出力してください 」となります。
愚直に連続部分列の左端及び右端 $l,r$ を決めて種類数を求めると $O(N^3)$ となり、TLEしてしまいます。
しかし、配列の長さと配列の要素の種類数は単調性あり、今回の場合でも $f(A) - f(B)$に単調性があるので尺取り法が利用できます。 $f(A)≦f(B)$ ならば右端を進め、そうでないなら左端を進めます。一連の流れの中で $f(A)=f(B)$ となるものがあれば、答えの候補としその中の最大値が$f(A) = f(B)$を満たす最長のものです。

ある状態の $f(A)=x, f(B)=y$ とおきます。rをひとつ進めた時、$f(A')=x, x+1、f(B')=y-1, y$ の $4$ パターンが考えられます。どのパターンにおいても $f(A)-f(B)≦f(A')-f(B')$が成り立つので本問題では単調性があると言えます。$l$ についても同様です。

類題

• 034 - There are few types of elements（★4）

def f(e,A,B):
    if(e not in A):
        A[e] = 1
    else:
        A[e] += 1
    
    B[e] -= 1
    if(B[e] == 0):
        del B[e]

n = int(input())
A = list(map(int,input().split()))

cntA = {}
cntB = {}
for i in range(n):
    if(A[i] not in cntB):
        cntB[A[i]] = 1
    else:
        cntB[A[i]] += 1

ans = 10**18
j = 0

for i in range(n-1):
    if(len(cntA) == len(cntB)):
        ans = min(ans, n-(j-i))
    while j < n and len(cntA) <= len(cntB):
        f(A[j], cntA, cntB)
        j += 1
        if(len(cntA) == len(cntB)):
            ans = min(ans,n-(j-i))

    f(A[i], cntB, cntA)


if(ans == 10**18):
    print(-1)
    exit()
print(ans)

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

void push(map<int, int>& Box, int& count, int number) {
    if (Box[number] == 0) count++;
    Box[number]++;
}
void pop(map<int, int>& Box, int& count, int number) {
    Box[number]--;
    if (Box[number] == 0) count--;
}

int main() {

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    map<int, int>A, B;
    int Ac = 0, Bc = 0;

    for (int i = 0; i < n; i++) push(B, Bc, a[i]);

    int ans = -1;
    for (int l = 0, r = 0; l < n;) {
        while (r < n && Ac <= Bc) {
            push(A, Ac, a[r]);
            pop(B, Bc, a[r]);
            r++;
            if (Ac == Bc) ans = max(ans, r - l);
        }
        
        push(B, Bc, a[l]);
        pop(A, Ac, a[l]);
        l++;
        if (Ac == Bc) ans = max(ans, r - l);
    }

    if (ans == -1) {
        cout << -1 << endl;
    }
    else {
        cout << n - ans << endl;
    }
}