Codeforces 466C Number of Ways(高效)

题目链接：Codeforces 466C Number of Ways

题目大意：给定一个序列，要求分成三段，每段和相同，问有多少种拆分方法。

解题思路：将所有前缀和为sum3的位置全部记录下来，然后在逐个计算后缀和，然后对应如果和为sum3，计算该位置前有多少个前缀和sum3。

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;
const int maxn = 5 * 1e5 + 5;

int n, arr[maxn];
ll s = 0;
vector<int> vec;

ll solve () {
    if (s % 3)
        return 0;

    s /= 3;
    ll p = 0, ret = 0;

    for (int i = 0; i < n; i++) {
        p += arr[i];
        if (p == s)
            vec.push_back(i);
    }

    p = 0;
    for (int i = n-1; i >= 0; i--) {
        p += arr[i];
        if (p == s)
            ret += lower_bound(vec.begin(), vec.end(), i-1) - vec.begin();
    }
    return ret;
}

int main () {
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
        s += arr[i];
    }
    printf("%lld\n", solve());
    return 0;
}