#include <bits/stdc++.h>
using namespace std;
mt19937 rng(time(0));
struct Node {
char val;
int prior;
int sz;
Node *left;
Node *right;
Node(char c) {
val = c;
prior = rng();
sz = 1;
left = nullptr;
right = nullptr;
}
} *root;
int get_sz(Node *nd) { return nd == nullptr ? 0 : nd->sz; }
void upd(Node *&nd) { nd->sz = get_sz(nd->left) + get_sz(nd->right) + 1; }
void Merge(Node *&treap, Node *left, Node *right) {
if (left == nullptr) { treap = right; return; }
if (right == nullptr) { treap = left; return; }
if (left->prior > right->prior) {
Merge(left->right, left->right, right);
treap = left;
} else {
Merge(right->left, left, right->left);
treap = right;
}
upd(treap);
}
void Split(Node *treap, Node *&left, Node *&right, int val) {
if (treap == nullptr) {
left = nullptr;
right = nullptr;
return;
}
if (get_sz(treap->left) < val) {
Split(treap->right, treap->right, right, val - get_sz(treap->left) - 1);
left = treap;
} else {
Split(treap->left, left, treap->left, val);
right = treap;
}
upd(treap);
}
void dfs(Node *nd) {
if (nd == nullptr) return;
dfs(nd->left);
printf("%c", nd->val);
dfs(nd->right);
}
const int N = 1e6 + 10;
int n, q;
char s[N];
char Query(int idx) {
Node *a, *b;
Split(root, a, b, idx - 1);
Node *c, *d;
Split(b, c, d, 1);
char res = c->val;
Merge(b, c, d);
Merge(root, a, b);
return res;
}
int main() {
scanf("%d%d", &n, &q);
scanf("%s", s + 1);
for (int i = 1; i <= n; i++) {
Merge(root, root, new Node(s[i]));
}
while (q--) {
char c;
scanf("%c", &c);
while (c < 'a' || c > 'z') {
scanf("%c", &c);
}
if (c == 'a') {
int i, j;
scanf("%d%d", &i, &j);
if (i < j) j--;
Node *a, *b;
Split(root, a, b, i - 1);
Node *c, *d;
Split(b, c, d, 1);
Merge(root, a, d);
Split(root, a, b, j - 1);
Merge(d, a, c);
Merge(root, d, b);
} else {
int i;
scanf("%d", &i);
printf("%c\n", Query(i));
}
}
}
Compilation message
collider.cpp: In function 'int main()':
collider.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
67 | scanf("%d%d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~
collider.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | scanf("%s", s + 1);
| ~~~~~^~~~~~~~~~~~~
collider.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
74 | scanf("%c", &c);
| ~~~~~^~~~~~~~~~
collider.cpp:76:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
76 | scanf("%c", &c);
| ~~~~~^~~~~~~~~~
collider.cpp:80:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
80 | scanf("%d%d", &i, &j);
| ~~~~~^~~~~~~~~~~~~~~~
collider.cpp:92:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
92 | scanf("%d", &i);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
