题意
给定长度为 \(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();
}
}