洛谷 P1638 逛画展

// P1638 的第 ① 版：枚举左端点，往右一直扫到「五种画家都齐了」
//
// 这是最直接的想法，也确实是对的。★ 题面把它的分数标出来了：
//   「对于 30% 的数据，n <= 200，m <= 20」—— 这一档它稳过，**考场上是实打实的 30 分**。
//   「对于 60% 的数据，n <= 1e5，m <= 1e3」—— 这一档就悬了。
//
// ⚠ 它每换一个左端点都要把 cnt 清一遍（O(m)），再往右扫到齐全（平均 m·ln m 步）。
//   满数据 n = 1e6、m = 2000 时大约 1.6×10¹⁰ 次 —— 没有任何机会。
//
// ★ 它慢在哪很值得说清楚：**左端点右移一格，右边那一大段是白扫的** ——
//   上一轮已经知道 [x, y] 齐全了，这一轮从 x+1 开始又从头数了一遍。
//   滑动窗口就是把这段重复的账省掉。

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

static int a[1000005];
static int cnt[2005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];

    int best = INT_MAX, bx = 1, by = n;
    for (int x = 1; x <= n; x++) {
        memset(cnt, 0, sizeof(int) * (size_t)(m + 1));
        int kinds = 0;
        for (int y = x; y <= n; y++) {
            if (cnt[a[y]]++ == 0) kinds++;
            if (kinds == m) {
                if (y - x + 1 < best) { best = y - x + 1; bx = x; by = y; }
                break;                                   // 再往右只会更长
            }
        }
    }
    cout << bx << ' ' << by << '\n';
    return 0;
}

// P1638 逛画展 —— 能 AC 的那一版：滑动窗口 + 计数数组
//
// 要的是「包含全部 m 种画家、长度最短」的区间，多组解取左端点最小的那组。
//
// 窗口 [l, r]：`cnt[v]` 是窗口里画家 v 出现了几次，`kinds` 是窗口里有几种画家。
//   r 每往右吃一个数 -> cnt[a[r]]++，如果它从 0 变 1，kinds++
//   然后把左端**能缩就缩**：cnt[a[l]] > 1 说明 a[l] 是多余的（窗口里还有一个），扔掉它
//   缩到不能再缩之后，如果 kinds == m，这就是「以 r 为右端点」的最短合法区间
//
// ★ 双指针的前提在这里长这样：r 往右走只会让 kinds 变大或不变，
//   l 往右走只会让 kinds 变小或不变 —— **两个指针都不用回退**，总共走 2n 步。
//
// ⚠ 两个细节，各值一条测试点：
//   ① 收缩要用 **while** 不是 if —— 一次可能要扔掉好几个多余的数（见 p1638If.cpp）
//   ② 更新最优要用 **严格小于** —— 题面说「若存在多组解，输出 x 最小的那组」，
//      而 r 是从左往右扫的，写成 <= 就会被后面等长的解顶掉（见 p1638Le.cpp）

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

static int a[1000005];
static int cnt[2005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];

    int l = 1, kinds = 0, best = INT_MAX, bx = 1, by = n;
    for (int r = 1; r <= n; r++) {
        if (cnt[a[r]]++ == 0) kinds++;
        while (cnt[a[l]] > 1) { cnt[a[l]]--; l++; }      // ① while，不是 if
        if (kinds == m && r - l + 1 < best) {            // ② 严格小于
            best = r - l + 1; bx = l; by = r;
        }
    }
    cout << bx << ' ' << by << '\n';
    return 0;
}

// 演示错误写法：更新最优用了 <= 而不是 <
//
// 题面那句「**若存在多组解，输出 x 最小的那组**」就落在这一个字符上。
//
// 右端点 r 是从左往右扫的，所以**后来出现的等长解，左端点一定更大**。
// 写成 <= 就会被后面那个顶掉 ⇒ 输出的是 **x 最大**的那组。
//
// ★ 它露头的条件很硬：**必须存在两组以上等长的最优解**。
//   随机数据上这不常见；对拍档位 1 专门造了「1..m 反复循环」这种形状 ——
//   那时每一个长度为 m 的窗口都是最优解，一共 n − m + 1 组。

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

static int a[1000005];
static int cnt[2005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];

    int l = 1, kinds = 0, best = INT_MAX, bx = 1, by = n;
    for (int r = 1; r <= n; r++) {
        if (cnt[a[r]]++ == 0) kinds++;
        while (cnt[a[l]] > 1) { cnt[a[l]]--; l++; }
        if (kinds == m && r - l + 1 <= best) { best = r - l + 1; bx = l; by = r; }   // ← <=
    }
    cout << bx << ' ' << by << '\n';
    return 0;
}

