截断数组

题目描述：

给定长度为n的数组，现在要将数组分成三段连续的非空子数组，使得三段非空子数组的元素和都相等，问存在多少种划分方法

思路：

设n个数字的数字和为sum，前缀和数组是sum[i]

首先可以发现三段元素和相同，代表sum一定是3的倍数，没一顿数字和一定是sum/3

所以问题其实可以转化成，问存在多少对(i,j)使得 \sum_{id=1}^{id<=i}{ar[id]} = \sum_{id=i+1}^{id<=j}{ar[id]} = \sum_{id=j+1}^{id<=n}{ar[id]} = sum/3

最暴力的方法是同时枚举(i, j)，不过这样会超时

其实我们只需要枚举满足sum[i] = sum[n]/3的所有i，然后通过某种O(1)的方法求出i<j<n中存在多少个下标j，使得sum[j] = 2 * (sum/3)，而sum/3 = sum[i],也就是需要O(1)获得sum[j] = 2 * sum[i]的j的数量

由于需要求的j的数量是从i+1到n，所以我们需要逆序维护，为了简单一点我们可以用map直接维护，当然也可以用一个变量num来记录

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define io ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define m_p(a, b) make_pair(a, b)
typedef long long ll;
typedef pair<int, int> pii;
#define MAX 100005
#define mod 1000000007
int n, m, x, k, y;
int tr[MAX];
int sum[MAX];

void work(){
	cin >> n;
	for(int i = 1; i <= n; ++i)cin >> tr[i], sum[i] = sum[i - 1] + tr[i];
	map<int,int>mp;
	mp[sum[n-1]]++;
	ll ans = 0;
	for(int i = n - 2; i >= 1; --i){
		if(sum[n] == 3 * sum[i]){
			ans += mp[sum[i] * 2];
		}
		++mp[sum[i]];
	}
	cout << ans << endl;
}

int main(){
	io;
	work();
	return 0;
}