output 最后一行是什么意思?!块状链表敬佩kkk?!
by 持之以珩 @ 2019-02-25 22:48:10
orzzzzz 平衡树
by NaCly_Fish @ 2019-02-25 22:49:00
maybe this?
```
#undef debug
#include<bits/stdc++.h>
using namespace std;
list<string> node;
size_t len(0);
string _a("kkksc03");
#define strnull begin(_a)
list<string> _aa{"kkksc03","400ACpj"};
string notout;
#define ndnull begin(_aa)
#define max_len\
static_cast<size_t>\
(sqrt(static_cast<double>(len)))<<1
#define min_len\
static_cast<size_t>\
(sqrt(static_cast<double>(len)))>>1
pair<string,string>
split(const string& s,size_t pos){
string a="",b="";
for(size_t i=0;i<s.size();++i)
if(i<pos)a+=s[i];
else b+=s[i];
return make_pair(a,b);
}
void split(list<string>::iterator& pos,size_t brk){
auto strpair=split(*pos,brk);
*pos=strpair.second;
node.insert(pos,strpair.first);
--pos;
}
void merge(list<string>::iterator p1,
list<string>::iterator p2){
if(p1==end(node)||p2==end(node))return;
*p1+=*p2;
node.erase(p2);
}
void maintain(){
for(auto it=begin(node);it!=end(node);++it){
if(it->size()>max_len)
split(it,max_len);
if(it->size()>min_len)continue;
if((++it)--!=end(node)){
if(it->size()+(++it)--->size()<max_len)
merge(it,(++it)--);
}
}
}
string::iterator at(size_t pos){
if(!pos)return strnull;
if(pos>=len)return strnull;
int len=0;
auto ti=begin(node);
while(len+ti->size()<pos)len+=ti->size(),++ti;
auto it=begin(*ti);
for(size_t i=len;i!=pos;++i,++it);
return it;
}
list<string>::iterator atnode(size_t pos){
if(!pos)return begin(node);
if(pos>=len)return ndnull;
int len=0;
auto ti=begin(node);
while(len+ti->size()<pos)len+=ti->size(),++ti;
if(ti==end(node))return ndnull;
return ti;
}
void insert(size_t pos,string s){
len+=s.size();
if(!pos){
node.push_front(s);
maintain();
return;
}
auto tmp=node;
node.clear();//these 3 lines divide string `s'.
node.push_back(s);
maintain();//these.
auto tmptmp=node;
node=tmp;tmp=tmptmp;//restore `node'.
//Store `s' in `tmp'.
auto ipos=atnode(pos);
auto kkk=at(pos);
split(ipos,kkk-ipos->begin());++ipos;
if(ipos==end(node)){
for(auto it=begin(tmp);it!=end(tmp);++it)
node.push_back(*it);
}else{
for(auto it=begin(tmp);it!=end(tmp);++it)
node.insert(ipos,*it);
}
maintain();
}
void erase(size_t _pos,size_t len){
auto pos=atnode(_pos);
auto brk=at(_pos);
split(pos,brk-pos->begin());
++pos;//`brk' is already unuseful. 2019.2.25
while(pos->size()<len){
len-=pos->size();
++pos;
node.erase((--pos)++);
}
string tmp="";
for(size_t i=len;i<pos->size();++i)
tmp+=(*pos)[i];
*pos=tmp;
maintain();
}
void output(size_t pos,size_t len){
notout="";
for(auto it=begin(node);it!=end(node);++it)
notout+=*it;
for(size_t i=pos+1,j=1;j<=len;++i,++j)
putchar(notout[i]);
putchar('\n');
}
int read(){
int sign=1,x=0;char ch=getchar();
while(!isdigit(ch)&&ch!='-')ch=getchar();
if(ch=='-'){
sign=-1;ch=getchar();
}
x=ch-'0';ch=getchar();
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return sign*x;
}
int main(){
int pointer=0;
int t=read();
char op[10]="";
while(t--){
scanf("%s",op);
if(isspace(op[0]))scanf("%s",op);
if(op[0]=='M'){//move
pointer=read();
}else if(op[0]=='I'){//ins
int len=read();
string s;
for(int i=1;i<=len;++i){
char ch=getchar();
while(ch=='\n')ch=getchar();
s+=ch;
}
insert(pointer,s);
}else if(op[0]=='D'){//del
erase(pointer,read());
}else if(op[0]=='G'){
// int n=read();
// auto bl=atnode(pointer);
// auto kkk=at(pointer);
// for(int i=1;i<=n;++i){
// ++kkk;
// if(kkk==end(*bl)){
// ++bl;kkk=begin(*bl);
// }
// putchar(*kkk);
// }
// putchar('\n');
output(pointer-1,read());
}else if(op[0]=='P')--pointer;
else ++pointer;
#ifdef debug
puts("Outputting...");
for(auto it=begin(node);it!=end(node);++it)
cout<<'\t'<<*it<<endl;
#endif
}
return 0;
}
```
by 持之以珩 @ 2019-02-25 23:09:55
0?!
by 持之以珩 @ 2019-02-25 23:10:08
@[NaCly_Fish](/user/115864) It is me who want to say "Orz" now!
by 持之以珩 @ 2019-12-14 23:15:04
kaogu
by 持之以珩 @ 2019-12-14 23:15:17