// 演示错误写法：收缩左端用了 if 而不是 while
//
// 和正解只差一个词。窗口右端吃进一个数之后，左边可能**一口气**多出好几个多余的数，
// 一次只扔一个是不够的。
//
// ⚠ 它给出的区间**仍然包含全部 m 种**（所以肉眼看着「对」），只是**不够短**。
//   ⇒ 这类 bug 靠「答案看起来合理」是发现不了的，只能对拍。
//   ★ 它露头的条件：窗口左边要**连续出现两个以上多余的数** —— 值域越小越容易撞上。

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

static int a[1000005];
static int cnt[2005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];

    int l = 1, kinds = 0, best = INT_MAX, bx = 1, by = n;
    for (int r = 1; r <= n; r++) {
        if (cnt[a[r]]++ == 0) kinds++;
        if (cnt[a[l]] > 1) { cnt[a[l]]--; l++; }         // ← if：一次只扔一个
        if (kinds == m && r - l + 1 < best) { best = r - l + 1; bx = l; by = r; }
    }
    cout << bx << ' ' << by << '\n';
    return 0;
}

// P1638 的第二关：n 到 10⁶ 了，读入还来得及吗？
//
// 用法：./p1638Read [n] [m] [csv]      默认 n = 1000000、m = 2000（就是满数据）
//   ★ 它自己造一份 P1638 形状的输入写进临时文件，再 freopen 回 stdin 读四遍 ——
//     不需要喂输入。四遍的**答案必须一模一样**（csv 里的 same 就是钉这件事的）。
//
// 四种读法（第 45 章第 11 步解释过它们的区别，这里量的是**这道题上的**代价）：
//   ① cin（默认，同步开着）    ② cin + sync_with_stdio(false)
//   ③ scanf                    ④ 手写快读（fread 整块读进来自己拼数字）
//
// ⚠ 顺序不能换：关掉同步之后 cin 会自己预读一大块，之后再 freopen 换文件，
//   cin 缓冲里剩的就是上一份文件的残渣 ⇒ 「同步开着」那一趟必须排在最前面
//   （这条坑是第 45 章 read.cpp 里踩过的，照抄它的顺序）。
//
// ★★ 这道题和第 6 章 [P2367] 是一对：那道题要读 2×10⁷ 个整数，**连 scanf 都不够**；
//   这道题只读 10⁶ 个 —— 结论会不会一样，正文第 7 步摆了两张表并排看。

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

static char path[64];
static int a[1000005];
static int cnt[2005];

static void makeData(int n, int m) {
    snprintf(path, sizeof(path), "/tmp/p1638-bench-%d.txt", (int)getpid());
    FILE* f = fopen(path, "w");
    if (!f) { fprintf(stderr, "写不出临时文件 %s\n", path); exit(1); }
    mt19937 rng(20260827u);
    vector<int> v(n);
    for (int i = 0; i < n; i++) v[i] = 1 + (int)(rng() % (unsigned)m);
    vector<int> pos(n);
    for (int i = 0; i < n; i++) pos[i] = i;
    shuffle(pos.begin(), pos.end(), rng);
    for (int c = 1; c <= m; c++) v[pos[c - 1]] = c;          // 保证 m 种齐全
    fprintf(f, "%d %d\n", n, m);
    for (int i = 0; i < n; i++) fprintf(f, "%d%c", v[i], i + 1 == n ? '\n' : ' ');
    fclose(f);
}
static void reopen() {
    if (!freopen(path, "r", stdin)) { fprintf(stderr, "读不回临时文件\n"); exit(1); }
}

/* 滑动窗口那几行 —— 四趟共用，所以四趟之间的差别只可能来自读入 */
static long long solve(int n, int m) {
    memset(cnt, 0, sizeof(int) * (size_t)(m + 1));
    int l = 1, kinds = 0, best = INT_MAX, bx = 1, by = n;
    for (int r = 1; r <= n; r++) {
        if (cnt[a[r]]++ == 0) kinds++;
        while (cnt[a[l]] > 1) { cnt[a[l]]--; l++; }
        if (kinds == m && r - l + 1 < best) { best = r - l + 1; bx = l; by = r; }
    }
    return (long long)bx * 1000000000LL + by;
}

