MC0439符号统计

码蹄集OJ-符号统计

MC0439・符号统计
难度：黄金
时间限制：1 秒
占用内存：256 M
收藏
报错
在华容道放曹的紧张时刻，小码哥接到了一个看似微不足道却至关重要的任务：解读一条仅由小写英文字母组成的神秘字符串 s，这条字符串隐藏着敌军的行军路线和计划。
字符串 s 长度为 n，小码哥需要对它进行 q 次询问，每次询问包括两个参数 l,r (l ≤ r)，他必须迅速回答区间 s_l ~ s_r 中，有多少种字母出现次数为偶数，有多少种为奇数。这些信息对于破解敌军的密码至关重要，因为它们关系到敌军的部署和动向。
格式
输入格式：第一行两个整数 n,q (1 < n,q ≤ 10⁵)。
第二行一个长度为 n 的字符串 s。
接下来 q 行，每行两个整数 l,r (1 ≤ l ≤ r ≤ n)。
输出格式：输出 q 行，每行两个整数 x,y，x 表示出现次数为偶数的字母数量，y 表示出现次数为奇数的字母数量。
样例 1
输入: 5 2
ababc
1 5
2 5
输出: 25 1
24 2
备注
本题中小写英文字母出现次数为 0 的，也算偶数。

代码：
 

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int sum[N][30];
int n,q,x,y;
int main()
{cin >> n >> q;string s;cin >> s;s = " " + s;for(int i = 1 ; i <= n ; i++){for(int j = 0 ; j < 26 ; j++){sum[i][j] = sum[i-1][j];}sum[i][s[i] - 'a']++;}while(q--){int l,r;cin >> l >> r;int even = 0,odd = 0;for(int i = 0 ; i < 26 ; i++){int cnt = sum[r][i] - sum[l-1][i];if(cnt % 2 == 0)even++;elseodd++;}cout << even << " " << odd << '\n';}return 0;
}