CF2004 EDU169 F. Make a Palindrome

首先考虑对于一个序列直接怎么 \(O(n)\) 求 \(f\) 值，就发现考虑维护两个指针 \(l,r\)，如果 \(a_l=a_r\)，则 \(l+1，r-1\)，否则我们就让小的那一个分裂，那么每次操作一定可以减少长度，所以最优。
然后就可以 \(O(n^3)\)，考虑换一种可优化的方式计算 \(f\)，通过猜想大概就是看一下前缀后缀集合有多少个不相等的数字。
发现能够过拍。

考虑优化，我们考虑枚举区间，区间的和为 \(val\)，且这个区间作为某个前缀，其左端点为 \(l\)，右端点为 \(r\)。
问题就是找有多少个 \(j(j\ge l)\) 满足：
\(\forall i(l\le i)~ s_{i,j} \ne val\)
于是我们考虑枚举了 \(l,r\) 之后看看有多少个 \(j\) 不满足条件即可。

然后发现某一个 \(j\) 所对应的 \(i\) 也一定只有至多一个满足 \(s_{i,j}=val\)。
问题就是问有多少个区间 \([i,j]\) 满足和 \(s_{i,j}=s_{l,r},(l\le i,r\le j)\)。
于是我们用 map 维护一个 int, vector<pair<int, int>> 表示值为 \(val\) 对应的区间。
然后按照左端点排序，对于每个区间看看它后面有多少个右端点大于它的右端点即可。
用树状数组维护。
时间复杂度：\(O(n^2\log n)\)。

Code:

#include <bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for (int i = (l); i <= (r); i++)
#define per(i,r,l) for (int i = (r); i >= (l); i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define maxn(a, b) a = max(a, b)
#define minn(a, b) a = min(a, b)
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
const ll mod = 998244353;
mt19937 gen(114514);
ll rp(ll a,ll b) {ll res=1%mod;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
template<class T>
struct BIT {
    vector<T> bit;
    int size;
    void init(int n) {
        bit.clear(); bit.resize(n + 1, 0);
        size = n;
    }
    void update(int x, T v) {
        assert(x);
        while (x <= size) {
            bit[x] += v;
            x += (x & -x);
        }
    }

    T query(int x) {
        assert(x <= size);
        T res = 0;
        while (x) {
            res += bit[x];
            x -= (x & -x);
        }
        return res;
    }

    int find(T k) {
        assert(k); k--;
        int x = 0;
        for (int i = log2(size); i >= 0; i--) {
            int y = x + (1 << i);
            if (y <= size && bit[y] <= k) {
                x = y;
                k -= bit[y];
            }
        }
        return x + 1;
    }
};
BIT<int> t;
const int N = 2043;
int n;
int a[N];
map<int, vector<PII>> p;

void solve() {
    // init();
    scanf("%d", &n);
    rep(i,1,n) scanf("%d", &a[i]);
    ll ans = 0;

    p.clear();
    per(i,n,1) {
    	int sum = 0;
    	rep(j,i,n) {
    		sum += a[j];
    		p[sum].eb(i, j);
    	}
    }
    for (auto [val, ve] : p) {
        t.init(n);
        // cout << "val: " << val << endl;
    	for (auto [l, r] : ve) {
            ans += n - r - t.query(n - r + 1);
            // cout << l << ' ' << r << endl;
            t.update(n - r + 1, 1);
    	}
        // cout << ans << endl;
    }
    printf("%lld\n", ans);
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--)
        solve();
    return 0;
}