[C++知识库]深渊水妖

题目链接

你进行了 nnn 次考试，第 iii 次考试的分数是 aia_iai?。

你想知道你最大进步的幅度是多少，定义最大进步的幅度为：
?

1. 选定一段?极长?的区间 [l,r][l,r][l,r]，满足 al≤al+1≤?≤ara_l\le a_{l+1}\le\cdots\le a_ral?≤al+1?≤?≤ar?。

2. 满足条件一的情况下，使得 ar?ala_r-a_lar??al? 的值最大。

如果你有多段最大进步，你需要输出所有的最大进步段，每一段用两个数 l,rl,rl,r 表示，按照区间的左端点升序输出。

一句话题意：找到所有极长的不严格上升段，并找出它们当中右端点权值 - 左端点权值最大的那些个段，输出端点坐标。

输入描述:

全文第一行输入一个正整数 T(1≤T≤105)T(1\le T\le10^5)T(1≤T≤105)，表示数据组数。

每组数据第一行输入一个正整数 n(2≤n≤105)n(2\le n\le10^5)n(2≤n≤105)。

第二行输入 nnn 个正整数，第 iii 个正整数是 ai(1≤ai≤n)a_i(1\le a_i\le n)ai?(1≤ai?≤n)。

数据保证 ∑n≤3×106\sum n\le3\times10^6∑n≤3×106，保证至少存在一个 i∈[2,n]i\in[2,n]i∈[2,n] 满足 ai≥ai?1a_i\ge a_{i-1}ai?≥ai?1?。

输出描述:

对每组询问输出一行，表示你所得到的所有答案。

示例1

输入

1
7
1 3 5 2 4 6 3

输出

1 3 4 6

备注:

区间 [1,3] 是 1,3,5，满足 1≤3≤5 并且 5?1=4差值最大。

区间 [4,6] 同理，6?2=4 同样为最大的差值。

思路：这个题与最长上升子序列的题目很像，但是最长上升子序列的数据非常少，直接就能暴力过（n^2时间复杂度）。这个题让求得是：（值）最大的上升子串。子串这个就非常简单了，挨着遍历一遍就能找最大的子串，题中说会有多个最大的子串，那么我们在遍历一遍，差值是最大的就行。

分开想：先找最大的子串，再找出重复的最大子串。

完整代码：

#include <bits/stdc++.h>

using namespace std;

#define int long long
const int mod=1e9+7;

const int N=1e5+10;
int a[N];

void solve()
{
    int n;
    cin>>n;
    int ans=0;
    int val=0,l=1;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(a[i-1]>a[i])
        {
            val=max(val,a[i-1]-a[l]);
            l=i;
        }
    }
    val=max(val,a[n]-a[l]);
    
    l=1;
    for(int i=1;i<=n;i++)
    {
        if(a[i-1]>a[i])
        {
            if(a[i-1]-a[l]==val)
            {
                cout<<l<<" "<<i-1<<" ";
            }
            l=i;
        }
    }
    if(a[n]-a[l]==val)
    {
        cout<<l<<" "<<n<<" ";
    }cout<<endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}