网站屏幕自适应代码,seo查询站长,长春高铁站,一流网站模板题干#xff1a;
链接#xff1a;https://ac.nowcoder.com/acm/contest/157/C 来源#xff1a;牛客网
题目描述 PH试纸#xff0c;是一种检测酸碱度的试纸#xff0c;试纸红色为酸性#xff0c;蓝色为碱性。 HtBest有一个PH试纸#xff0c;试纸被分成了n段#xff0c…题干
链接https://ac.nowcoder.com/acm/contest/157/C 来源牛客网
题目描述 PH试纸是一种检测酸碱度的试纸试纸红色为酸性蓝色为碱性。 HtBest有一个PH试纸试纸被分成了n段每一段都可以被染色成红色或者蓝色WHZ在试纸的每一段上都染为一种颜色HtBest有m个询问对于每个询问Ta想知道某种颜色第qi次在什么地方出现。
输入描述:
第一行有两个正整数nm。
第二行有n个字母(‘R’或’B’)每个第i个字母表示PH试纸第i段的颜色。
接下来m行第i行有一个大写字母 ci(‘R’或’B’)和一个正整数qi 用空格隔开表示查询颜色ci 第qi 次出现的位置。
输出描述:
共m行第i行一个整数表示查询结果若颜色ci出现次数少于qi次则输出-1否则输出颜色qi第ci次出现的位置。
示例1
输入
复制
2 2
RB
R 1
B 1
输出
复制
1
2
示例2
输入
复制
2 2
BB
R 1
B 2
输出
复制
-1
2
示例3
输入
复制
3 3
BRB
B 1
B 2
R 1
输出
复制
1
3
2
备注:
对于100%的测试数据
1 ≤ n, m ≤ 1000000
所有输入数据不超过1000000。
数据量较大注意使用更快的输入输出方式。
解题报告 直接维护两个前缀和复杂度O(m)。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX 2e6 5;
int n,m;
char s[MAX];
int R[MAX],B[MAX],r,b;
int main()
{cinnm;scanf(%s,s1);getchar();memset(R,-1,sizeof R);memset(B,-1,sizeof B);for(int i 1; in; i) {if(s[i] R) R[r] i;if(s[i] B) B[b] i;}char ch[4];int x;while(m--) {scanf(%s%d,ch,x);if(ch[0] R) printf(%d\n,R[x]);else printf(%d\n,B[x]);}return 0 ;
}
进一步扩展如果是1e5种颜色呢 答那也很简单啊1e5个vector就完事了。
再一步扩展如果两种颜色带修改呢 答那就建两棵线段树对应位置如果是当前线段树维护的颜色 那就置为1 然后查询第k大。
终极扩展那如果是1e5种颜色带修改呢 答那就主席树。每种颜色都建一棵4*n这么大的线段树因为同构 所以压缩到一棵主席树里查询就找该颜色对应的线段树 在线段树上二分线段树上维护的是 是该树维护的颜色则该点记为1 其他颜色记为0。%%%syt
