BZOJ 3065 带插入区间K小值
声明：本人第一篇树套树blog ， 由于看二逼平衡树的码量太大， 选择了这个题。结果发现是一道平衡树套权值线段树的题目。。心里mmp-ing…..
重点收获：
经过一顿被(%)D之后， 同届神犇JZYshuraK同学提出了一个问题：为什么对于这道题来说， 必须把平衡树放在外层， 不能放在内层？ 像我这种蒟蒻。。连正解都搞不懂， 还去想其他算法为什么是“错”的？呵呵呵。。愉快的被挂了起来。另一同届神犇EM_LGH却随口说出了答案：因为线段树的形态改变了啊， 需要重构。（暗自拍大腿ing…..为什么这都想不到？）终于找到自己菜的诸多原因之一了：没有考虑事情的反面， 只关注正解， 却忽略了逐一排除错误思想的过程。
据JZYshuraK同学介绍：这个东东其实也可以反过来， 不过要用什么ZKW线段树。。。
题目讲解：
我们考虑要维护的东西， 和题目中的操作：
1.在数列中一个数之前插入一个数。
2.修改一个数的值。
3.查询$[l, r]$区间k小值。
4.强制在线。
单点插入操作需要一种平衡树来实现。 还得需要又一个维护无序序列的数据结构， 用来查询区间$k$小值。 平衡树需要放在外层， 且我们需要一种不太复杂（不用太多旋转的）， 但是只需能维护单点信息的平衡树即可。显然替罪羊树比较适合。那么我们把替罪羊树放在外层。内层需要一个权值线段树。外层的替罪羊树每个节点维护自己对应的权值线段树和整棵子树所有权值的权值线段树。
插入/修改时需要把经过的节点的权值线段树拿出来， 然后按照权值线段树的查询方式， 在树上二分即可。
对于重构：当外层的替罪羊树达到重构条件时， 我们需要重构这棵树。优化：当多个地方需要重构时， 可以直接重构最上面的那个节点， 这样可以节省时间。
另外， 这个题需要内存回收。
附代码：
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define m 70000
#define N 70010
using namespace std;
struct scg
{
int v, ls, rs, si, wr, tr;
}a[N];
struct seg
{
int ls, rs, si;
}b[20000010];
queue <int > q;
char str[5];
int root, n, pos[N], tot, qr[100], qt;
void update(int p, int a, int l, int r, int &x)
{
if(!x)
{
x = q.front();
q.pop();
}
b[x].si += a;
if(!b[x].si)
{
x = 0;
return ;
}
if(l == r)
return ;
int mid = (l + r) >> 1;
if(p <= mid)
update(p, a, l, mid, b[x].ls);
else
update(p, a, mid + 1, r, b[x].rs);
}
void del(int &x)
{
if(!x)
return ;
q.push(x);
del(b[x].ls);
del(b[x].rs);
b[x].si = 0;
x = 0;
}
int query(int k, int l, int r)
{
if(l == r)
return l;
int mid = (l + r) >> 1;
int sum = 0;
for(int i = 1;i <= qt;i ++)
sum += b[b[qr[i]].ls].si;
if(k <= sum)
{
for(int i = 1;i <= qt; i ++)
qr[i] = b[qr[i]].ls;
return query(k, l, mid);
}
else
{
for(int i = 1;i <= qt;i ++)
qr[i] = b[qr[i]].rs;
return query(k - sum, mid + 1, r);
}
}
int build(int l, int r)
{
if(l > r)
return 0;
int mid = (l + r) >> 1;
for(int i = l;i <= r; i ++)
update(a[pos[i]].v, 1, 0, m, a[pos[mid]].tr);
a[pos[mid]].ls = build(l, mid - 1);
a[pos[mid]].rs = build(mid + 1, r);
a[pos[mid]].si = r - l + 1;
return pos[mid];
}
void dfs(int &x)
{
if(!x)
return ;
dfs(a[x].ls);
pos[++ tot] = x;
dfs(a[x].rs);
a[x].si = 0;
del(a[x].tr);
x = 0;
}
void insert(int p, int &x, int v, bool flag)
{
if(!x)
{
x = ++ n;
a[x].v = v;
a[x].si = 1;
update(v, 1, 0, m, a[x].wr);
update(v, 1, 0, m, a[x].tr);
return ;
}
bool tag;
update(v, 1, 0, m, a[x].tr);
a[x].si ++;
if(p <= a[a[x].ls].si)
{
tag = ((a[a[x].ls].si + 1) * 4 > (a[x].si + 1) * 3);
insert(p, a[x].ls, v, tag || flag);
}
else
{
tag = ((a[a[x].rs].si + 1) * 4 > (a[x].si + 1) * 3);
insert(p - a[a[x].ls].si - 1, a[x].rs, v, tag || flag);
}
if(!flag && tag)
{
tag = 0;
dfs(x);
x = build(1, tot);
}
}
int find(int p, int x)
{
if(p <= a[a[x].ls].si)
return find(p, a[x].ls);
else
if(p > a[a[x].ls].si + 1)
return find(p - a[a[x].ls].si - 1, a[x].rs);
else
return a[x].v;
}
void modify(int p, int x, int v1, int v2)
{
update(v1, -1, 0, m, a[x].tr);
update(v2, 1, 0, m, a[x].tr);
if(p <= a[a[x].ls].si)
modify(p, a[x].ls, v1, v2);
else
if(p > a[a[x].ls].si + 1)
modify(p - a[a[x].ls].si - 1, a[x].rs, v1, v2);
else
{
del(a[x].wr);
update(v2, 1, 0, m, a[x].wr);
a[x].v = v2;
}
}
void split(int b, int e, int x)
{
if(b <= 1 && e >= a[x].si)
{
qr[++ qt] = a[x].tr;
return ;
}
if(b <= a[a[x].ls].si + 1 && e >= a[a[x].ls].si + 1)
qr[++ qt] = a[x].wr;
if(b <= a[a[x].ls].si)
split(b, e, a[x].ls);
if(e > a[a[x].ls].si + 1)
split(b - a[a[x].ls].si - 1, e - a[a[x].ls].si - 1, a[x].rs);
}
int main()
{
for(int i = 1; i <= 20000000; i ++)
q.push(i);
scanf("%d",&n);
for(int i = 1; i <= n; i ++)
{
scanf("%d", &a[i].v);
update(a[i].v, 1, 0, m, a[i].wr);
pos[i] = i;
}
root = build(1, n);
int k;
int las = 0;
scanf("%d", &k);
while(k --)
{
int x, y, z;
scanf("%s%d%d", str, &x, &y);
x ^= las;
y ^= las;
if(str[0] == 'Q')
{
qt = 0;
split(x, y, root);
scanf("%d", &z);
z ^= las;
printf("%d\n", las = query(z, 0, m));
}
else
if(str[0] == 'M')
modify(x, root, find(x, root), y);
else
insert(x - 1, root, y, 0);
}
return 0;
}
版权声明：本文为0724-zcsblog原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。