次长上升子序列

题目描述
最长上升子序列是一道经典的题目,liu_runda很想在模拟赛中考考这个题目,但是他又不想被选手骂出原题,于是就把原题魔改一下再出出来.
对于一个数列a[1],a[2]…a[n], 我们定义子序列是一系列下标的集合: {x1,x2…xm}
其中, 1<=x1<x2<x3…<xm<=n
本题的上升子序列应满足a[x1]<=a[x2]<=a[x3]…<=a[xm], 也就是说, 我们考虑的是非严格的上升子序列(或者说,不下降子序列)
两个子序列不同, 当且仅当有一个下标被一个子序列包含却不被另一个子序列包含.
给出一个数列, 你需要找出所有非严格的上升子序列中第二长的子序列的长度. 它有可能比最长上升子序列短, 也有可能和最长上升子序列一样长.

输入
每个输入包含多组测试数据,第一行一个整数T表示测试数据的组数.
接下来每组数据第一行一个整数n, 表示数列的长度,第二行n个整数表示数列.

输出
T行, 第i行一个数字表示第i组输入的次长上升子序列长度
样例输入 Copy
5
10
10 1 8 10 2 6 4 1 5 4
10
8 2 6 1 6 8 10 3 7 4
10
1 8 7 9 9 6 10 3 2 2
10
5 4 8 2 2 2 2 9 3 3
10
8 4 9 7 6 9 10 3 7 3
样例输出 Copy
4
4
5
5
4
提示
100%的数据, T=5, 1<=ai<=100000，n≤100000问题 A: 次长上升子序列
时间限制: 1 Sec 内存限制: 128 MB
[提交] [状态]
题目描述
最长上升子序列是一道经典的题目,liu_runda很想在模拟赛中考考这个题目,但是他又不想被选手骂出原题,于是就把原题魔改一下再出出来.
对于一个数列a[1],a[2]…a[n], 我们定义子序列是一系列下标的集合: {x1,x2…xm}
其中, 1<=x1<x2<x3…<xm<=n
本题的上升子序列应满足a[x1]<=a[x2]<=a[x3]…<=a[xm], 也就是说, 我们考虑的是非严格的上升子序列(或者说,不下降子序列)
两个子序列不同, 当且仅当有一个下标被一个子序列包含却不被另一个子序列包含.
给出一个数列, 你需要找出所有非严格的上升子序列中第二长的子序列的长度. 它有可能比最长上升子序列短, 也有可能和最长上升子序列一样长.

输入
每个输入包含多组测试数据,第一行一个整数T表示测试数据的组数.
接下来每组数据第一行一个整数n, 表示数列的长度,第二行n个整数表示数列.

输出
T行, 第i行一个数字表示第i组输入的次长上升子序列长度
样例输入 Copy
5
10
10 1 8 10 2 6 4 1 5 4
10
8 2 6 1 6 8 10 3 7 4
10
1 8 7 9 9 6 10 3 2 2
10
5 4 8 2 2 2 2 9 3 3
10
8 4 9 7 6 9 10 3 7 3
样例输出 Copy
4
4
5
5
4
提示
100%的数据, T=5, 1<=ai<=100000，n≤100000问题 A: 次长上升子序列
时间限制: 1 Sec 内存限制: 128 MB
[提交] [状态]
题目描述
最长上升子序列是一道经典的题目,liu_runda很想在模拟赛中考考这个题目,但是他又不想被选手骂出原题,于是就把原题魔改一下再出出来.
对于一个数列a[1],a[2]…a[n], 我们定义子序列是一系列下标的集合: {x1,x2…xm}
其中, 1<=x1<x2<x3…<xm<=n
本题的上升子序列应满足a[x1]<=a[x2]<=a[x3]…<=a[xm], 也就是说, 我们考虑的是非严格的上升子序列(或者说,不下降子序列)
两个子序列不同, 当且仅当有一个下标被一个子序列包含却不被另一个子序列包含.
给出一个数列, 你需要找出所有非严格的上升子序列中第二长的子序列的长度. 它有可能比最长上升子序列短, 也有可能和最长上升子序列一样长.

输入
每个输入包含多组测试数据,第一行一个整数T表示测试数据的组数.
接下来每组数据第一行一个整数n, 表示数列的长度,第二行n个整数表示数列.

输出
T行, 第i行一个数字表示第i组输入的次长上升子序列长度
样例输入
5
10
10 1 8 10 2 6 4 1 5 4
10
8 2 6 1 6 8 10 3 7 4
10
1 8 7 9 9 6 10 3 2 2
10
5 4 8 2 2 2 2 9 3 3
10
8 4 9 7 6 9 10 3 7 3
样例输出
4
4
5
5
4
提示
100%的数据, T=5, 1<=ai<=100000，n≤100000

因为要找第二长的子序列， 所以先贪心dp一下最长的非严格上升子序列， 然后我们再求一下得出这个序列的方案数， 如果得出最长的子序列方案数大于1，那么答案就是最长的方案书序列长度， 不然的会就是最长长度减1

#pragma GCC optimize(3 , "Ofast" , "inline")
#include <bits/stdc++.h>
using namespace std ;
const int N = 1e5 + 10 ;
int dp[N] , a[N] , p[N] , now[N] ;
int main()
{
    int n ;
    int T ;
    cin >> T ;
    while(T --)
    {
        scanf("%d" , &n) ;
        for(int i = 1; i <= n ;i ++)  scanf("%d" , &a[i]) ;
        memset(dp , 0 , sizeof dp) , memset(now , 0 , sizeof now) ;
        memset(p , 0 , sizeof p) ;
        int cnt = 0 ;
        dp[++ cnt] = a[1] , p[1] = 1 ;
        for(int i = 2 ; i <= n ;i ++)
         {
             if(a[i] >= dp[cnt]) dp[++ cnt] = a[i] , p[i] = cnt ;
             else
              {
                    int pos = upper_bound(dp + 1 , dp + cnt + 1 , a[i]) - dp ;
                    if(a[i] >= dp[pos - 1]) p[i] = pos ;
                    else p[i] = 1 ;
                    dp[pos] = a[i] ;
                }
         }
         vector<int> v[N] ;
         int ans = 0 ;
         for(int i = 1; i <= n ;i ++)
          {
                if(p[i] == 1) now[i] ++ ;
                for(auto x : v[p[i] - 1])
                     if(a[i] >= a[x]) now[i] += now[x] ;
                if(p[i] == cnt) ans += now[i] ;
                if(ans > 1) break ;
                v[p[i]].push_back(i) ;
            }
            printf("%d\n" , cnt - (ans <= 1)) ;
    }

}