P6416 题解-526互联

省流：离线以后，每个字符做前缀和然后直接水过去

首先离线所有询问。对于每个英文字母，我们把查询这个字母的询问都一起处理。
对于每个字母 \(c\)，我们跑一遍前缀和，令 \(p_i\) 表示 \(\mathit{s}_{1,i}\) 中字符 \(c\) 出现的次数。接下来我们定义 \(\operatorname{f}(i,l,r)\) 为 \(\mathit{s}_{l,r}\) 中字符 \(i\) 出现的次数。
对于每次询问:
首先求出第 \(a_i\) 行的第一个字符是什么，这等价于求前 \(a_i-1\) 行的元素个数加一再对字符串长度取模。注意到 \(n\) 在 long long 范围内，因此我们采取下面的函数计算首个字符 \(p\)。

long long getP(long long r) {
    if (r & 1) {
        return r % m * (((r + 1) >> 1) % m) % m;
    } else {
        return (r >> 1) % m * ((r + 1) % m) % m;
    }
}

接下来对询问的长度进行分讨。
要么这行一直到最后都和 \(p\) 在同一字符串循环里，那么答案显然是 \(\operatorname{f}(p, p + a_i - 1)\)。
要么我们可以把第 \(a_i\) 行分成三部分：前面的散块，中间的若干整块和后面的散块。此时分别处理并相加，不难得出 \(\operatorname{query}(a_i,c_i)\) 可以被写成 \(\operatorname{f}(c_i,\;p,\;len - 1) + \operatorname{f}(c_i,\;0,\;len - 1) \times (\frac{a_i-len-p}{len})+[len\bmod m\not= 0]\times\operatorname{f}(c_i,0,(a_i-p) \bmod m)\)。

上面的公式看起来很复杂，其实就是三块分别加起来

综合上述，我们可以得出此题的完整代码如下。

#include <bits/stdc++.h>

using namespace std;

const int maxM = 1000000;
const int maxK = 50000;

struct query {
    long long row;
    int id;
    query(long long row = 0, int id = 0) : row(row), id(id) {}
};

long long n, m, k, a, ans[maxK];
char w[maxM + 1];
int p[maxM];
vector<query> Q[26];

long long getP(long long r) {
    if (r & 1) {
        return r % m * (((r + 1) >> 1) % m) % m;
    } else {
        return (r >> 1) % m * ((r + 1) % m) % m;
    }
}

int f(int p1, int p2) {
    return p[p2] - (p1 != 0 ? p[p1 - 1] : 0);
}

long long solve(long long r) {
    int p = getP(r - 1);
    long long ans = 0, len = r - (m - p);
    if (p + r <= m)
        return f(p, p + r - 1);
    ans = f(p, m - 1) + f(0, m - 1) * (len / m);
    return ans + (!!(len % m)) * f(0, len % m - 1);
}
char c;
int main() {
    scanf("%d", &n);scanf("%s", w);scanf("%d", &k);
    m = strlen(w);
    for (int i = 0; i < k; ++i) {
        scanf("%lld %c", &a, &c);
        Q[c - 'A'].push_back(query(a, i));
    }

    for (int i = 0; i < 26; ++i) {
        for (int j = 0; j < m; ++j) {
            p[j] = (w[j] - 'A' == i) + (!!j) * p[j - 1];
        }
        for (int j = 0; j < Q[i].size(); ++j)
            ans[Q[i][j].id] = solve(Q[i][j].row);
    }

    for (int i = 0; i < k; ++i)
        printf("%lld\n", ans[i]);
    return 0;
}