# 競程練題 #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=?$的數量

    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

    #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();
        }
    }