序列计数

序列计数

描述

给定一个n 个整数的序列以及一个非负整数 d，请你输出这个序列中有多少个连续子序列

（长度大于 1），满足该子序列的最大值最小值之差不大于 d。连续子序列：序列 1 2 3 中长度大于 1 的连续子序列有：

输入

第一行包含两个整数 n,d。接下来一行包含n 个整数。

输

输出一个整数，表示满足条件的连续子序列个数。

样例 1 输入

样例 1 输

样例 1 解释

满足条件的连续子序列有：

样例 2

请查看下发文件内的 sample2_input.txt 和 sample2_output.txt。

限制

对于 60%的数据，n ≤ 5000；

对于 100%的数据，n ≤ 300000。

保证所有整数的绝对值不超过 10^9，d 不超过 2×10^9。时间：10 sec

空间：512 MB

提示

[考虑分治。]

[令函数 solve(l, r)表示统计[l, r]中合法的连续子序列个数，mid 为(l+r)/2（下取整），那么] [solve(l, r) = 0, 当 l = r]

[solve(l, r) = solve(l, mid) + solve(mid + 1, r) + cal(l, r, mid)，当 l≠r]

[其中 cal(l, r, mid)表示在左端点在区间[l, mid]中、右端点在区间[mid + 1, r]中的符合要求的连续子序列数目]

[那么答案就是 solve(1, n)。]

[至于 cal(l, r, mid)怎么算，大家可以仔细思考思考。（右端点是有单调性的）]

[**注意答案要用 long long**]

[（另外这题也可以用线性的方法做哦~有兴趣去搜一搜单调栈）]

代码

#include <iostream> #include<vector> #include<stack> #include<algorithm>

#pragma warning(disable:4996) typedef long long ll;

using namespace std;

// ================= 代码实现开始 =================

/* 请在这里定义你需要的全局变量 */ const int N = 300005;

//n:题目中的n

//d:题目中的d

//max_value:用于存储solve函数中的最大值

//min_value:用于存储solve函数中的最小值

//a:题目中的a

int n, d, max_value[N], min_value[N]; vector<int> a;

//分治计算区间[l,r]中有多少连续子序列满足最大值最小值之差不大于d

//l:区间左边界

//r:区间右边界

//返回值:满足条件的连续子序列的个数ll solve(int l, int r)

{

if (l == r)//边界情况。我们不计算长度等于1的连续子序列,故返回0

return 0;

int mid = (l + r) / 2;//获得区间中点

ll ans = solve(l, mid) + solve(mid + 1, r);//递归，分治地求出左右两半的值，并累加

//我们计算区间[mid+1,r]的前缀最小值和前缀最大值，也就是说min_value[i]=min(a[mid+1,mid+2,..,i]),max同理

for (int i = mid + 1; i <= r; ++i)

{

min_value[i] = (i == mid + 1) ? a[i] : min(min_value[i - 1], a[i]);

max_value[i] = (i == mid + 1) ? a[i] : max(max_value[i - 1], a[i]);

}

//我们倒序枚举子序列的左端点i,i的取值范围在[l,mid]

//pos表示若连续子序列的左端点是i,那么子序列的右端点最远能拓展到pos位置，当然pos取值范围在[mid+1,r]，一开始初始化为r

//mn是后缀最小值,mx是后缀最大值，也就是说mn=min(a[i,...,mid]),mx同理

//那么以i为左端点的连续子序列(右端点在[mid+1,r]内)个数应该有pos-mid个

int mn = 0, mx = 0, pos = r;

for (int i = mid; i >= l && pos > mid; --i)

{

min_value[i] = (i == mid) ? a[i] : min(min_value[i + 1], a[i]);

mn = min_value[i];

max_value[i] = (i == mid) ? a[i] : max(max_value[i + 1], a[i]);

mx = max_value[i];

for (; pos > mid&&max(mx, max_value[pos]) - min(mn, min_value[pos]) > d; -- pos);//pos随着i的递减也递减(注意此处for循环无执行语句)

ans += pos - mid;//相当于求左端点在区间[l,mid]、右端点在区间[mid + 1, r]中的符合要求的连续子序列数目

                 //注意此处不是为pos-i的原因是在上面的ll ans = solve(l, mid) + solve(mid + 1, r);中已经获得了mid左边至i的子序列数目，故此时只需要加上mid右边至pos的子序列数目即可得到上一行注释中的连续子序列数目

}

return ans;

}

// 求出有多少个a数组中的连续子序列（长度大于1），满足该子序列的最大值最小值之差不大于d

// n：a数组的长度

// d：所给d

// a：数组a，长度为n

// 返回值：满足条件的连续子序列的个数

long long getAnswer(int n, int d, vector<int> a) {

::n = n;

::d = d;

::a = a;

return solve(0, n - 1);

/* 请在这里设计你的算法 */

}

// ================= 代码实现结束 =================

int main() {

scanf("%d%d", &n, &d);

a.resize(n);

for (int i = 0; i < n; ++i)

scanf("%d", &a[i]);

printf("%lld\n", getAnswer(n, d, a));

return 0;

}