NlogN binary search, with explaination
we just need find two indexes x, y to make [0, x) ,[x, y), [y, n) satisified. 0 != x && x != y && and y != n\n\nwe have to do iteration from 1 to n - 1 for x, b
we just need find two indexes x, y to make [0, x) ,[x, y), [y, n) satisified. 0 != x && x != y && and y != n\n\nwe have to do iteration from 1 to n - 1 for x, but for y, we can use binary search\n\nwhen y is decided, we need to know how many y\'s in current x.\n\nwe need do another binary search\n\nfor example [1, 2, 2, 2, 5]\nwe know x = 1, y = 2, and sum1 = 1 sum2 = 2 sum3 = 9, and we know (9 - 2) / 2 = 3 we and move y NO bigger than 3\n\n```\nclass Solution {\npublic:\n    int waysToSplit(const vector<int>& nums) {\n        static const int mod = 1e9 + 7;\n        int n = nums.size(), res = 0;\n        vector<int> acc{0};\n        partial_sum(nums.begin(), nums.end(), back_inserter(acc));\n        for (int x = 1; x <= n - 2; ++x) {\n            int sum1 = acc[x] - acc.front();\n            int sum2low = acc[x] + sum1;\n            int y = lower_bound(acc.begin() + x, acc.end() - 1, sum2low) - acc.begin();\n            if (y == x && y < n) ++y;\n            int sum2 = acc[y] - acc[x];\n            int sum3 = acc.back() - acc[y];\n            if (sum3 < sum2) continue;\n            int range = (sum3 - sum2) / 2 + acc[y];\n            int lasty = upper_bound(acc.begin() + y, acc.end() - 1, range) - acc.begin();\n            res += lasty - y;\n            if (res >= mod) res -= mod;\n        }\n        return res;\n    }\n};\n```
[]