单调栈+线段树

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

// 线段树：查询区间内最左边的>=k的元素位置
struct SegmentTree {
    vector<int> tree;
    int n;

    SegmentTree(const vector<int>& arr) {
        n = arr.size() - 1; // 数组是1-based
        tree.resize(4 * (n + 2));
        build(1, 1, n, arr);
    }

    void build(int node, int l, int r, const vector<int>& arr) {
        if (l == r) {
            tree[node] = arr[l];
            return;
        }
        int mid = (l + r) / 2;
        build(2 * node, l, mid, arr);
        build(2 * node + 1, mid + 1, r, arr);
        tree[node] = max(tree[2 * node], tree[2 * node + 1]);
    }

    int query(int l, int r, int k) {
        return query(1, 1, n, l, r, k);
    }

    int query(int node, int node_l, int node_r, int l, int r, int k) {
        if (node_r < l || node_l > r) return -1;
        if (tree[node] < k) return -1;
        if (node_l == node_r) {
            return node_l;
        }
        int mid = (node_l + node_r) / 2;
        // 优先查左子树，找最左边的满足条件的位置
        int left_res = query(2 * node, node_l, mid, l, r, k);
        if (left_res != -1) {
            return left_res;
        }
        return query(2 * node + 1, mid + 1, node_r, l, r, k);
    }
};

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 2); // 1-based索引
    int max_a = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        max_a = max(max_a, a[i]);
    }

    // 1. 预处理left_bound和len数组
    vector<int> left_bound(n + 2, 1);
    vector<int> last_pos(n + 2, 0); // 元素范围1~n，数组直接访问
    for (int i = 1; i <= n; ++i) {
        left_bound[i] = max(left_bound[i - 1], last_pos[a[i]] + 1);
        last_pos[a[i]] = i;
    }
    // len[i]：以i结尾的最长无重复子串长度
    vector<int> len(n + 2);
    for (int i = 1; i <= n; ++i) {
        len[i] = i - left_bound[i] + 1;
    }

    // 2. 单调栈求left_bigger：左边第一个严格大于a[i]的位置
    vector<int> left_bigger(n + 2, 0);
    stack<int> st;
    for (int i = 1; i <= n; ++i) {
        while (!st.empty() && a[st.top()] <= a[i]) {
            st.pop();
        }
        left_bigger[i] = st.empty() ? 0 : st.top();
        st.push(i);
    }

    // 3. 单调栈求right_bigger：右边第一个严格大于a[i]的位置
    vector<int> right_bigger(n + 2, n + 1);
    while (!st.empty()) st.pop();
    for (int i = n; i >= 1; --i) {
        while (!st.empty() && a[st.top()] <= a[i]) {
            st.pop();
        }
        right_bigger[i] = st.empty() ? (n + 1) : st.top();
        st.push(i);
    }

    // 4. 构建线段树
    SegmentTree seg_tree(len);

    // 5. 收集每个值对应的位置
    vector<vector<int>> pos(n + 2);
    for (int i = 1; i <= n; ++i) {
        if (a[i] <= n) { // 超过n的k不可能有解（长度最多n）
            pos[a[i]].push_back(i);
        }
    }

    // 6. 从大到小枚举k，找最长的合法解
    int max_k = min(n, max_a);
    for (int k = max_k; k >= 1; --k) {
        if (pos[k].empty()) continue;
        int min_start = n + 1;
        for (int i : pos[k]) {
            // 计算R'的范围：R'=L'+k-1，窗口[L', R']长度k，最大值k，包含i，无重复
            int A = max(i, left_bigger[i] + k); // R'的下限
            // 修正：嵌套调用min取三个数的最小值
            int B = min(min(right_bigger[i] - 1, i + k - 1), n); // R'的上限
            if (A > B) continue;

            // 查询区间[A,B]内最左边的R'，满足len[R']>=k
            int R_prime = seg_tree.query(A, B, k);
            if (R_prime != -1) {
                int L_prime = R_prime - k + 1;
                if (L_prime < min_start) {
                    min_start = L_prime;
                }
            }
        }
        // 当前k有解，直接输出（最长长度+最早起始位置）
        if (min_start <= n) {
            cout << k << " " << min_start << "\n";
            return;
        }
    }

    // 无解
    cout << "0 0\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

这题要我用sunny过还是有难度啊

首先题目没有描述清吧

应该是找个最长的序列使其包含了1..s中的所有元素吧，当然没有重复的数出现

然后其中必然包含1吧，抓住1这个元素

