提出 #74308823

---

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int MAXN = 100;  // fib[100] > 1e18
string x, y;
int q, l1, l2;
int fib[MAXN];
int cnt[MAXN][30];  // cnt[n][c] = S_n中字符c的总数

// 预计算
void precompute() {
    fib[1] = l1;
    fib[2] = l2;
    
    for (int i = 3; i < MAXN; i++) {
        if (fib[i-1] > 2e18) {
            fib[i] = 2e18;
        } else {
            fib[i] = fib[i-1] + fib[i-2];
        }
    }
    
    // 计算S1
    for (int c = 1; c <= 26; c++) cnt[1][c] = 0;
    for (char ch : x) {
        if (ch >= 'a' && ch <= 'z') {
            cnt[1][ch - 'a' + 1]++;
        }
    }
    
    // 计算S2
    for (int c = 1; c <= 26; c++) cnt[2][c] = 0;
    for (char ch : y) {
        if (ch >= 'a' && ch <= 'z') {
            cnt[2][ch - 'a' + 1]++;
        }
    }
    
    for (int i = 3; i < MAXN; i++) {
        for (int c = 1; c <= 26; c++) {
            cnt[i][c] = cnt[i-1][c] + cnt[i-2][c];
        }
    }
}

// 优化的查询函数，避免重复计算
int query_optimized(int n, int len, int c) {
    if (len <= 0) return 0;
    
    int result = 0;
    int cur_n = n;
    int cur_len = len;
    
    while (cur_len > 0 && cur_n > 2) {
        if (cur_len <= fib[cur_n-1]) {
            // 全部在S_{n-1}中
            cur_n--;
        } else {
            // 包含S_{n-1}的全部
            result += cnt[cur_n-1][c];
            cur_len -= fib[cur_n-1];
            cur_n -= 2;
        }
    }
    
    // 处理S1或S2
    if (cur_n == 1 && cur_len > 0) {
        int l = min(cur_len, l1);
        for (int i = 0; i < l; i++) {
            if (x[i] - 'a' + 1 == c) result++;
        }
    } else if (cur_n == 2 && cur_len > 0) {
        int l = min(cur_len, l2);
        for (int i = 0; i < l; i++) {
            if (y[i] - 'a' + 1 == c) result++;
        }
    }
    
    return result;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    cin >> x >> y >> q;
    l1 = x.size();
    l2 = y.size();
    
    precompute();
    
    // 预计算S1和S2中每个位置的前缀字符计数
    vector<vector<int>> pre1(l1+1, vector<int>(27, 0));
    vector<vector<int>> pre2(l2+1, vector<int>(27, 0));
    
    for (int i = 1; i <= l1; i++) {
        for (int c = 1; c <= 26; c++) pre1[i][c] = pre1[i-1][c];
        pre1[i][x[i-1] - 'a' + 1]++;
    }
    
    for (int i = 1; i <= l2; i++) {
        for (int c = 1; c <= 26; c++) pre2[i][c] = pre2[i-1][c];
        pre2[i][y[i-1] - 'a' + 1]++;
    }
    
    while (q--) {
        int ql, qr;
        char ch;
        cin >> ql >> qr >> ch;
        int c = ch - 'a' + 1;
        
        // 找到n使得fib[n] >= qr
        int n = 1;
        while (n < MAXN && fib[n] < qr) n++;
        if (n >= MAXN) n = MAXN - 1;
        
        // 计算前缀和
        int ans_r = 0, ans_l = 0;
        
        // 计算[1, qr]
        int cur_n = n, cur_len = qr;
        while (cur_len > 0 && cur_n > 2) {
            if (cur_len <= fib[cur_n-1]) {
                cur_n--;
            } else {
                ans_r += cnt[cur_n-1][c];
                cur_len -= fib[cur_n-1];
                cur_n -= 2;
            }
        }
        if (cur_n == 1 && cur_len > 0) {
            ans_r += pre1[min(cur_len, l1)][c];
        } else if (cur_n == 2 && cur_len > 0) {
            ans_r += pre2[min(cur_len, l2)][c];
        }
        
        // 计算[1, ql-1]
        cur_n = n; cur_len = ql - 1;
        while (cur_len > 0 && cur_n > 2) {
            if (cur_len <= fib[cur_n-1]) {
                cur_n--;
            } else {
                ans_l += cnt[cur_n-1][c];
                cur_len -= fib[cur_n-1];
                cur_n -= 2;
            }
        }
        if (cur_n == 1 && cur_len > 0) {
            ans_l += pre1[min(cur_len, l1)][c];
        } else if (cur_n == 2 && cur_len > 0) {
            ans_l += pre2[min(cur_len, l2)][c];
        }
        
        cout << ans_r - ans_l << "\n";
    }
    
    return 0;
}

提出情報

ジャッジ結果