题目解析

给定数组 $a$（元素在 $1$ 到 $n$ 之间）和整数 $k$，定义 $v$ 是子中位数当且仅当存在长度至少为 $k$ 的子数组，使得 $v$ 是该子数组的一个中位数（中位数定义见题目）。需要找出所有子中位数，并为每个子中位数输出任意一个对应的子数组。

关键性质

1. 单调性：如果 $x$ 和 $y$ 都是子中位数且 $x \le y$，那么区间 $[x, y]$ 内的所有整数都是子中位数。因此，子中位数构成一个连续整数区间 $[L, R]$，其中 $L$ 是最小子中位数，$R$ 是最大子中位数。

2. 最大子中位数：可以用二分法求出。对于固定 $v$，定义 $b_i = 1$ 若 $a_i \ge v$，否则 $b_i = -1$。则存在长度 $\ge k$ 的子数组使 $v$ 成为中位数的必要条件是该子数组的 $b$ 之和 $\ge 0$（因为 $\ge v$ 的元素不少于一半）。实际上，对于最大子中位数，这个条件也是充分的（证明见 E1 题解）。因此我们可以二分 $v$ 并检查是否存在长度 $\ge k$ 的子数组满足 $\sum b_i \ge 0$，同时记录找到的区间。

3. 最小子中位数：对称地，定义 $c_i = 1$ 若 $a_i \le v$，否则 $c_i = -1$，则存在子数组使 $v$ 成为中位数等价于 $\sum c_i \ge 0$。同样可以二分求出最小子中位数 $L$。

4. 为每个中间值构造区间：从 $L$ 对应的区间 $[l_L, r_L]$ 出发，通过逐步向左、向右扩展窗口（每次增加一个端点），窗口长度单调增加，中位数区间也会连续变化，从而覆盖 $[L, R]$ 中的所有整数。在扩展过程中，记录每个新出现的中位数对应的当前窗口区间即可。

算法步骤

对于每个测试用例：

1. 使用二分法找到最大子中位数 $R$ 和对应区间 $[l_R, r_R]$。
2. 使用二分法找到最小子中位数 $L$ 和对应区间 $[l_L, r_L]$。
3. 初始化窗口为 $[l_L, r_L]$，用两个 multiset（或堆）维护当前窗口的较小一半和较大一半，以便快速得到当前窗口的中位数区间。
4. 记录当前中位数区间内的所有尚未记录的值，并保存当前窗口作为它们的答案。
5. 不断扩展窗口：先向左扩展（$l \leftarrow l-1$）直到 $l=1$，再向右扩展（$r \leftarrow r+1$）直到 $r=n$。每次扩展后重新计算中位数区间，记录新出现的值。
6. 输出所有子中位数 $v \in [L, R]$ 及其对应的区间。

复杂度分析

• 二分查找 $O(\log n)$ 次，每次检查 $O(n)$，总 $O(n \log n)$。
• 扩展窗口时，端点移动总次数 $O(n)$，每次插入/删除 $O(\log n)$，总 $O(n \log n)$。
• 所有测试用例的 $n$ 之和不超过 $3\times 10^5$，因此总复杂度可接受。

代码实现

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

// 检查是否存在长度≥k的子数组使得≥v的元素不少于一半，并返回一个可行区间（如果存在）
bool check_max(int v, int n, int k, const vector<int>& a, int& out_l, int& out_r) {
    vector<int> b(n);
    for (int i = 0; i < n; ++i) b[i] = (a[i] >= v) ? 1 : -1;
    vector<int> pref(n+1, 0);
    for (int i = 0; i < n; ++i) pref[i+1] = pref[i] + b[i];
    int min_pref = pref[0];
    int min_pos = 0;
    for (int r = k; r <= n; ++r) {
        int idx = r - k;
        if (pref[idx] < min_pref) {
            min_pref = pref[idx];
            min_pos = idx;
        }
        if (pref[r] >= min_pref) {
            out_l = min_pos + 1; // 转为1-index
            out_r = r;
            return true;
        }
    }
    return false;
}

