Jesselrj's Blog

CF1944D - Non-Palindromic Substring

题意：称一个字符串为$k$-good字符串，当该字符串至少有一个长度为$k$的子串不是回文串。给定一个字符串，询问$[l, r]$子串的$\sum{k}$

通过模拟可以发现对于一个字符串：

1. 不是回文串，则$k$可以取$2 \sim len$中的每一个值。

2. 每个字符都相同，则答案为$0$。

3. 是交错型的字符串，则$k$可以取$2 \sim len$中的每一个偶数。

4. 只是回文串，则$k$可以取$2 \sim {len - 1}$中的每一个值。

   判断回文串使用了双Hash（好久没用过了，写一个规范点的出来用）

#include <bits/stdc++.h>
#include <chrono>
#include <random>
using namespace std;

const int N = 200010;
namespace RAND {
    unsigned int SEED() {
        auto now = chrono::system_clock::now();
        auto timestamp = chrono::duration_cast<chrono::milliseconds>(now.time_since_epoch());
        return static_cast<unsigned int>(timestamp.count());
    }
    mt19937 R(SEED());
} // namespace RAND

unsigned long long mod1 = RAND::R(), mod2 = RAND::R();
class HASH {
    typedef unsigned long long ull;
    typedef pair<ull, ull> pULL;
public:
    ull base, pow1[N], pow2[N];
    vector<ull> hash1, hash2;
    HASH() {
        base = 27;
        pow1[0] = pow2[0] = 1;
        for (int i = 1; i < N; ++i) {
            pow1[i] = (pow1[i - 1] * base) % mod1;
            pow2[i] = (pow2[i - 1] * base) % mod2;
        }
    }
    // 默认字符串从1开始
    void init(string s) {
        int len = s.size() - 1;
        hash1.reserve(s.size()), hash2.reserve(s.size());
        hash1[0] = hash2[0] = 0;
        for (int i = 1; i <= len; ++i) {
            hash1[i] = (hash1[i - 1] * base + s[i] - 'a') % mod1;
            hash2[i] = (hash2[i - 1] * base + s[i] - 'a') % mod2;
        }
    }
    pULL subHash(int l, int r) {
        if (l == 1) return make_pair(hash1[r], hash2[r]);
        pULL tmp;
        tmp.first = (hash1[r] - hash1[l - 1] * pow1[r - l + 1] % mod1 + mod1) % mod1;
        tmp.second = (hash2[r] - hash2[l - 1] * pow2[r - l + 1] % mod2 + mod2) % mod2;
        return tmp;
    }
} hashFront, hashBack;

int n, q;
string s;
void work() {
    cin >> n >> q;
    cin >> s;
    hashFront.init(" " + s);
    reverse(s.begin(), s.end());
    hashBack.init(" " + s);
    reverse(s.begin(), s.end());
    int len = s.size();
    s = " " + s;
    unsigned long long ans, L;
    vector<int> id(n + 1); // 判断交错
    id[1] = 1, id[2] = 2;
    for (int i = 3; i <= len; i++) {
        if (s[i] == s[i - 2]) id[i] = id[i - 2];
        else id[i] = i;
    }
    vector<int> con(n + 1); // 判断连续
    con[1] = 1;
    for (int i = 2; i <= len; i++) {
        if (s[i] == s[i - 1]) con[i] = con[i - 1];
        else con[i] = i;
    }
    for (int i = 1, l, r; i <= q; ++i) {
        cin >> l >> r;
        L = (r - l + 1);
        if (L == 1) {
            cout << "0\n";
            continue;
        }
        if (L == 2) {
            if (s[l] == s[r]) cout << "0\n";
            else cout << "2\n";
            continue;
        }
        auto x1 = hashFront.subHash(l, r);
        auto x2 = hashBack.subHash(len - r + 1, len - l + 1);
        if (x1 == x2) {
            bool flag = 1;
            if (con[r] == con[l]) {
                cout << 0 << '\n';
                continue;
            }
            if (id[l] == id[r] && id[l + 1] == id[r - 1]) {
                unsigned long long tmp = (L / 2) * 2;
                ans = (2 + tmp) * (L / 2) / 2;
            } else {
                ans = (1 + L - 1) * (L - 1) / 2 - 1;
            }
        } else {
            if (id[l] == id[r - 1] && id[l + 1] == id[r]) {
                ans = (2 + L) * L / 4;
            } else ans = (2 + L) * (L - 1) / 2;
        }
        cout << ans << '\n';
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--)
        work();
    return 0;
}