Codeforces Round ＃807 (Div. 2), problem: (C) Mark and His Unfinished Essay

一.题意

tina 拥有一串初始字符串s，他可以进行“复制现有字符串的某l-r段到当前字符串的末尾”操作多次，比如初始字符串是work 他选择 l=1 r=3 那么现在字符串就变成了workwor，当他反复执行c次这样的操作把这个字符串变完之后，给到你q个查询，每个查询给你一个数字k，让你输出目前字符串第k个字符是什么。

输入：

T（T组测试数据）

n（初始字符串长度） c（粘贴次数） q（q次查询，询问第k个字符是什么）

输出：

（q行）

第k个字符是什么

例子:

输入

1
4 3 3
mark
1 4
5 7
3 8
1
10
12
 

初始mark

• 第一次变换（将l=1,r=4段粘贴到末尾）->markmark
• 第二次变换（将l=5,r=7段粘贴到末尾）->markmarkmar
• 第三次变换（将l=3,r=8段粘贴到末尾）->markmarkmarrkmark

因此输出为

m

a

r 

二.思路

利用回溯思想，把每一段增添段的左右端点对应的源段的左右端点都记录下来，代码中的map<LL,LL>p实现这个操作，然后每次查询我们对k这个位置进行回溯，不断找到他在初始段的位置是哪个，因为它的位置是层层粘贴来的，所以它最初一定在初始字符串里有个位置。然后因为还要对k所在的区间进行查询，所以把全部增添字符段的左边界记录下来，代码中的map<LL,LL>st实现这个操作，然后每次查询二分查找是存在于哪一段增添片段，然后进行回溯，找这一段是哪一段粘贴来的，然后更新k的位置，然后再利用目前k的位置，再次进行二分查找左边界进行回溯，直到当前查找的这个位置的左边界为1（也就是当前位置是小于初始字符串长度的）为止。

然后输出当前位置的字符即可。

其实这题不用二分 就40个区间！ 哈哈哈我没掌握好时间复杂度 枚举的时候多了个二分，大家正常枚举就行~思路是正确的。

三.代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;
const int N = 55;
typedef long long LL;
map<LL,LL> p,st;
void solve()
{
    int n,c,q;
    cin>>n>>c>>q;
    string s;
    cin>>s;
    LL len=s.size();
    int cnt=1;//这个是存左边界的一个位置指针
    st[1]=1;//初始串的左边界为1
    for(int i=1;i<=c;i++)
    {
        LL a,b;
        cin>>a>>b;
        p[len+1]=a,p[len+1+b-a]=b;//这个是粘贴的段和原字符串段左右边界的对应关系
        st[++cnt]=len+1;//存下来每次粘贴的左边界
        len+=b-a+1;//字符串的长度，字符串在延长
        
    }
    
    while(q--)
    {
        LL k;
        cin>>k;
        
        while(k>s.size())//直到回溯到目前查询的位置 在初始字符串对应的位置为止
        {
            LL l=1,r=cnt;
            while(l<r)//二分找k目前在那个区间里面
            {
                LL mid=(l+r+1)>>1;
                if(st[mid]<=k) l=mid;
                else r=mid-1;
            }
            k=p[st[r]]+k-st[r];
        }
        cout<<s[k-1]<<endl;
        
    }

}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }
}