static char ibuf[1 << 22];
static size_t ipos = 0, ilen = 0;
static inline int gc() {
    if (ipos == ilen) { ilen = fread(ibuf, 1, sizeof(ibuf), stdin); ipos = 0; if (!ilen) return EOF; }
    return ibuf[ipos++];
}
static inline int readIntFast() {
    int c = gc(), x = 0;
    while (c != EOF && (c < '0' || c > '9')) c = gc();
    for (; c >= '0' && c <= '9'; c = gc()) x = x * 10 + (c - '0');
    return x;
}

int main(int argc, char** argv) {
    int n = (argc > 1) ? atoi(argv[1]) : 1000000;
    int m = (argc > 2) ? atoi(argv[2]) : 2000;
    bool csv = (argc > 3 && string(argv[3]) == "csv");
    makeData(n, m);
    double ms[4];
    long long ans[4];

    /* ① cin（默认，同步开着）—— 必须排第一趟 */
    { reopen();
      auto t0 = steady_clock::now();
      int nn, mm; cin >> nn >> mm;
      for (int i = 1; i <= nn; i++) cin >> a[i];
      ans[0] = solve(nn, mm);
      ms[0] = duration<double, milli>(steady_clock::now() - t0).count(); }

    /* ② cin + sync_with_stdio(false) */
    { reopen();
      auto t0 = steady_clock::now();
      ios::sync_with_stdio(false); cin.tie(nullptr);
      int nn, mm; cin >> nn >> mm;
      for (int i = 1; i <= nn; i++) cin >> a[i];
      ans[1] = solve(nn, mm);
      ms[1] = duration<double, milli>(steady_clock::now() - t0).count(); }

    /* ③ scanf */
    { reopen();
      auto t0 = steady_clock::now();
      int nn = 0, mm = 0; if (scanf("%d %d", &nn, &mm) != 2) { nn = mm = 0; }
      for (int i = 1; i <= nn; i++) { if (scanf("%d", &a[i]) != 1) break; }
      ans[2] = solve(nn, mm);
      ms[2] = duration<double, milli>(steady_clock::now() - t0).count(); }

    /* ④ 手写快读 */
    { reopen(); ipos = ilen = 0;
      auto t0 = steady_clock::now();
      int nn = readIntFast(), mm = readIntFast();
      for (int i = 1; i <= nn; i++) a[i] = readIntFast();
      ans[3] = solve(nn, mm);
      ms[3] = duration<double, milli>(steady_clock::now() - t0).count(); }

    remove(path);
    bool same = (ans[0] == ans[1] && ans[1] == ans[2] && ans[2] == ans[3]);
    if (csv) {
        const char* key[4] = { "cin", "nosync", "scanf", "fast" };
        for (int k = 0; k < 4; k++) printf("%s,%.1f\n", key[k], ms[k]);
        printf("same,%d\nx,%lld\ny,%lld\n", same ? 1 : 0, ans[0] / 1000000000LL, ans[0] % 1000000000LL);
        return 0;
    }
    const char* name[4] = { "cin（默认，同步开着）", "cin + sync_with_stdio(false)",
                            "scanf", "手写快读（fread）" };
    /* ⚠ 中文是双宽的，%-30s 按字节数补空格会补歪 —— 照第 45 章 read.cpp 那套按显示宽度补 */
    auto disp = [](const string& t) {
        int w = 0;
        for (unsigned char c : t) { if ((c & 0xC0) == 0x80) continue; w += (c < 0x80) ? 1 : 2; }
        return w;
    };
    auto padR = [&](const string& t, int w) { return t + string(max(0, w - disp(t)), ' '); };
    double best = *min_element(ms, ms + 4);
    printf("n = %d, m = %d（读 %d 个整数），四种读法跑同一个滑动窗口：\n\n", n, m, n);
    for (int k = 0; k < 4; k++)
        printf("  %s %8.1f 毫秒   慢 %4.1f 倍\n", padR(name[k], 30).c_str(), ms[k], ms[k] / best);
    printf("\n四趟的答案%s（都是 %lld %lld）\n", same ? "完全一致" : "居然不一致！",
           ans[0] / 1000000000LL, ans[0] % 1000000000LL);
    return 0;
}

