[洛谷 P1638] 逛画展

题目

题目链接

题目大意：给出一个长度为 $n$ 的序列，要求找到一段连续的子序列，满足子序列里出现所有 $1$ 到 $m$ 中的数。$1 \le n \le 10^6, 1 \le m \le 2000$。

思路

想了下 Two Pointers 应该算某种意义上的队列？

考虑用两个指针 $l, r$ 分别指向当前区间的左端点和右端点，维护一个 $s$ 表示当前区间内有多少不同的数，$v_i$ 表示当前区间里数 $i$ 的个数。

如果当前区间里的数不够就把 $r$ 往右移，够了的话就更新答案，然后把 $l$ 往右移。

然后就做完了。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

template <class T>
inline void read(T &x) {
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return ;
}

typedef unsigned long long uLL;
typedef long long LL;

int a[1000010], vis[2010];
int n, m, l = 1, r, ansl = 1, ansr, s, min = 0x3f3f3f3f;

int main() {
    read(n), read(m);
    ansl = 1, ansr = n;
    for (int i = 1; i <= n; ++i)	read(a[i]);
    while (l <= n) {
        while (s < m && r < n) {
            ++r;
            if (!vis[a[r]])	++s;
            ++vis[a[r]];
        }
        --vis[a[l]];
        if (!vis[a[l]])	--s;
        ++l;
        if (r - l < min && s == m)	ansl = l, ansr = r, min = r - l;
    }
    printf("%d %d\n", ansl, ansr);
    return 0;
}