// 检查是否存在长度≥k的子数组使得≤v的元素不少于一半
bool check_min(int v, int n, int k, const vector<int>& a, int& out_l, int& out_r) {
    vector<int> b(n);
    for (int i = 0; i < n; ++i) b[i] = (a[i] <= v) ? 1 : -1;
    vector<int> pref(n+1, 0);
    for (int i = 0; i < n; ++i) pref[i+1] = pref[i] + b[i];
    int min_pref = pref[0];
    int min_pos = 0;
    for (int r = k; r <= n; ++r) {
        int idx = r - k;
        if (pref[idx] < min_pref) {
            min_pref = pref[idx];
            min_pos = idx;
        }
        if (pref[r] >= min_pref) {
            out_l = min_pos + 1;
            out_r = r;
            return true;
        }
    }
    return false;
}

// 维护两个有序集合，模拟当前窗口的较小一半和较大一半
struct MedianTracker {
    multiset<int> small, large;
    int len = 0;
    int target() const { return (len + 1) / 2; } // ceil(len/2)
    void balance() {
        while (small.size() > target()) {
            auto it = prev(small.end());
            large.insert(*it);
            small.erase(it);
        }
        while (small.size() < target() && !large.empty()) {
            auto it = large.begin();
            small.insert(*it);
            large.erase(it);
        }
        // 保证 small 中的所有元素 <= large 中的所有元素
        if (!small.empty() && !large.empty() && *small.rbegin() > *large.begin()) {
            int x = *small.rbegin(), y = *large.begin();
            small.erase(prev(small.end()));
            large.erase(large.begin());
            small.insert(y);
            large.insert(x);
        }
    }
    void insert(int val) {
        if (small.empty() || val <= *small.rbegin()) small.insert(val);
        else large.insert(val);
        ++len;
        balance();
    }
    void erase(int val) {
        auto it = small.find(val);
        if (it != small.end()) small.erase(it);
        else {
            it = large.find(val);
            if (it != large.end()) large.erase(it);
        }
        --len;
        balance();
    }
    // 返回当前窗口的中位数区间 [low, high]
    pair<int,int> median_range() {
        if (len == 0) return {0,0};
        int low = *small.rbegin();
        int high = (len % 2 == 0 && !large.empty()) ? *large.begin() : low;
        return {low, high};
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        vector<int> a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        // 1. 找最大子中位数 R
        int lo = 1, hi = n, R = 1, lR = 0, rR = 0;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            int ltmp, rtmp;
            if (check_max(mid, n, k, a, ltmp, rtmp)) {
                R = mid;
                lR = ltmp; rR = rtmp;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        // 2. 找最小子中位数 L
        lo = 1, hi = n;
        int L = 1, lL = 0, rL = 0;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            int ltmp, rtmp;
            if (check_min(mid, n, k, a, ltmp, rtmp)) {
                L = mid;
                lL = ltmp; rL = rtmp;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        // 3. 滑动窗口，为 [L, R] 中每个值记录区间
        vector<int> ans_l(n+1, -1), ans_r(n+1, -1);
        MedianTracker tracker;
        // 初始化窗口为 [lL, rL]（1-indexed）
        int l = lL, r = rL;
        for (int i = l; i <= r; ++i) tracker.insert(a[i-1]);
        auto [low, high] = tracker.median_range();
        for (int v = low; v <= high; ++v) {
            if (ans_l[v] == -1) {
                ans_l[v] = l;
                ans_r[v] = r;
            }
        }
        // 向左扩展
        while (l > 1) {
            --l;
            tracker.insert(a[l-1]);
            auto [nl, nh] = tracker.median_range();
            for (int v = nl; v <= nh; ++v) {
                if (ans_l[v] == -1) {
                    ans_l[v] = l;
                    ans_r[v] = r;
                }
            }
        }
        // 向右扩展（此时 l 已到 1）
        while (r < n) {
            ++r;
            tracker.insert(a[r-1]);
            auto [nl, nh] = tracker.median_range();
            for (int v = nl; v <= nh; ++v) {
                if (ans_l[v] == -1) {
                    ans_l[v] = l;
                    ans_r[v] = r;
                }
            }
        }
        // 输出答案
        int cnt = R - L + 1;
        cout << cnt << "\n";
        for (int v = L; v <= R; ++v) {
            cout << v << " " << ans_l[v] << " " << ans_r[v] << "\n";
        }
    }
    return 0;
}