当前位置：首页 > article >正文

C1. Good Subarrays (Easy Version)

article 2025/2/27 2:47:10

思路：我们枚举每一个左端点，对于每一个左端点，寻找最长的满足条件的区间，这个区间长度就是左端点对答案的贡献，可以发现具有单调性，右端点只会前进不会倒退。所以我们两个指针各扫一遍区间就可以。

#include <bits/stdc++.h> 
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define ll long long
#define db double
#define ull unsigned long long
#define endl '\n'
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 2e5 + 10;
int t, a[N];
 
 
void solve()
{
	int n; cin >> n;
	ll ans = 0;
	for(int i = 1; i <= n; ++ i)	cin >> a[i];
	for(int l = 1, r = 1; l <= n; ++ l)
	{
		while(r <= n && a[r] >= r - l + 1)	++ r;
		-- r;
		ans += (r - l + 1);
	}
	cout << ans << endl;
}
 
 
int main()
{
	io
//	freopen("1.in", "r", stdin);
	cin >> t;
	while(t --)	
	solve(); 
	return 0;
}