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

One . The question

tina Have a string of initial strings s, He can do it “ Copy an existing string l-r Segment to the end of the current string ” Operate multiple times , For example, the initial string is work He chose l=1 r=3 So now the string becomes workwor, When he repeatedly executes c After changing this string in this way , Here you are q A query , Each query gives you a number k, Let you output the current string number k What is a character .

Input ：

T（T Group test data ）

n（ Initial string length ） c（ Paste times ） q（q Queries , Question no k What is a character ）

Output ：

（q That's ok ）

The first k What is a character

Example :

Input

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

initial mark

• The first transformation （ take l=1,r=4 Paste the paragraph to the end ）->markmark
• The second transformation （ take l=5,r=7 Paste the paragraph to the end ）->markmarkmar
• The third transformation （ take l=3,r=8 Paste the paragraph to the end ）->markmarkmarrkmark

So the output is

m

a

r 

Two . Ideas

utilize to flash back thought , Record the left and right endpoints of the source segment corresponding to the left and right endpoints of each added segment , In code map<LL,LL>p Do this , Then every time we check k Go back to this position , Keep finding out where he is in the initial stage , Because its position is pasted layer by layer , So it must initially have a position in the initial string . And then because I have to be right k Query the interval , So record the left boundary of all the added character segments , In code map<LL,LL>st Do this , Then every time you query, you can find out which additional segment exists , And then go back , Find out which paragraph of this paragraph is pasted , And then update k The location of , Then use the present k The location of , Again, binary search the left boundary for backtracking , The left boundary of this position until the current search is 1（ That is, the current position is less than the length of the initial string ） until .

Then output the character of the current position .

In fact, this question doesn't need two points Just 40 Intervals ！ Hahaha, I didn't master the time complexity There is an extra dichotomy when enumerating , Just enumerate normally ~ The idea is right .

3、 ... and . Code

#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;// This is a position pointer to the left boundary 
    st[1]=1;// The left boundary of the initial string is 1
    for(int i=1;i<=c;i++)
    {
        LL a,b;
        cin>>a>>b;
        p[len+1]=a,p[len+1+b-a]=b;// This is the correspondence between the pasted segment and the left and right boundaries of the original string segment 
        st[++cnt]=len+1;// Save the left border of each paste 
        len+=b-a+1;// Length of string , String is lengthening 
        
    }
    
    while(q--)
    {
        LL k;
        cin>>k;
        
        while(k>s.size())// Until we trace back to the location of the current query   At the position corresponding to the initial string 
        {
            LL l=1,r=cnt;
            while(l<r)// Dichotomy k Currently in that range 
            {
                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();
    }
}