#include <bits/stdc++.h>
#define ad push_back
using namespace std;
using ll = long long;
using ld = long double;
const int N = 1000*1000+7;
struct node{
char val;
int prior;
int key;
node *l,*r;
node (char _Val='0'):val(_Val),prior(rand()),key(1),l(nullptr),r(nullptr){}
};
void printt(node *t,int rnk=0){
if(t==nullptr)return;
printt(t->l,rnk+1);
cout<<rnk<<" -> LEVEL <-"<<t->val<<" "<<t->key<<" hi->"<<t->prior<<endl;
printt(t->r,rnk+1);
}
int cnt(node *t){
return t==nullptr ? 0:t->key;
}
void upd_cnt(node *&t){
if(t!=nullptr){
t->key=cnt(t->l)+cnt(t->r)+1;
}
}
void split(node *t,node *&l,node *&r,int key){
if(t==nullptr){
l=r=nullptr;
return;
}
// cout<<key<<" "<<t->val<<endl;
if(key<=cnt(t->l)){
// cout<<"qta "<<cnt(t->l)<<endl;
split(t->l,l,t->l,key);
r=t;
}
else{
split(t->r,t->r,r,key-cnt(t->l)-1);
l=t;
}
upd_cnt(t);
}
void merge(node *&t,node *l,node *r){
if(l==nullptr||r==nullptr){
t=l==nullptr ? r:l;
return;
}
if(l->prior>r->prior){
merge(l->r,l->r,r);t=l;
}
else{
merge(r->l,l,r->l);t=r;
}
upd_cnt(t);
upd_cnt(l);
upd_cnt(r);
}
node *ma[N];
int main(){
ios_base::sync_with_stdio(false);
srand(5431);
node *root=nullptr;
int n,m;
cin>>n>>m;
string s;
cin>>s;
ma[0]=new node('$');
for(int i=0;i<s.length();++i){
ma[i+1]=new node(s[i]);
}
for(int i=1;i<=s.length();++i){
merge(root,root,ma[i]);
/*
printt(root);
cout<<"yes\n"<<endl;
*/
}
printt(root);
for(int i=1;i<=m;++i){
char kind;
cin>>kind;
if(kind=='a'){
int a,b;
cin>>a>>b;
node *l=nullptr,*r=nullptr,*cur=nullptr;
if(a<b){
split(root,root,r,b);
split(root,root,l,a-1);
split(l,cur,l,1);
merge(root,root,l);
merge(root,root,cur);
merge(root,root,r);
// printt(root);
}
else if(a>b){
swap(a,b);
split(root,root,r,b-1);
split(root,root,l,a-1);
split(r,cur,r,1);
merge(root,root,cur);
merge(root,root,l);
merge(root,root,r);
}
}
else{
int pos;
cin>>pos;
node *l=nullptr,*r=nullptr,*ta=nullptr,*tb=nullptr;
// cout<<pos<<endl;
split(root,root,r,pos-1);
split(r,l,r,1);
/*
cout<<"start"<<endl;
printt(root);
cout<<"QQQQ"<<endl;
printt(l);
cout<<"ZZZZ"<<endl;
printt(r);
*/
cout<<l->val<<endl;
merge(r,l,r);
merge(root,root,r);
}
}
return 0;
}
Compilation message
collider.cpp: In function 'int main()':
collider.cpp:72:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<s.length();++i){
^
collider.cpp:75:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1;i<=s.length();++i){
^
collider.cpp:112:37: warning: unused variable 'ta' [-Wunused-variable]
node *l=nullptr,*r=nullptr,*ta=nullptr,*tb=nullptr;
^
collider.cpp:112:49: warning: unused variable 'tb' [-Wunused-variable]
node *l=nullptr,*r=nullptr,*ta=nullptr,*tb=nullptr;
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
9992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
