E. Group Photo 分类讨论

题目大意：

给出一个 (a_i) 数组，然后构造 (C) 和 (P) 序列，两个序列的合集是 (1) 到 (n) 的排列。然后 (C) 的排列对应的 (a) 的和要小于 (P) 对应的 (a) 的和，而且 (C) 序列相隔两个数的差值要递增，(P) 要递减。

题解：

(P..PC..C) 先是 (P) 后是 (C)
(CC..CP..CP..P) 先是连续的 (C) 然后是 (CP..CP) ，最后全部都是连续的 (P)
(CC..CP..CP..PC) 先是连续的 (C) 然后是 (CP..CP) ，然后是连续的 (P) 最后一个是 (C)
(PCC..CP..CP..P) 一开始是 (P) ，然后是连续的 (C) ，然后是 (CP..CP) 最后是连续的 (P)
(PCC..CP..CP..PC) 一开始是 (P) ，然后是连续的 (C) ，然后是 (CP..CP) ，然后是连续的 (P) ，最后是一个 (C)
因为第二种包含了 (C..CP..P) 所以不考虑 (CCCPPP)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
const int mod = 998244353;
typedef long long ll;
ll a[maxn],sum[maxn],all = 0;
ll solve(int x,int y,ll now) {
    if (now * 2 >= all || x > y) return 0;
    int l = 1, r = (y - x) / 2 + 1, ans = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (2 * (now + sum[x + 2 * (mid - 1)] - sum[x]) < all) ans = mid, l = mid + 1;
        else r = mid - 1;
    }
//    printf("x = %d y = %d now = %lld ans = %d
", x, y, now, ans);
    return ans;
}
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        all = 0;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &a[i]);
            sum[i] = a[i], all += a[i];
            if (i > 1) sum[i] += sum[i - 2];
        }
        ll ans = 0;
        for (int i = 1; i <= n; i++) {
            if (2 * (sum[i] + sum[i - 1]) > all) ans++;
        }
        for (int i = 1; i <= n; i++) {
            ll now = sum[i] + sum[i - 1];
            ans = (ans + solve(i, n - 1, now)) % mod;//CCC..CPCP..P
            now += a[n];
            ans = (ans + solve(i, n - 2, now)) % mod;//CC..CPCP..PC
            if (i > 1) {
                now -= a[1];
                ans = (ans + solve(i, n - 2, now)) % mod;//PCC..CPCP..PC
                now -= a[n];
                ans = (ans + solve(i, n - 1, now)) % mod;//PCC..CPCP..P
            }
        }
        printf("%lld
", ans);
    }
    return 0;
}
// PCPC PCPP PCCP