// 数据生成器（P1638 对拍用）：`./p1638Gen <seed> [level]`
//
//   level 0（默认）随机：n <= 30、m <= 8，**1..m 各先放一个到随机位置**（保证有解）
//   level 1        **多组等长最优**：1..m 反复循环（1 2 … m 1 2 … m …），
//                  于是每一个长度为 m 的窗口都是最优解，一共 n − m + 1 组
//   level 2        **左边扎堆重复**：只用 2~3 种画家把序列铺满，再零星撒进其余种类
//
// ★ 三个档位各盯一个错版：
//   level 1 是给 p1638Le（`<=` 顶掉了 x 更小的解）造的 —— 没有等长解它就抓不到；
//   level 2 是给 p1638If（一次只缩一格）造的 —— 要左边**连续**堆着好几个多余的数才露头；
//   level 0 是兜底。
//
// ⚠ 题面「数据保证一定有解」，所以三个档位都必须自己保证 m 种齐全。
//   随机撒 a_i ∈ [1, m] 是不够的：凑齐 m 种平均要 m·ln m 个数（集邮问题），
//   n <= 30、m = 8 时经常凑不齐。⇒ 第 5 章 P1618 那条「先造出有答案的数据」。

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

static mt19937 rng;
static int ri(int lo, int hi) { return lo + (int)(rng() % (unsigned)(hi - lo + 1)); }

int main(int argc, char** argv) {
    unsigned seed = (argc > 1) ? (unsigned)atoi(argv[1]) : 1;
    int level = (argc > 2) ? atoi(argv[2]) : 0;
    rng.seed(seed);

    int m = ri(1, 8);
    int n = ri(m, 30);
    vector<int> a(n);

    if (level == 1) {
        for (int i = 0; i < n; i++) a[i] = i % m + 1;                 // 1 2 … m 1 2 … m …
    } else if (level == 2) {
        int few = min(m, ri(2, 3));
        for (int i = 0; i < n; i++) a[i] = ri(1, few);                // 先用 2~3 种铺满
        vector<int> pos(n);
        for (int i = 0; i < n; i++) pos[i] = i;
        shuffle(pos.begin(), pos.end(), rng);
        for (int v = 1; v <= m; v++) a[pos[v - 1]] = v;               // 再保证 m 种齐全
    } else {
        for (int i = 0; i < n; i++) a[i] = ri(1, m);
        vector<int> pos(n);
        for (int i = 0; i < n; i++) pos[i] = i;
        shuffle(pos.begin(), pos.end(), rng);
        for (int v = 1; v <= m; v++) a[pos[v - 1]] = v;
    }
    printf("%d %d\n", n, m);
    for (int i = 0; i < n; i++) printf("%d%c", a[i], i == n - 1 ? '\n' : ' ');
    return 0;
}

// 大数据生成器（P1638 计时用）：`./p1638GenBig [n] [m] [level]`
//
//   level 0（默认）随机 a_i ∈ [1, m]，并保证 1..m 各出现至少一次
//   level 1        **最坏形状**：前 n−m 个位置全是画家 1，最后 m 个位置才把 2..m 亮出来
//                  ⇒ 暴力的每一个左端点都要一路扫到接近末尾
//
// ★ 两个档位差得很远：档位 0 的最短窗口大约 m·ln m（随机），
//   档位 1 的最短窗口是 m，但**暴力**要扫的距离几乎是整个数组 ——
//   「量上限」要用档位 1（第 5 章 P1563 那条：**要量上限就把旋钮拧到头**）。

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

static mt19937 rng;

int main(int argc, char** argv) {
    int n = (argc > 1) ? atoi(argv[1]) : 1000000;
    int m = (argc > 2) ? atoi(argv[2]) : 2000;
    int level = (argc > 3) ? atoi(argv[3]) : 0;
    rng.seed(12345);
    vector<int> a(n);
    if (level == 1) {
        for (int i = 0; i < n; i++) a[i] = 1;
        for (int v = 2; v <= m; v++) a[n - m + v - 1] = v;
    } else {
        for (int i = 0; i < n; i++) a[i] = 1 + (int)(rng() % (unsigned)m);
        vector<int> pos(n);
        for (int i = 0; i < n; i++) pos[i] = i;
        shuffle(pos.begin(), pos.end(), rng);
        for (int v = 1; v <= m; v++) a[pos[v - 1]] = v;
    }
    printf("%d %d\n", n, m);
    for (int i = 0; i < n; i++) printf("%d%c", a[i], i == n - 1 ? '\n' : ' ');
    return 0;
}