假设最大值在右边则递增r，去除左边重复的点，维护l，如果r-l+1=max（其中最大的数）则更新ans

同理假设最大值在左边递减l去除右边部行的点

这题相当好，赞！！！

这题目的样例数据没问题么？

看了楼下的简短思路。。我自愧不如。我的方法不难写但是想起来很绕，不理清楚思路写不下去。。所以虽然比较短但是写了快2小时。。

我的做法是这样的:

如果一个序列最大值等于长度且没有重复元素，那么就是一个合法方案。

首先求出每个点往右最远能到多少使得无重复的点，然后求出每个点i出发的这样一个序列：第一个元素是点i，第二个元素是i右边中最左边的>a[i]的元素j，第三个是j右边中最左边的>a[j]的元素k..以此类推。，然后如果在这个序列中存在某个元素q(q对应的实际上是下标,令队列中q的后面的一个元素是r)满足：i∈[q-a[q]+1，(r-1)-a[q]+1]，则a[q]这个长度是可以取到的。但是枚举判断还是O(n^2)，这里我们注意到一个冗余：当队列中元素后继以及本身不变时，对应的[q-a[q]+1，(r-1)-a[q]+1]是不变的，那么我们就可以考虑对于每一个区间，受他影响的i是哪些（显然能受这个区间影响的i一定是i所对应的序列中，q r依然是相邻的元素），可以注意到受区间影响的i一定是连续的，因此枚举判断区间对应的长度，考虑两个区间是否有交即可。O(n)

我是先用最小表示法对数据分组

使每一组内无重复数据

再递归不断划分

知道每组的长度=该组内的最大数

可以用最优性剪枝

├ 测试数据 07：答案正确... 728ms

├ 测试数据 08：答案正确... 712ms

├ 测试数据 09：答案正确... 712ms

├ 测试数据 10：答案正确... 712ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2864ms

写的貌似不怎么样

不过还是过了

一样的程序,一样的机子.不一样的分数..

嘿嘿 原来的题解被delete了

SPOJ原题...

O(T*n^2)，居然过了，而且表现很好（除了1个点0.9s-其他都0ms）

数据太随机了。偶自己已经构造出来达到那个平方的数据了。

O(N)的差不多都要2s..

这题细节里挂了不少...自己总是懒得去静态调试（以后得改正）

终于AC，20次提交啊

我kao, 标程能能超...

数据没错

AC

第一个

编译通过...├ 测试数据 01：答案正确... 0ms├ 测试数据 02：答案正确... 0ms├ 测试数据 03：答案正确... 0ms├ 测试数据 04：答案正确... 0ms├ 测试数据 05：答案正确... 0ms├ 测试数据 06：答案正确... 0ms├ 测试数据 07：答案正确... 650ms├ 测试数据 08：答案正确... 619ms├ 测试数据 09：答案正确... 650ms├ 测试数据 10：答案正确... 0ms-------------------------Accepted 有效得分：100 有效耗时：1919ms

汗..来晚了

写写题解巩固下.

在读入数据时可以搜索没两个卖一样的食物的店铺中间,如果不能则可以舍掉这个区间.,建一个a数组用来存第I个数在map数组中的第几个.

当且仅当当前有J 个数,最大值=j时且无重复即为正解,与目前最佳比较下就行了.

每次搜索从1开始往周围扩展..

编译通过...

├ **测试数据 01：答案正确... 0ms**

├ **测试数据 02：答案正确... 0ms**

├ **测试数据 03：答案正确... 0ms**

├ **测试数据 04：答案正确... 0ms**

├ **测试数据 05：答案正确... 0ms**

├ **测试数据 06：答案正确... 0ms**

├ **测试数据 07：答案正确... 416ms**

├ **测试数据 08：答案正确... 525ms**

├ **测试数据 09：答案正确... 588ms**

├ **测试数据 10：答案正确... 478ms**

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2007**ms**

地下室的地板

..数据范围我咋看不懂………………

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 384ms

├ 测试数据 08：答案正确... 369ms

├ 测试数据 09：答案正确... 322ms

├ 测试数据 10：答案正确... 306ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1381ms

mt orz

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 869ms

├ 测试数据 08：答案正确... 916ms

├ 测试数据 09：答案正确... 916ms

├ 测试数据 10：答案正确... 916ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：3617ms

我好怕怕，好恐怖的时间。。。。。。

乱七八糟的几个优化加几个弱弱的剪枝，发现自己原来只是一个菜鸟，5KB200行，强烈膜拜voyagec2神牛！！！！！！