首页 > 代码库 > BZOJ 3217 ALOEXT 替罪羊树套Trie树
BZOJ 3217 ALOEXT 替罪羊树套Trie树
题目大意:维护一个序列,支持以下操作:
1.在某个位置插入一个数
2.删除某个位置上的数
3.修改某个位置上的数
4.求某段区间中的次大值与区间中另一个数的异或值的最大值
强制在线
替罪羊树套Trie树。。。终于尼玛A了。。。7.4KB的大代码啊- -
插入和修改同带插入区间k小值 删除要打标记不能直接删
删除的时候注意 删除导致的不平衡不要重建 否则复杂度无法保证
因此每个节点维护一个max_size代表历史size最大值 判断不平衡时用这个变量来判断即可
注意访问替罪羊树的时候一定要判断当前节点是否已被删除- - 否则问题大大的- -
询问时先找到次小值 然后找异或的最大值 注意不要二分 直接在替罪羊树上找对应区间 具体写法详见代码(如果能找到函数在哪里的话- -)
还有啥注意事项。。。 变量重名,成员函数访问错误,友元函数不引用本结构体指针,失效的默认值,忘记重载delete。。。我也是醉了
尼玛万恶的360把我家的渣渣C-Free给杀了- - 调试功能爆炸了,只能gdb- - 调过样例之后就没心情再调了- -
#include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 200200 #define L (1<<15) #define ALPHA 0.88 using namespace std; class Trie *null; class Trie{ private: static queue<Trie*> bin; public: Trie *son[2]; int size; void* operator new (size_t,Trie *_,Trie *__,int ___) { static Trie *mempool,*C=mempool; Trie *re; if( !bin.empty() ) re=bin.front(),bin.pop(); else { if(C==mempool) mempool=(C=new Trie[L])+L; re=C++; } re->son[0]=_; re->son[1]=__; re->size=___; return re; } void operator delete (void *p) { bin.push((Trie*)p); } friend void Insert(Trie* &p,int num,int pos=1<<20) { if(p==null) p=new (null,null,0) Trie; p->size++; if(!pos) return ; if(num&pos) Insert(p->son[1],num,pos>>1); else Insert(p->son[0],num,pos>>1); } void Delete(int num,int pos=1<<20) { size--; if(!pos) return ; if(num&pos) son[1]->Delete(num,pos>>1); else son[0]->Delete(num,pos>>1); } int Get_Kth(int pos,int k) { if(!pos) return 0; if(k<=son[1]->size) return pos|son[1]->Get_Kth(pos>>1,k); else return son[0]->Get_Kth(pos>>1,k-son[1]->size); } int Get_Max(int pos,int x) { int temp=pos&x?1:0; if(!pos) return 0; if(son[!temp]->size) return pos|son[!temp]->Get_Max(pos>>1,x); else return son[temp]->Get_Max(pos>>1,x); } void Decomposition() { if(this==null) return ; son[0]->Decomposition(); son[1]->Decomposition(); delete this; } }; class Kth_Getter{ private: int first,second; public: Kth_Getter():first(-1),second(-1) {} bool Insert(int x) { if(x>first) { second=first; first=x; return true; } if(x>second) second=x; return false; } int Second() { return second; } }; class Scapetree *nil,**to_rebuild; int to_delete; class Scapetree{ private: static queue<Scapetree*> bin; public: static int stack[M],top; Scapetree *ls,*rs; int val,size,max_size; Trie *tree; void* operator new (size_t,Scapetree *_,Scapetree *__,int ___,int ____) { static Scapetree *mempool,*C=mempool; Scapetree *re; if( !bin.empty() ) re=bin.front(),bin.pop(); else { if(C==mempool) mempool=(C=new Scapetree[L])+L; re=C++; } re->ls=_; re->rs=__; re->val=___; re->size=____; re->max_size=____; re->tree=null; return re; } void operator delete (void *p) { bin.push((Scapetree*)p); } bool Check() { if((double)ls->max_size/max_size>ALPHA) return true; if((double)rs->max_size/max_size>ALPHA) return true; return false; } friend void Insert(Scapetree* &p,int pos,int val) { int temp=~p->val?1:0; if(p==nil) { p=new (nil,nil,val,1) Scapetree; Insert(p->tree,val); return ; } p->size++;Insert(p->tree,val); p->max_size=max(p->max_size,p->size); if(pos<=p->ls->size) Insert(p->ls,pos,val); else Insert(p->rs,pos-p->ls->size-temp,val); if(p->Check()) to_rebuild=&p; } void Delete(int pos) { int temp=~val?1:0; if(pos<=ls->size) ls->Delete(pos); else { pos-=ls->size; if(pos==temp) { to_delete=val; val=-1; } else rs->Delete(pos-temp); } size--;tree->Delete(to_delete); } void Modify(int pos,int val) { int temp=~this->val?1:0; if(pos<=ls->size) ls->Modify(pos,val); else { pos-=ls->size; if(pos==temp) { to_delete=Scapetree::val; Scapetree::val=val; } else rs->Modify(pos-temp,val); } tree->Delete(to_delete); Insert(tree,val); } void Decomposition() { if(this==nil) return ; ls->Decomposition(); if(~val) stack[++top]=val; rs->Decomposition(); tree->Decomposition(); delete(this); } void Get_2th(int l,int r,Kth_Getter& getter) { if( l==1 && r==size ) { if( getter.Insert( tree->Get_Kth(1<<20,1) ) && size>=2 ) getter.Insert( tree->Get_Kth(1<<20,2) ); return ; } int temp=~val?1:0; if( temp && l<=ls->size+1 && r>=ls->size+1 ) getter.Insert(val); if( l<=ls->size ) ls->Get_2th(l,min(r,ls->size),getter); if( r>ls->size+temp ) rs->Get_2th(max(l-(ls->size+temp),1),r-(ls->size+temp),getter); } int Get_Max(int l,int r,int val) { if( l==1 && r==size ) return tree->Get_Max(1<<20,val); int re=-1,temp=~this->val?1:0; if( temp && l<=ls->size+1 && r>=ls->size+1 ) re=max(re,val^this->val); if( l<=ls->size ) re=max(re,ls->Get_Max(l,min(r,ls->size),val) ); if( r>ls->size+temp ) re=max(re,rs->Get_Max(max(l-(ls->size+temp),1),r-(ls->size+temp),val) ); return re; } void Output() { if(this==nil) return ; ls->Output(); printf("---------------- %d\n",val); rs->Output(); } }*root=nil; Scapetree* Build_Tree(int a[],int l,int r) { if(l>r) return nil; int i,mid=l+r>>1; Scapetree *lson=Build_Tree(a,l,mid-1); Scapetree *rson=Build_Tree(a,mid+1,r); Scapetree *re=new (lson,rson,a[mid],r-l+1) Scapetree; for(i=l;i<=r;i++) Insert(re->tree,a[i]); return re; } queue<Trie*> Trie :: bin; queue<Scapetree*> Scapetree :: bin; int Scapetree :: stack[M]; int Scapetree :: top; int n,m,last_ans; int a[M>>1]; void Initialize() { null=new (0x0,0x0,0) Trie; null->son[0]=null->son[1]=null; nil=new (0x0,0x0,0,0) Scapetree; nil->ls=nil->rs=nil; } void Insert(int pos,int val) { to_rebuild=0x0; Insert(root,pos,val); if(to_rebuild) { Scapetree::top=0; (*to_rebuild)->Decomposition(); (*to_rebuild)=Build_Tree(Scapetree::stack,1,Scapetree::top); } } int Query(int l,int r) { Kth_Getter getter; root->Get_2th(l,r,getter); int val=getter.Second(); return root->Get_Max(l,r,val); } int main() { #ifndef ONLINE_JUDGE freopen("3217.in","r",stdin); freopen("3217.out","w",stdout); #endif int i,x,y; char p[100]; Initialize(); cin>>n>>m; for(i=1;i<=n;i++) scanf("%d",&a[i]); root=Build_Tree(a,1,n); for(i=1;i<=m;i++) { scanf("%s",p); switch(p[0]) { case 'I': scanf("%d%d",&x,&y); x=(x+last_ans)%(n++); y=(y+last_ans)%1048576; Insert(x,y); break; case 'D': scanf("%d",&x); x=(x+last_ans)%n+1; root->Delete(x); n--; break; case 'C': scanf("%d%d",&x,&y); x=(x+last_ans)%n+1; y=(y+last_ans)%1048576; root->Modify(x,y); break; case 'F': scanf("%d%d",&x,&y); x=(x+last_ans)%n+1; y=(y+last_ans)%n+1; if(x>y) swap(x,y); printf("%d\n", last_ans=Query(x,y) ); break; } //root->Output();puts(""); } return 0; }
BZOJ 3217 ALOEXT 替罪羊树套Trie树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。