Description
Given a sequence of N numbers.
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
Consecutive means continuous, all elements in the subsequence should be continuous in the original sequence.
For example, if the given sequence is {3, 4, 5},
then all possible consecutive subsequences are {3}, {3, 4}, {3, 4, 5}, {4}, {4, 5}, {5}.
A "Stabled Consecutive Subsequence" is a consecutive subsequence that the "maximum value in the subsequence" minus the "minimum value in the subsequence" is less than or equal to a given number K.
Your goal is to find the number of "Stabled Consecutive Subsequences".
ouo.
Some useful hints left by ouo:
0. As the right bound increases, the available left bound is non-decreasing.
1. The O(N2) solution, you can enumerate the right bound(枚舉右邊界) of your subsequence, and try to find how far you can reach the left bound.
2. The O(Nlog2N) solution, still enumerate the right bound of your subsequence, use std::set to maintain the left bound.
3. The O(N) solution, still enumerate the right bound, use 2 "std::deque" (note, deque stands for double-end queue), to maintain an increasing sequence and a decreasing sequence, both should end up with your current right bound. Use these 2 double-end queues to maintain the left bound.
4. The last 2 test cases are large, so use scanf instead of cin, the speed will be 2 times faster. Or if you really want to use cin, cout, then try to add "ios::sync_with_stdio(false); cin.tie(nullptr);" to your code, these 2 lines will make your input output speed up 2 times faster. Note that if you add these 2 lines, then you cannot use scanf, printf anymore.
Further explanation about the usage of std::deque:
Declaration: `deque<int> dq;`
Add a value to the back of the deque: `dq.push_back(value);` O(1)
Add a value to the front of the deque: `dq.push_front(value);` O(1)
Remove a value from the back of the deque: `dq.pop_back();` O(1)
Remove a value from the front of the deque: `dq.pop_front();` O(1)
Get the first value of the deque: `dq.front();` O(1)
Get the last value of the deque: `dq.back();` O(1)
Check if the deque is empty: `dq.empty();` O(1)
For Sample Input 1,
N = 5, K = 2, the sequence is {10, 9, 8, 6, 9},
then all possible Stabled Consecutive Subsequences are {10}, {10, 9}, {10, 9, 8}, {9}, {9, 8}, {8}, {8, 6}, {6}, {9}.
So the answer is 9.
For Sample Input 2,
N = 6, K = 3, the sequence is {7, 5, 8, 6, 11, 13},
then all possible Stabled Consecutive Subsequences are {7}, {7, 5}, {7, 5, 8}, {7, 5, 8, 6}, {5}, {5, 8}, {5, 8, 6}, {8}, {8, 6}, {6}, {11}, {11, 13}, {13}.
So the answer is 13.
Input
There are 2 numbers N, K in the first line, separated by the space character.
There are N numbers Ai in the second line, separated by the space characters.
There are 12 test cases in this problem:
For all test cases, it is guaranteed that:
1 <= N <= 107,
1 <= K <= 109,
1 <= Ai <= 109,
and all numbers in the sequence are unique.
For test cases 1 ~ 3,
1 <= N <= 500, that is, time complexity O(N3) will pass these cases.
For test cases 4 ~ 6,
1 <= N <= 5000, that is, time complexity O(N2) will pass these cases.
For test cases 7 ~ 10,
1 <= N <= 500000, that is, time complexity O(Nlog2N) will pass these cases.
For test cases 11 ~ 12,
1 <= N <= 107, that is, time complexity O(N) will pass these cases.
Output
Output contains only 1 line.
Output the number of "Stabled Consecutive Subsequences" with the given N, K numbers and sequence, with a newline character.
Note that the answer is in the range of [0, 262].
Tags