---
# System prepended metadata

title: '競程練題 #2 題解'

---

# 競程練題 #2 題解

## Problem F - Good Subarrays
題目要找有幾對$[l, r]$，符合$\sum_{i=l}^r a_i=𝑟−𝑙+1$
1. by royyaha
    上面的的等式，可以改用$Prefix Sum$表示
    這邊用符號$S$代替$Prefix Sum$
    $S_r - S_{l-1} = r-l+1, l <= r$
    由這個等式直接枚舉$[l, r]$，看有幾組符合，需要用$O(n^2)$的時間
    
    這邊就想到一個方法：把和$l$有關的都放到左式，$r$有關的都放到右式
    $S_{l-1}-l  + 1 = S_r - r, l <= r$
    我們遍歷l的時候，可以直接紀錄$f(l)=S_{l-1}-l+1=?$的數量
    ``` cpp
    map<int, long long> mp; 
    // (key, value) = (f(l), f(l)這個值的出現次數)
    for(int i = 1; i <= n; i++) {
        mp[prefix_sum[i-1]-i+1]++; // 累計f(l)的值
    }
    ```
    > 注意出現次數可以能很大，要開long long
    
    完整code
    ``` cpp
    #include <bits/stdc++.h>
    using namespace std;

    void solve() {
        int n;
        cin >> n;
        vector<int> v(n+1), prefix_sum(n+1);
        for(int i = 1; i <= n; i++) { // 注意我這邊適用1-index，方便處理前綴
            char c;
            cin >> c;
            v[i] = c - '0';
        }

        for(int i = 1; i <= n; i++) {
            prefix_sum[i] = prefix_sum[i-1] + v[i];
        }

        map<int, long long> mp;
        long long ans = 0;
        for(int i = 1; i <= n; i++) {
            mp[prefix_sum[i-1]-i+1]++; // 累計f(l)的值
            ans += mp[prefix_sum[i]-i]; // 查詢有幾個=S_r-r
        }
        cout << ans << endl;
    }

    int main() {
        int t;
        cin >> t;
        while(t--) {
            solve();
        }
    }
    ```