E - 小晴天老师系列——我有一个数列!

时间:2023-12-15 09:22:56

E - 小晴天老师系列——我有一个数列!

Time Limit: 20000/10000MS (Java/Others)    Memory Limit: 128000/64000KB (Java/Others)
Submit Status

Problem Description

小晴天:“我有一个数列!”

小晴天:“我还要有很多很多的数列!”

于是小晴天就把这个数列的所有连续子数列写出来。

然后小晴天把每个连续子数列中的最大的数写出来。

那么,有多少个比K大呢?

Input

多组数据,首先是一个正整数t(t<=100),表示数据的组数

对于每组数据,首先是两个整数n(1<=n<=200000),K(0<=K<=10^9).,但所有数据中的n之和不超过1000000.

接下来是n个整数a[i](1<=a[i]<=10^9)

Output

对于每组数据,输出一个整数,表示最大元素大于K的连续子序列的个数。

Sample Input

2
3 2
1 2 3
3 1
1 2 3

Sample Output

3
5

Hint

对于样例一,共有6个连续子序列{1}{2}{3}{1,2}{2,3}{1,2,3}(注意{1,3}不满足题意,因为不连续)

其中最大元素大于2的共有3个{3}{2,3}{1,2,3}

对于样例二,大于1的连续子序列共有5个,{2}{3}{1,2}{2,3}{1,2,3}

题意:

对于输入的每一个数列,计算该数列的每一个子序列中最大的元素大于所给定的数的个数.

(PS:刚开始还以为是计算的是不一样的子序列,结果后来才知道1212中前面{1,2}和后面的{1,2}算作是两个不同的子序列,不是算作同一个子序列囧囧囧.)

用DP[i]来保存的以i为结符合条件的子序列的最大数量,

所以符合条件的子序列=全部的DP[i]相加。

所以

if(Num[i]>K)

    DP[i]=i+1;

 else

    DP[i]=DP[i-1];

 #include <algorithm>
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
int Num[];
int DP[];
int main()
{
int T,i,j,SUM;
int Max,N,K,MAX,k;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&N,&Max);
for(i=,SUM=;i<N;i++)
{
DP[i]=; /*初始化DP[]*/
scanf("%d",&Num[i]);
}
for(i=;i<N;i++)
{
if(Num[i]>Max) /*符合条件的话*/
{
DP[i]=i+; /*最大数量等于他前面数的个数以及自己*/
}
else
{
DP[i]=DP[i-]; /*否则等于它前一个数的最大值*/
}
SUM+=DP[i]; /*计算总和*/
}
printf("%d\n",SUM); /*输出答案*/
}
return ;
}