#### URAL 2060 – Subpalindrome pairs [Manacher+树状数组]

http://acm.timus.ru/problem.aspx?space=1&num=2060

### Problem

Your task is to calculate number of triplets (i, j, k) such that ij < k and s[i..j] is a palindrome and s[j+1 .. k] is a palindrome.

### Code

```#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 6 * 102400;
char s[maxn];
int len;
vector<int> ans;

struct BIT {
int dat[maxn];
void clear() {
memset(dat, 0, sizeof(dat));
}
int query(int pos) {
int s = 0;
for(int i = pos; i < maxn; i += (i&-i))
s += dat[i];
return s;
}
void addRange(int l, int r, int d) {
for(int i = r; i > 0; i -= (i&-i))
dat[i] += d;
for(int i = l-1; i > 0; i -= (i&-i))
dat[i] -= d;
}
}bitL, bitR;

void Manacher(const string & str, vector<int> &res) {
string t = "\$#";
for(auto i : str)
t.push_back(i), t.push_back('#');
res.resize(t.size(), 0);
int mx = 0, id = 0;
for(int i = 0; i < t.size(); ++i) {
res[i] = mx > i ? min(res[2*id-i], mx-i) : 1;
while(t[i+res[i]] == t[i-res[i]]) ++res[i];
if(i + res[i] > mx) {
mx = i + res[i];
id = i;
}
}
//    for(int i = 0; i < res.size(); ++i) {
//        printf("%d : %c : %d\n", i, t[i], res[i]);
//    }
bitL.clear(), bitR.clear();
for(int i = 1; i < res.size(); ++i) {
bitL.addRange(i - res[i] + 1, i, 1);
bitR.addRange(i, i + res[i] - 1, 1);
}
ll ans = 0;
for(int i = 3; i < res.size() - 1; ++i) {
if(t[i] == '#')
ans += (ll)bitR.query(i-1) * bitL.query(i+1);
}
printf("%lld\n", ans);
}

int main() {
scanf("%s", s);
len = strlen(s);
Manacher(s, ans);
return 0;
}
```