#pragma GCC optimize("Ofast")
#include "lib1271.h"
#include<stdio.h>
#include<random>
#include<time.h>
#include<algorithm>
using namespace std;
struct Treap{
Treap *l,*r;
int sz;
char c;
Treap(){}
Treap(char _c){
c=_c;
sz=1;
l=r=0;
}
}*treap[1000025];
int cnt;
void pull(Treap *t){
t->sz=(t->l?t->l->sz:0)+(t->r?t->r->sz:0)+1;
}
void copy(Treap *&a,Treap *&b){
a=new Treap;
a->l=b->l;
a->r=b->r;
a->sz=b->sz;
a->c=b->c;
}
Treap* merge(Treap *a,Treap *b){
if(!a||!b)
return a?a:b;
Treap *t;
if(rand()%(a->sz+b->sz)<a->sz){
copy(t,a);
t->r=merge(a->r,b);
pull(t);
}
else{
copy(t,b);
t->l=merge(a,b->l);
pull(t);
}
return t;
}
void split(Treap *t,Treap *&a,Treap *&b,int k){
if(!t){
a=b=0;
return;
}
int l_sz=t->l?t->l->sz:0;
if(l_sz+1<=k){
copy(a,t);
split(t->r,a->r,b,k-l_sz-1);
pull(a);
}
else{
copy(b,t);
split(t->l,a,b->l,k);
pull(b);
}
}
void Init(){
fill(treap,treap+1000025,nullptr);
cnt=0;
}
void TypeLetter(char c){
cnt++;
treap[cnt]=merge(treap[cnt-1],new Treap(c));
}
void UndoCommands(int k){
cnt++;
treap[cnt]=treap[cnt-k-1];
}
char GetLetter(int k){
Treap *left=0,*right=0;
split(treap[cnt],left,treap[cnt],k);
split(treap[cnt],treap[cnt],right,1);
char temp=treap[cnt]->c;
treap[cnt]=merge(merge(left,treap[cnt]),right);
return temp;
}
Compilation message
scrivener.cpp:2:10: fatal error: lib1271.h: No such file or directory
#include "lib1271.h"
^~~~~~~~~~~
compilation terminated.
