---
tags: 程式筆記
---

# [DP學習筆記2] Codeforces 1736C Good Subarrays (Easy Version)
> https://codeforces.com/contest/1736/problem/C1

## 題意
在一個整數序列 $a$ 中，有 $n$ 個數字（從$1$開始編號至$n$），如：`2 1 4 3`，我們想要找出有幾個好區間？

首先要定義區間，對於區間來說有兩個特徵，一個左邊界 $l$ ，一個右邊界 $r$ ($1 \le l \le r \le n$)，這兩個邊界代表 $[a_l, ..., a_r]$ 的整數序列，像是左邊界 $l = 2$，右邊界 $r = 4$，就代表 `1 4 3` 的整數序列。

接下來就是本題的重點了，好的區間是什麼？每個區間會對應到一個整數序列 $b$，這個 $b$ 中每個數字都要大於等於他的位置編號（$i \le b_i$），像是剛剛的 `1 4 3` 就是一個好的區間，因為 $1 \le 1, 2 \le 4, 3 \le 3$，但是像是區間 $l=1, r=2$ 對應到的序列為 `2 1`，這就不是一個好的區間，因為第二個數字為 $1$，位置編號大於數字。

$$
1 \le n \le 2 * 10^5 \\
1 \le a_i \le n
$$

**input**
`4`
`2 1 4 3`
**output**
`7`

**說明**
`[1,1], [2,2], [2,3], [2,4], [3,3], [3,4], [4,4]` 共 7 個好區間。

**備註**
$[l, r]$ 是閉區間的表示法。

## 思考

**前言**
我覺得直覺既美麗又飄渺，順著直覺走通常都會很開心，但是最困擾競技選手的就是直覺總是那麼無理取鬧，有時候哭有時笑，有時偏偏不來到，所以我認為一個好的 SOP 很重要，當有直覺的時候再回來思考當前的 SOP 是否有改進的必要。
（我是押韻大師 ^^）

首先盤點已知的線索與問題，遇到「區間」的問題時，有很高的機率區間與另一個區間有關聯，這個**關聯性往往是我們減少重複計算**的關鍵，然而減少重複計算的能力就是選手的核心能力之一，畢盡人類社會資源有限，使用最少的資源做最多的事情一直都是人類生存的課題～

**區間關聯尋找常用 SOP**
因為區間有兩個特徵，一個左邊界 $l$ ，一個右邊界 $r$，所以我們要來探討區間與區間之間的關聯，在探討區間與區間的關聯時，我們可以思考以下三種關聯，固定左變動右、固定右變動左或是固定長度變動左右。從這兩個特徵下去思考關聯會是很自然的思考流程。

**重返案發現場**
首先我們先整理題目中的線索
- 區間長度為 $1$ 的都是好區間，因為每個數字都大於等於 $1$。
- 好區間中，每個數字都要大於等於他的位置編號（$i \le b_i$）。
- 計算所有區間中，有幾組區間是好區間。

**辦案**
我想這時候我們需要重新詮釋第二點「好區間中，每個數字都要大於等於他的位置編號（$i \le b_i$）」，思考這句話跟左右邊界的關聯性，讓我們換句話說「包含數字 $x$ 的區間，在 $x$ 前面最多 $x - 1$ 個數字。(位置編號)」，赫然發現左邊界的極限被決定了！

那麼我們接下來我們可以套用「常見區間關聯」，左邊界動一下，右邊界換一下，區間長度變一下。

已知一個長度為 $k$ 的好區間，如果下一個數字大於等於 $k + 1$，那麼這 $k+1$ 個數字為新的好區間。

| 6 | 3 | 2 | 4 | 區間序列 |
|:-----------:| ----- |:-----:|:-----:|:-------- |
| | $l_2$ | $r_2$ | | _ 3 2 |
| $l_{r_3}$<- | <- | <- | $r_3$ | X X X 4 |
| | $l_3$ | | $r_3$ | _ 3 2 4 |

範例：已知 `3 2` 為好區間的區間序列，考慮下一個數字 `4`，因為大於等於 $3 = 2 + 1$，所以 `3 2 4` 為好區間。

已知一個長度為 $k$ 的好區間，如果下一個數字 $j$ 小於 $k + 1$，那麼這 $j$ 個數字為新的好區間。

| 6 | 3 | 2 | 2 | 區間序列 |
|:---:|:-----:|:-----------:|:-----:|:----------- |
| | $l_2$ | $r_2$ | | _ 3 2 |
| | | $l_{r_3}$<- | $r_3$ | _ _ X 2 |
| | | $l_3$ | $r_3$ | _ ~~3~~ 2 2 |

## 實作

void solve() {
	int n;
	cin >> n;
	vector<int> as(n);
	for(int i = 0; i < n; i++) cin >> as[i];
 
	vector<int> l(n, 0);
	for(int i = 1; i < n; i++) l[i] = max(l[i-1], i - (as[i] - 1));
 
	ll ans = 0;
	for(int i = 0; i < n; i++) ans += (i - l[i] + 1);
	cout << ans << '\n';
}

**Note**
L7: 對於每個數字的左極限座標，且最極限就是在數列的頭，所以初始化為 $0$。

L8: 由於 `as[i] - 1` 為前面最多放幾個數字，所以從 i 往前找座標，這裡不用擔心座標計算出負數，因為我們有初始化最極限為數列的頭，所以可以透過 max 避免掉存取到 `as[-5]` 這種案例。

L11: 為累計每個左極限下的區間數量，得到最終結果。