3.8 KiB

Raw Permalink Blame History

Eye of the Storm

题目描述

云浅来到了风暴的中心。这里漂浮着一个长为 n 的，由小写字母组成的字符串 S。字符串的下标从 1 开始。

想要逃出风暴，就需要回答一些询问。

每次询问会给出一对正整数 l,r 和一个字符串 T，云浅需要回答 S_{l\cdots r} 这段子串内有多少个子序列是 T。这里保证 T 的长度为 2。

形式化地，你需要求出有多少对 (i,j) 满足 l\le i<j\le r，使得 S_i=T_1,S_j=T_2。

现在云浅预测出了风暴在接下来 q 个时刻内的询问，你需要帮她求出每个询问的答案。

输入格式

第一行两个正整数 n,q。

第二行一个长为 n 的字符串 S。

接下来 q 行，每行会给出两个正整数 l,r 和一个字符串 T，表示云浅需要回答的询问。保证 |T|=2。

输出格式

对于每次询问，输出一行一个正整数表示答案。

数据范围

对于 100\% 的数据，1\le n,q\le 2\times 10^5,1\le l\le r\le n,S,T 中只含小写英文字母，|T|=2。

测试点编号	`n`	`q`	其他
`1\sim 4`	`\le 100`	`\le 100`	无
`5\sim 8`	`\le 5000`	`\le 5000`	无
`9\sim 10`	`\le 10^5`	`\le 10^5`	所有的 `S_i` 均相同
`11\sim 12`	`\le 10^5`	`\le 3`	无
`13\sim 16`	`\le 10^5`	`\le 10^5`	无
`17\sim 20`	`\le 2\times 10^5`	`\le 2\times 10^5`	无

题解

记字符集大小为 V=26。

考虑设 \text{Sum}(i,c) 为 S_{1\cdots i} 中字符 c 的出现次数，那么答案就是\displaystyle \sum_{l\le i\le r,S_i==T_2}\text{Sum}(i-1,T_1)-\text{Sum}(l-1,T_1) 用一个 vector 来存一下 S 中等于 T_2 的数的出现位置，顺便附带记录一下 \text{Sum}，每次查询的时候二分出 r 前面和 l 后面的第一个满足等于 S_i==T_2 的 i 的位置，那么要求的就是 vector 内的一个前缀和。具体可以看代码。

时间复杂度 O(nV+q\log n)，空间复杂度 O(nV)。

参考代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0, f = 1;
    char c = getchar();
    for (; (c < '0' || c > '9'); c = getchar()) {
        if (c == '-') {
            f = -1;
        }
    }
    for (; (c >= '0'&& c <= '9'); c = getchar()) {
        x = x * 10 + (c& 15);
    }
    return x * f;
}
int n, q;
string S, T;
#define mk make_pair
#define fi first
#define se second
const int MN = 2e5 + 5;
vector<int > pos[26], sum[26][26];
int f[MN][26];
signed main(void) {
    freopen("ridge.in", "r", stdin);
    freopen("ridge.out", "w", stdout);
    cin >> n >> q;
    cin >> S;
    for (int i = 1; i <= n; i++) {
        int t = (int)(S[i - 1] - 'a');
        for (int x = 0; x < 26; x++) {
            f[i][x] = f[i - 1][x], sum[t][x].push_back(f[i][x]);
        }
        pos[t].push_back(i);
        f[i][t]++;
    }
    for (int t = 0; t < 26; t++) {
        for (int x = 0; x < 26; x++) {
            for (int j = 1; j < sum[t][x].size(); j++) {
                sum[t][x][j] += sum[t][x][j - 1];
            }
        }
    }
    while (q--) {
        int l, r;
        cin >> l >> r >> T;
        if (l > r) {
            puts("**");
            return 0;
        }
        int a = T[0] - 'a', b = T[1] - 'a';
        int ql = lower_bound(pos[b].begin(), pos[b].end(), l) - pos[b].begin();
        int qr = upper_bound(pos[b].begin(), pos[b].end(), r) - pos[b].begin() - 1;
        if (ql > qr) {
            puts("0");
            continue;
        }
        int cnt = qr - ql + 1;
        cout << sum[b][a][qr] - (ql == 0 ? 0 : sum[b][a][ql - 1]) - f[l - 1][a] * cnt << endl;
    }
    return 0;
}

3.8 KiB Raw Permalink Blame History