[Codeforces] CF1705C Mark and His Unfinished Essay

题目传送门

题意

给定长度为 \(n\) 的字符串 \(s\)，进行 \(c\) 次操作，每次操作将 \(s_l\) 到 \(s_r\) 复制到字符串尾。 全部操作结束后有 \(q\) 次询问，每次询问字符串 \(s\) 的第 \(k\) 位。

数据保证 \(r\) 不超过当前字符串长度，\(k\) 不超过最终字符串长度。

思路及分析

通过数据范围，我们可以很明显的察觉到这题的正解不是模拟

首先来画一幅图，这是模拟题目样例1中的复制后的字符串

再将其按照每次操作划分一下：

再来手玩一下样例，如果把第\(10\)个位置的产生过程标出来，就是如下：

不难发现，除非当前字母属于最初的字符串，否则他一定有一个复制前的位置与之对应。所以，如果要求出当前字母的位置，就要知道复制前与之对应的位置的字母

这个操作就很像一个递归操作，终止条件就是当前字母的位置已经在最初的字符串中了。

这种方法只需要存储每次分的段落的左右端点即可，每次递归寻找，时间复杂度\(O(qc^2)\)

代码

很明显，这题需要开\(long\space long\)，但是不开的话会奇怪的TLE（别问我是怎么知道的

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node
{
	int l,r;
	int len;
	int st,en;
}a[50];
int n,c,q,len;
string s;

int find(int now,int turn)
{
	if(now<=n) return now;
	int t=(now-a[turn].st+1)+a[turn].l-1,i=1,cnt=n;
	while(a[i].en<t) i++;
//	cout<<"> "<<t<<" "<<i<<endl;
	return find(t,i);
}

int run()
{
	cin>>n>>c>>q>>s;
	a[0].l=1,a[0].r=n,a[0].st=1,a[0].en=n,a[0].len=n;
	for(int i=1;i<=c;i++)
	{
		cin>>a[i].l>>a[i].r;
		a[i].len=a[i].r-a[i].l+1;
		a[i].st=a[i-1].en+1,a[i].en=a[i].st+a[i].len-1;
	}
//	for(int i=1;i<=c;i++) cout<<a[i].st<<" "<<a[i].en<<" "<<a[i].len<<endl;
	while(q--)
	{
		int t,i=0;
		cin>>t;
		while(a[i].en<t) i++;
//		cout<<t<<" "<<i<<endl;
		cout<<s[find(t,i)-1]<<endl;
	}
}

signed main()
{
	int t;
	cin>>t;
	while(t--)
	{
		run();
	 } 
}