#include <bits/stdc++.h>
#define N 300005
#define M 1005
using namespace std;
const int block_size = 1;
deque<char> block[N];
void solve(){
int n,m;
cin >> n >> m;
string s;
cin >> s;
assert(n < N);
for(int i=0;i<n;i++){
block[i/block_size].push_back(s[i]);
}
while(m--){
char type;
cin >> type;
if(type == 'a'){
int a,b;
cin >> a >> b;
a--;
b--;
vector<char> tmp;
char add;
for(int i = 0;block[a/block_size].size();i++){
if(i != a%block_size){
tmp.push_back(block[a/block_size].front());
}
else add = block[a/block_size].front();
block[a/block_size].pop_front();
}
for(auto u:tmp){
block[a/block_size].push_back(u);
}
if(block[a/block_size + 1].size()){
block[a/block_size].push_back(block[a/block_size + 1].front());
}
for(int i=a/block_size + 1;block[i].size();i++){
block[i].pop_front();
if(block[i+1].size()){
block[i].push_back(block[i+1].front());
}
}
tmp.clear();
char last = '.';
for(int i = 0;block[b/block_size].size();i++){
if(i == b%block_size)tmp.push_back(add);
if(tmp.size() < block_size){
tmp.push_back(block[b/block_size].front());
}
else last = block[b/block_size].front();
block[b/block_size].pop_front();
}
if(b == n-1)tmp.push_back(add);
for(auto u:tmp){
block[b/block_size].push_back(u);
}
for(int i=b/block_size + 1;last != '.';i++){
block[i].push_front(last);
if(block[i].size() > block_size){
last = block[i].back();
block[i].pop_back();
}
else last = '.';
}
/*
for(int j=0;block[j].size();j++){
for(int i=0;i<block[j].size();i++){
cout << block[j][i];
}
}
cout << endl;*/
}
if(type == 'q'){
int pos;
cin >> pos;
pos--;
cout << block[pos/block_size][pos%block_size] << endl;
}
}
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef Local
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t=1;
//cin>>t;
while(t--){
solve();
}
#ifdef Local
cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
#endif
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
150 ms |
202216 KB |
Output is correct |
| 2 |
Correct |
215 ms |
202376 KB |
Output is correct |
| 3 |
Execution timed out |
2092 ms |
239996 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
