筆記一下
code時大蓋遇到兩個問題
1. string需要d&c的加進去，儘量平衡
2. 冊資有加密（強迫在線）
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
int delta = 0;
int grand(){
return rand()^0xdeadbeaf;
}
struct Jeap{
Jeap* l;
Jeap* r;
int sz;
char val;
int pri;
Jeap(char _v = 0){
l = nullptr, r = nullptr;
sz = 1;
val = _v;
pri = rand();
return;
}
int Size(){
if(this == nullptr) return 0;
return sz;
}
void Update(){
sz = l->Size() + r->Size() + 1;
return;
}
void Print(){
if(this == nullptr)
return;
l->Print();
printf("%c", val);
delta += (val == 'c');
r->Print();
return;
}
};
Jeap* Cp(Jeap* a){
if(a == nullptr)
return nullptr;
Jeap* ret = new Jeap();
*ret = *a;
return ret;
}
Jeap* Merge(Jeap* a, Jeap* b){
if(a == nullptr) return Cp(b);
if(b == nullptr) return Cp(a);
if(a->pri > b->pri){
a = Cp(a);
a->r = Merge(a->r, b);
a->Update();
return a;
}else{
b = Cp(b);
b->l = Merge(a, b->l);
b->Update();
return b;
}
}
void Split(Jeap* org, int low, Jeap* &a, Jeap* &b){
if(!low){
a = nullptr, b = Cp(org);
}else if(org == nullptr) a = nullptr, b = nullptr;
else if(org->l->Size() >= low){
b = Cp(org);
Split(org->l, low, a, b->l);
b->Update();
}else{
a = Cp(org);
Split(org->r, low-org->l->Size()-1, a->r, b);
a->Update();
}
return;
}
typedef Jeap* ptrJeap;
Jeap* jver[50005];
int ver;
void Init(){
jver[0] = nullptr;
ver = 0;
return;
}
Jeap* Build(const char* str, int ll, int rr){
if(ll > rr) return nullptr;
int md = (ll+rr)>>1;
Jeap* ret = nullptr;
ret = Merge(ret, Build(str, ll, md-1));
ret = Merge(ret, new Jeap(str[md]));
ret = Merge(ret, Build(str, md+1, rr));
return ret;
}
void PrintVer(int ts = ver){
printf("ver%d -> [", ts);
jver[ts]->Print();
printf("]\n");
return;
}
void Insert(int p, const char* str){
ptrJeap a, b;
Split(jver[ver], p, a, b);
a = Merge(a, Build(str, 0, strlen(str)-1));
jver[++ver] = Merge(a, b);
return;
}
void Delete(int p, int c){
ptrJeap a, b, b1, c1;
Split(jver[ver], p, a, b);
Split(b, c, b1, c1);
jver[++ver] = Merge(a, c1);
return;
}
void Iter(int _ver, int p, int c){
ptrJeap a, b, b1, c1;
Split(jver[_ver], p, a, b);
Split(b, c, b1, c1);
b1->Print();
puts("");
jver[_ver] = Merge(a, b1);
jver[_ver] = Merge(jver[_ver], c1);
return;
}
char s[200];
int main(){
Init();
delta = 0;
int n; scanf("%d", &n);
int op, v, p, c;
while(n--){
scanf("%d", &op);
if(op == 1){
scanf("%d %s", &p, s);
Insert(p - delta, s);
}else if(op == 2){
scanf("%d %d", &p, &c);
Delete(p-1 - delta, c - delta);
}else if(op == 3){
scanf("%d %d %d", &v, &p, &c);
Iter(v - delta, p-1 - delta, c - delta);
}
//for(int lx = 0;lx <= ver;lx++)
// PrintVer(lx);
}
return 0;
}
沒有留言:
張貼留言