// 换一把尺子：两种写法各碰了多少下（外加一笔「随机数据够不够齐全」的账）
//
// 用法：./p1638Count <n> <m>        人话版（带秒表）
//       ./p1638Count <n> <m> csv    只打 `键,值`，给 check:viz 用
//
// ① 尺子：暴力每换一个左端点都要重新往右数一遍；滑动窗口两个指针各走一趟，一共 2n 步。
//    ⇒ 这一比是「重复的账」到底有多少。
//
// ② 顺带一笔常被忽略的账：**随机造 a_i ∈ [1, m] 的数据，n 要多大才几乎必然 m 种齐全？**
//    这是「集邮问题」：期望要 m·(1 + 1/2 + … + 1/m) ≈ m·ln m 个数。
//    m = 2000 时约 16 400 —— 满数据 n = 10⁶ 远远够；
//    但对拍用的小数据（n <= 30、m <= 8）就常常凑不齐 ⇒ **生成器必须自己保证有解**。
//    （第 5 章 P1618 那条：「先造出有答案的数据」。）

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

static double now_ms() {
    timespec t;
    clock_gettime(CLOCK_MONOTONIC, &t);
    return t.tv_sec * 1000.0 + t.tv_nsec / 1e6;
}

int main(int argc, char** argv) {
    int n = (argc > 1) ? atoi(argv[1]) : 20000;
    int m = (argc > 2) ? atoi(argv[2]) : 200;
    bool csv = (argc > 3 && string(argv[3]) == "csv");

    /* 造一份「保证有解」的随机数据：先把 1..m 各放一个到随机位置，其余随机填 */
    mt19937 rng(20260827u);
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) a[i] = 1 + (int)(rng() % (unsigned)m);
    {
        vector<int> pos(n);
        for (int i = 0; i < n; i++) pos[i] = i + 1;
        shuffle(pos.begin(), pos.end(), rng);
        for (int v = 1; v <= m; v++) a[pos[v - 1]] = v;
    }

    vector<int> cnt(m + 1, 0);
    long long bruteIter = 0;
    double t0 = now_ms();
    int bBest = INT_MAX, bx = 1, by = n;
    for (int x = 1; x <= n; x++) {
        fill(cnt.begin(), cnt.end(), 0);
        bruteIter += m + 1;                              // 清 cnt 也是实打实的开销
        int kinds = 0;
        for (int y = x; y <= n; y++) {
            bruteIter++;
            if (cnt[a[y]]++ == 0) kinds++;
            if (kinds == m) { if (y - x + 1 < bBest) { bBest = y - x + 1; bx = x; by = y; } break; }
        }
    }
    double tBrute = now_ms() - t0;

    fill(cnt.begin(), cnt.end(), 0);
    long long winIter = 0;
    t0 = now_ms();
    int wBest = INT_MAX, wx = 1, wy = n;
    {
        int l = 1, kinds = 0;
        for (int r = 1; r <= n; r++) {
            winIter++;
            if (cnt[a[r]]++ == 0) kinds++;
            while (cnt[a[l]] > 1) { winIter++; cnt[a[l]]--; l++; }
            if (kinds == m && r - l + 1 < wBest) { wBest = r - l + 1; wx = l; wy = r; }
        }
    }
    double tWin = now_ms() - t0;

    /* 集邮问题：随机取 a_i ∈ [1, m] 时，凑齐 m 种平均要几个数 */
    double coupon = 0;
    for (int i = 1; i <= m; i++) coupon += 1.0 / i;
    coupon *= m;

    if (csv) {
        printf("n,%d\nm,%d\nbrute,%lld\nwin,%lld\nratio,%lld\n"
               "same,%d\nbest,%d\nx,%d\ny,%d\ncoupon,%d\n",
               n, m, bruteIter, winIter, bruteIter / winIter,
               (bBest == wBest && bx == wx && by == wy) ? 1 : 0,
               wBest, wx, wy, (int)(coupon + 0.5));
    } else {
        printf("n = %d, m = %d（随机数据，1..m 各保证出现一次）\n\n", n, m);
        printf("(1) 枚举左端点  %12lld 次   %8.1f ms\n", bruteIter, tBrute);
        printf("(2) 滑动窗口    %12lld 次   %8.1f ms\n", winIter, tWin);
        printf("=> 差 %lld 倍\n\n", bruteIter / winIter);
        printf("两版答案%s：%d %d（长度 %d）\n\n",
               (bBest == wBest && bx == wx && by == wy) ? "一致" : "不一致！", wx, wy, wBest);
        printf("集邮问题：随机取 a_i in [1, %d]，凑齐 %d 种平均要 %d 个数\n", m, m, (int)(coupon + 0.5));
        printf("  => 满数据 n = 1e6 远远够用；但对拍的小数据必须由生成器保证有解\n");
    }
    return 0;
}