今日学习记录
1. 3748. 统计稳定子数组的数目
关键词：前缀和 二分
问题分析：
找到单调递增的子序列数量,给出数组进行 n 次区段查询
核心思路:
可以分区段讨论,每个区段内的满足条件的子序列数量是固定的,所以可以提前算出每个递增区段的数量,可以分为三个区段计算
当查询都在同一个区间的时候,直接计算 r-l+1 长度的子序列数量
当查询在不同的区间时计算[l,第一个递减点]和[最后一个递减点,r]中间的就是固定的区间和,所以左右端点要单独处理,发现我们要记录的其实都是递减,所以我们只用记录左端点就行了,中间的区间已经计算过了,所以没必要再记录右端点
每次使用二分搜索查询上下界一样
**最终代码：
typedef long long ll;
class Solution {
public:
vector<long long> countStableSubarrays(vector<int>& nums, vector<vector<int>>& queries) {
int n = nums.size();
vector<ll> left,sums = {0};
int start = 0;
for(int i = 0;i<n;i++){
int x = nums[i];
//i==n-1,把最后一个区段的开头装进去
if(i==n-1||x>nums[i+1]){
left.push_back(start);
ll m = i-start+1;
sums.push_back(sums.back()+m*(m+1)/2);
start = i+1;
}
}
vector<ll> ans;
for(auto &q:queries){
int l = q[0],r = q[1];
int i = ranges::upper_bound(left,l)-left.begin();
int j = ranges::upper_bound(left,r)-left.begin();
//一个区段中
j--;
if(i>j){
ll m = r-l+1;
ans.push_back(m*(m+1)/2);
}
else{
//不同区段
ll m = left[i] - l;
ll m2 = r-left[j]+1;
ans.push_back(m*(m+1)/2+(sums[j]-sums[i])+m2*(m2+1)/2);
}
}
return ans;
}
};学到的点：
- 二分查找