LuoguP13841.cpp

//https://www.luogu.com.cn/problem/P13841
//思路：找到所有的HI和HE，HE每变化一次就会在它前方增加一个S，HI根据它后面的字符决定它的开始变化时机，一旦开始变化后就是HIS->HER->SHER->SSHER
//当它的后面是s，那么就是从第1次开始变化，后面是he就是从第二次开始变化，后面是hi就是它后面的hi变化时机+2
//对于一次查询请求k与x，从最左侧的hi/he开始，如果经过K次变化后，hi/he扩展后的长度覆盖了x，那么就从这个扩展后hi/he找到第X位的字符

#include<cstdio>
#include<vector>
#include<algorithm>
#define TYPE_HE 0
#define TYPE_HI 1
using namespace std;
char BUF[200010];
typedef struct {
	int type;
	int pos;
	int mutateStart;
}Node;

void process() {
	int n, q;
	scanf("%d %d",&n, &q);
	scanf("%s", BUF);
	BUF[n] = 0;
	vector<Node> nodes;
	
	int nextState = -1;
	for(int i = n - 1; i > 0; --i) {
		if(BUF[i] == 'e' && BUF[i - 1] == 'h') {
			nodes.push_back(Node {TYPE_HE, i - 1, 1});
			nextState = 2;
			--i;
			continue;
		}
		if(BUF[i] == 's') {
			nextState = 1;
			continue;
		}
		if(BUF[i] == 'i' && BUF[i - 1] == 'h') {
			if(nextState >= 0) {
				nodes.push_back(Node{TYPE_HI, i - 1, nextState});
				nextState += 2;
			}
			--i;
			continue;
		}
		nextState = -1;
	}
	for(Node& node : nodes) {
		//printf("%d %d %d\n", node.type, node.pos, node.mutateStart);
	}
	int len = nodes.size();
	for(int i = 0; i < q; ++i) {
		int k, x;
		scanf("%d %d",&k, &x);
		x--;
		if(len <= 0) {
			if(x < n) {
				printf("%c\n", BUF[x]);
			}
			else {
				printf("0\n");
			}
			continue;
		}
		int expanded = 0;
		bool found = false;
		for(int j = len - 1; j >= 0; j--) {
			if(nodes[j].pos + expanded > x) {
				printf("%c\n", BUF[x - expanded]);
				found = true;
				break;
			}
			if(nodes[j].type == TYPE_HE) {
				int start = nodes[j].pos + expanded;
				int end = start + 1 + k;
				expanded += k;
				if(x >= start && x <= end) {
					if(x == end) {
						printf("e\n");
					}
					else if(x == end - 1) {
						printf("h\n");
					}
					else {
						printf("s\n");
					}
					found = true;
					break;
				}
			}
			else {
				int steps = max(0, k - nodes[j].mutateStart + 1);
				int expandedSteps = max(0, steps - 1);
				int start = nodes[j].pos + expanded;
				int end = start + expandedSteps + 1;
				expanded += expandedSteps;
				if(x == end + 1 && steps > 0) {
					printf("r\n");
					found = true;
					break;
				}
				if(x >= start && x <= end) {
					if(x == end) {
						if(steps > 0) {
							printf("e\n");
						}
						else {
							printf("i\n");
						}
					}
					else if(x == end - 1) {
						printf("h\n");
					}
					else {
						printf("s\n");
					}
					found = true;
					break;
				}
			}
		}
		if(found) {
			continue;
		}
		if(x < n + expanded) {
			printf("%c\n", BUF[x - expanded]);
		}
		else {
			printf("0\n");
		}
		//printf("%d %d\n", k, x);
	}
}

int main() {
	//freopen("LuoGu13841.in", "r", stdin);
	int c, t;
	scanf("%d %d", &c, &t);
	for(int i = 0; i < t; ++i){
		process();
	}
}