?
BZOJ 3065 带插入区间K小值 替罪羊树套线段树(二)
bool Check(ScapeTree *a) { if(a->son[0] != NULL) if((double)a->son[0]->size / a->size > alpha) return false; if(a->son[1] != NULL) if((double)a->son[1]->size / a->size > alpha) return false; return true; } ScapeTree *will_rebuild; void Insert(ScapeTree *&a,int k,int val) { if(a == NULL) { SegTree *root = new SegTree(); root->Insert(0,RANGE,val); a = new (val,NULL,NULL,root,1)ScapeTree; return ; } a->root->Insert(0,RANGE,val); int temp = SIZE(a->son[0]); if(k <= temp) Insert(a->son[0],k,val); else Insert(a->son[1],k - temp - 1,val); a->Maintain(); if(!Check(a)) will_rebuild = a; } void Modify(ScapeTree *a,int k,int val) { static int old; if(k <= SIZE(a->son[0])) Modify(a->son[0],k,val); else if((k -= SIZE(a->son[0])) == 1) { old = a->val; a->val = val; } else Modify(a->son[1],k - 1,val); a->root->Delete(0,RANGE,old); a->root->Insert(0,RANGE,val); } inline int Judge(int l,int r,int ans) { return root->Ask(r,ans) - root->Ask(l - 1,ans); } inline int Query(int x,int y,int k) { int l = 0,r = RANGE,re = -1; while(l <= r) { int mid = (l + r) >
> 1; if(Judge(x,y,mid) >= k) r = mid - 1,re = mid; else l = mid + 1; } return re; } char c[10]; int main() { cin >> cnt; for(int i = 1; i <= cnt; ++i) scanf("%d",&src[i]); root = BuildScapeTree(1,cnt,src); cin >> asks; int last_ans = 0; for(int x,y,z,i = 1; i <= asks; ++i) { scanf("%s%d%d",c,&x,&y); x ^= last_ans; y ^= last_ans; if(c[0] == 'Q') { scanf("%d",&z); z ^= last_ans; printf("%d\n",last_ans = Query(x,y,z)); } else if(c[0] == 'M') Modify(root,x,y); else { will_rebuild = NULL; Insert(root,x - 1,y); if(will_rebuild != NULL) Rebuild(will_rebuild); } } return 0; }