[SCOI2009]生日礼物

这道题很容易看出是一道单调队列题。

首先我们根据珠子的位置排序。

然后按顺序枚举一个个珠子。

如果该种珠子没有出现过标记上它的位置，如果出现过修改并打上当前位置。当所有珠子都出现后，将当前位置减去打标记位置最小的一个即为当前解。

可以证明正确性。

显然选择珠子越靠后越好。

最小位置的查找要$O(K)$，所以复杂度为$O(NK)$。

这道题$K$比较小，该复杂度能过。但当$K$较大时会超时。

我们充分运用单调队列的性质，牺牲空间换取时间。

具体做法就是开一个数组记录第$i$个珠子是否在标记中，然后用一个指针$P$记录位置最小的珠子。

珠子只会从前往后打上标记，所以当取消珠子的标记时，根据需要向后移动$P$指针直到再一次指向位置最小的珠子即可。

#include <bits/stdc++.h>

using namespace std;

#define re register
#define rep(i, a, b) for (re int i = a; i <= b; ++i)
#define repd(i, a, b) for (re int i = a; i >= b; --i)
#define maxx(a, b) a = max(a, b);
#define minn(a, b) a = min(a, b);
#define LL long long
#define inf (1 << 30)

inline int read() {
    int w = 0, f = 1; char c = getchar();
    while (!isdigit(c)) f = c == '-' ? -1 : f, c = getchar();
    while (isdigit(c)) w = (w << 3) + (w << 1) + (c ^ '0'), c = getchar();
    return w * f;
}

const int maxn = 1e6 + 5, maxk = 60 + 5;

struct Ball {
    int k, p;
} A[maxn];
bool cmp(Ball a, Ball b) {
    return a.p < b.p;
}

int loc[maxk], N, K, tag[maxn];

int main() {
    N = read(), K = read();

    int P = 0;
    rep(i, 1, K) {
        int T = read();
        rep(x, 1, T) A[++P] = (Ball){i, read()};
    }
    sort(A+1, A+N+1, cmp);
    P = 0;
    int cnt = 0, ans = (1<<31)-1;
    memset(tag, 0, sizeof(tag));
    rep(i, 1, N) {
        tag[loc[A[i].k]] = 0;
        if (!loc[A[i].k]) cnt++;
        loc[A[i].k] = i;
        tag[loc[A[i].k]] = 1;
        while (!tag[P]) P++;
        if (cnt == K) minn(ans, A[i].p - A[P].p);
    }
    printf("%d", ans);
    return 0;
}