ABC290E回文串分类讨论计数STL

#include <bits/stdc++.h>
using namespace std;
int n, m, i, j, k;
long long ans, c;
multiset <int> s[200050];
multiset <int> :: iterator p;
int main(){
    scanf("%d", &n);
    for(i=1; i<=n; i++){
        scanf("%d", &k);
        s[k].insert(min(i, n-i+1));//离边界的距离、数量
        ans += (i>>1) * (n-i+1ll);//累加长度i字符串修改次数
    }//假设各不相同，每个串有一半字符需要修改
    for(i=1; i<=n; i++){
        c = s[i].size();
        for(p=s[i].begin(); p!=s[i].end(); p++){
            ans -= *p * --c;
        }//任意两个相同则不需要修改，减回去
    }//这两个相同的，被多少个回文串包含？取决于谁先到左右边界
    printf("%lld\n", ans);
    return 0;
}