Short Palindrome[HackerRank]

Short Palindrome

• 题目大意：

  给字符串 S(1<=length(S)<=1e6) ,全由小宝字母组成，求出有多少对 (a,b,c,d)(a<b<c<d) 满足 Sa==SdandSb==Sc .

• 解法：

  由于只有26种字母，并不多，我们可以枚举字母来处理，假设现在枚举 Sa==Sd=′a′andSb==Sc=′b′ 我们定义：

  • A数组表示字母 Sa 出现的位置，在哪个位置出现，就计数加1
  • B数组表示字母 Sb 出现的位置p，并且前面的 Sa 的数量，假设 S100==′b′ , (∑99i=1Si==′a′)==50 那么数组 B100==50

现在来枚举’b’的所有位置p，则：

result+=(∑i=1p−1Bi)∗(∑j=p+11e6Sj==′a′)

这表示位置p左边的ab对，乘以右边的位置d，也就是说我们枚举的是c。

上面乘号两边，都可以利用树状数组来 O(log) 的时间内算出。

代码：

#include <bits/stdc++.h>

typedef long long LLONG;
typedef std::vector<int> VI;

const int N =  + ;
const LLONG MOD =  + ;

char s[N];
LLONG a[N];
LLONG b[N];
VI idxSet[];

inline void add(LLONG& rlt, LLONG av) {
    rlt += av;
    if (rlt >= MOD)
        rlt %= MOD;
}

inline int lowBit(int k) { return k & -k;}

inline void update(LLONG x[], int p, LLONG v) {
    for (; p < N; p += lowBit(p)) {
        x[p] += v;
    }
}

inline LLONG query(LLONG x[], int l, int r) {
    LLONG rlt = ;
    for (; r; r -= lowBit(r))
        rlt += x[r];
    for (--l; l > ; l -= lowBit(l))
        rlt -= x[l];
    return rlt;
}

int main() {
    int t;
    scanf("%s", s);
    for (int i = ; s[i]; ++i) {
        int idx = s[i] - 'a';
        idxSet[idx].push_back(i + );
    }
    LLONG rlt = ;
    for (int i = ; i < ; ++i) {
        for (int j = ; j < (int)idxSet[i].size(); ++j) {
            update(a, idxSet[i][j], L);
        }
        for (int j = ; j < ; ++j) {
            for (int k = ; k < (int)idxSet[j].size(); ++k) {
                int p = idxSet[j][k];
                LLONG vv = query(a, p + , N - );
                LLONG vvv = query(b, , p - );
                add(rlt, vv * vvv);

                LLONG v = query(a, , p - );
                update(b, p, v);
            }
            for (int k = ; k < (int)idxSet[j].size(); ++k) {
                int p = idxSet[j][k];
                LLONG v = query(a, , p - );
                update(b, p, -v);
            }
        }
        for (int j = ; j < (int)idxSet[i].size(); ++j) {
            update(a, idxSet[i][j], -);
        }
    }
    printf("%lld\n", rlt);
    return ;
}