#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC target ("avx2")
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma comment (linker, "/STACK: 16777216")
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
#define int long long
using namespace std;
using namespace __gnu_pbds;
template <typename T> inline bool umax(T &a, const T &b) { if(a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool umin(T &a, const T &b) { if(a > b) { a = b; return 1; } return 0; }
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll mod = 998244353;
const ll base = 1e6 + 5;
const ll inf = 1e18;
const int MAX = 1e6;
const int lg = 20;
random_device rd;
mt19937 gen(rd());
uniform_int_distribution<ll> dis(1, inf);
const int buben = 1000;
void solve() {
int n, q;
cin >> n >> q;
int nb = (n + buben - 1) / buben;
vector<deque<char>> dq(nb);
string s;
cin >> s;
vector<int> bl(n), lb(nb), rb(nb);
for(int i = 0; i < n; i++) {
bl[i] = i / buben;
lb[bl[i]] = bl[i] * buben;
rb[bl[i]] = min(lb[bl[i]] + buben - 1, n - 1);
}
for(int i = 0; i < n; i++) {
dq[bl[i]].pb(s[i]);
}
auto norm = [&]() {
for(int i = 0; i + 1 < nb; i++) {
while(sz(dq[i]) > buben) {
dq[i + 1].push_front(dq[i].back());
dq[i].pop_back();
}
while(sz(dq[i]) < buben) {
dq[i].pb(dq[i + 1].front());
dq[i + 1].pop_front();
}
}
};
while(q--) {
char t;
cin >> t;
if(t == 'a') {
int i, j;
cin >> i >> j;
i--, j--;
int idx = 0;
while(i - sz(dq[idx]) >= 0) i -= sz(dq[idx++]);
char add = dq[idx][i];
dq[idx].erase(dq[idx].begin() + i);
idx = 0;
while(j - sz(dq[idx]) >= 0) j -= sz(dq[idx++]);
dq[idx].insert(dq[idx].begin() + j, add);
norm();
}
else {
int i;
cin >> i;
i--;
int idx = 0;
while(i - sz(dq[idx]) >= 0) i -= sz(dq[idx++]);
cout << dq[idx][i] << '\n';
}
}
}
signed main() {
// freopen("collider.in", "r", stdin); freopen("collider.out", "w", stdout);
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int ttt = 1;
// cin >> ttt;
while(ttt--) {
solve();
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
