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}
思路：ST算法可以解决。用 O(n*n)枚举每个区间，用ST算法在O(1)找到每个区间的最大再与k比较。
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N=;
int a[N], cur;
int big[N][], small[N][]; void pre_cal(int n)
{
memset(big,,sizeof(big));
memset(small,,sizeof(small)); for(int i=; i<=n; i++)
{
big[i][]=a[i];
small[i][]=a[i];
} for(int i=,q=; i<=n; i<<=,q++) //以i为距离
{ for(int j=; j<=n; j++ )
{
if(j+i-<=n)
{
big[j][q]=max(big[j][q-],big[ j+i/ ][q-]);
small[j][q]=min(small[j][q-],small[ j+i/ ][q-]);
}
else break;
}
}
} unordered_map<int,int> mapp,mapp2;
void init() //获得二进制最高位，这个也可以先处理的。
{
for(int j=; j<=N; j++)
{
int tmp=, cnt=;
for(int i=; i<; i++)//找出二进制最高位的1
{
if(!(j>>i))
{
tmp=((j>>(i-))<<(i-));
break;
}
cnt++;
}
mapp2[j]=tmp;//记录j只剩最高位的值
mapp[j]=cnt;//记录tmp是2的几次幂
}
} bool iscor(int l, int r) //判断这个区间是否满足要求
{
int len=r-l+;
int da= max( big[l][ mapp[len] ], big[ r-mapp2[len]+ ][ mapp[len] ]);
int xiao=min( small[l][ mapp[len] ], small[ r-mapp2[len]+ ][ mapp[len] ]);
return da-xiao<cur? true :false; } int main(void)
{
freopen("e://input.txt", "r", stdin);
int t, n;
init();
cin>>t;
while(t--)
{
scanf("%d%d",&n,&cur);
for(int i=; i<=n; i++) scanf("%d",&a[i]);
pre_cal(n);
LL cnt=;
int l=, r=;
while(r<=n)
{
if( iscor(l,r) ) r++;
else
{
cnt+=r-l;
l++;
}
}
while(l<r) cnt+=r-l,l++;
printf("%lld\n",cnt);
}
return ;
}
AC代码
