首页 > 代码库 > BZOJ 3065 带插入区间K小值 替罪羊树套线段树
BZOJ 3065 带插入区间K小值 替罪羊树套线段树
题目大意：带插入，单点修改的区间k小值在线查询。
思路：本年度做过最酸爽的题。
树套树的本质是一个外层不会动的树来套一个内层会动（或不会动）的树。两个树的时间复杂度相乘也就是差不多O(nlog^2n)左右。但是众所周知，高级数据结构经常会伴有庞大的常数，所以一般来说树套树的常数也不会小到哪去。所以在做这种题的时候先不要考虑常数的问题。。。
为什么要用替罪羊树呢？因为一般的平衡树都是会动的，这就很难办了。外层的树动了之后，内层的树肯定也是会动的。很显然，一般的二叉平衡树会经常会旋转，这样在动外层的树那么时间复杂度就会飞起。所以就需要一种不会动（或很少动）的二叉平衡树来做外层的树。
这样的树有两种：朝鲜树和替罪羊树。其中朝鲜树的时间复杂度是大概O(√n)的，而替罪羊树是O(logn)的。为什么朝鲜树的均摊时间是O(√n)呢，因为朝鲜树的思想是当树的高度超过√n是就暴力重建整棵树。所以所有操作的均摊时间就是O(√n)。
替罪羊树相对来说就比较优越一些了。一般来说替罪羊树很少直接暴力重建整棵树。在每次向替罪羊树中插入东西的时候，就查看经过的节点中有没有子树的size太大的节点，如果有的话就直接重建一个子树，保证了树的高度是logn左右，均摊时间复杂度也就减下来了。
重建一棵子树也十分简单，把这个子树的中序遍历记录下来，然后让它变得平衡就行了。然后要记得经过的所有节点都要回收内存，~不然内存会飞起~，用一个厉害一点的垃圾收集器，内存池也别静态开了，没敢，直接全都动态。当然，外层替罪羊树的内存回收了，内层的线段树的内存也要回收，~不然内存会飞起~。
这个题的查询过程时间复杂度O(nlong^3n)，其余操作均摊O(nlong^2n)。推荐你们去看看vfk的代码，简直dio……
CODE：
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 70010
#define RANGE 70010
using namespace std;
#define SIZE(a) ((a) == NULL ? 0:(a)->size)
const double alpha = 0.8;
const int L = 1 << 15;
int cnt,src[MAX],asks;
struct SegTree{
static queue<SegTree *> bin;
SegTree *son[2];
int cnt;
void *operator new(size_t,int _ = 0,SegTree *__ = NULL,SegTree *___ = NULL) {
static SegTree *mempool,*C;
SegTree *re;
if(!bin.empty()) {
re = bin.front(); bin.pop();
}
else {
if(C == mempool)
C = new SegTree[L],mempool = C + L;
re = C++;
}
re->cnt = _;
re->son[0] = __,re->son[1] = ___;
return re;
}
void operator delete(void *r) {
bin.push(static_cast<SegTree *>(r));
}
void Insert(int l,int r,int x) {
++cnt;
if(l == r) return ;
int mid = (l + r) >> 1;
if(x <= mid) {
if(son[0] == NULL)
son[0] = new SegTree();
son[0]->Insert(l,mid,x);
}
else {
if(son[1] == NULL)
son[1] = new SegTree();
son[1]->Insert(mid + 1,r,x);
}
}
void Delete(int l,int r,int x) {
--cnt;
if(l == r) return ;
int mid = (l + r) >> 1;
if(x <= mid) son[0]->Delete(l,mid,x);
else son[1]->Delete(mid + 1,r,x);
}
void Decomposition() {
if(son[0] != NULL) son[0]->Decomposition();
if(son[1] != NULL) son[1]->Decomposition();
delete this;
}
int Ask(int l,int r,int x) {
if(this == NULL) return 0;
if(l == r) return cnt;
int mid = (l + r) >> 1;
if(x <= mid) return son[0]->Ask(l,mid,x);
return (son[0] ? son[0]->cnt:0) + son[1]->Ask(mid + 1,r,x);
}
};
struct ScapeTree{
static queue<ScapeTree *> bin;
ScapeTree *son[2];
SegTree *root;
int val,size;
void *operator new(size_t,int _,ScapeTree *__,ScapeTree *___,SegTree *____,int _size) {
static ScapeTree *mempool,*C;
ScapeTree *re;
if(!bin.empty()) {
re = bin.front(); bin.pop();
}
else {
if(C == mempool)
C = new ScapeTree[L],mempool = C + L;
re = C++;
}
re->val = _;
re->son[0] = __,re->son[1] = ___;
re->root = ____;
re->size = _size;
return re;
}
void operator delete(void *r) {
bin.push(static_cast<ScapeTree *>(r));
}
void Maintain() {
size = 1;
if(son[0] != NULL) size += son[0]->size;
if(son[1] != NULL) size += son[1]->size;
}
int Ask(int k,int _val) {
if(!k) return 0;
if(SIZE(son[0]) >= k) return son[0]->Ask(k,_val);
k -= SIZE(son[0]);
int re = (son[0] ? son[0]->root->Ask(0,RANGE,_val):0) + (val <= _val);
if(k == 1) return re;
return son[1]->Ask(k - 1,_val) + re;
}
}*root;
queue<ScapeTree *> ScapeTree :: bin;
queue<SegTree *> SegTree :: bin;
ScapeTree *BuildScapeTree(int l,int r,int arr[])
{
if(l > r) return NULL;
int mid = (l + r) >> 1;
SegTree *root = new (0,NULL,NULL)SegTree;
for(int i = l; i <= r; ++i)
root->Insert(0,RANGE,arr[i]);
ScapeTree *re = new (arr[mid],BuildScapeTree(l,mid - 1,arr),BuildScapeTree(mid + 1,r,arr),root,r - l + 1)ScapeTree;
return re;
}
int temp[MAX],top;
void DFS(ScapeTree *a)
{
if(a == NULL) return ;
DFS(a->son[0]);
temp[++top] = a->val;
DFS(a->son[1]);
a->root->Decomposition();
delete a;
}
void Rebuild(ScapeTree *&a)
{
top = 0;
DFS(a);
a = BuildScapeTree(1,top,temp);
}
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;
}
BZOJ 3065 带插入区间K小值 替罪羊树套线段树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。