「BZOJ3065」带插入区间K小值

2014年9月30日28,90014

Description

从前有n只跳蚤排成一行做早操，每只跳蚤都有自己的一个弹跳力a[i]。跳蚤国王看着这些跳蚤国欣欣向荣的情景，感到非常高兴。这时跳蚤国王决定理性愉悦一下，查询区间k小值。他每次向它的随从伏特提出这样的问题: 从左往右第x个到第y个跳蚤中，a[i]第k小的值是多少。
这可难不倒伏特，他在脑袋里使用函数式线段树前缀和的方法水掉了跳蚤国王的询问。
这时伏特发现有些跳蚤跳久了弹跳力会有变化，有的会增大，有的会减少。
这可难不倒伏特，他在脑袋里使用树状数组套线段树的方法水掉了跳蚤国王的询问。（orz 主席树）
这时伏特发现有些迟到的跳蚤会插入到这一行的某个位置上，他感到非常生气，因为……他不会做了。
请你帮一帮伏特吧。
快捷版题意：带插入、修改的区间k小值在线查询。

Input

第一行一个正整数n，表示原来有n只跳蚤排成一行做早操。
第二行有n个用空格隔开的非负整数，从左至右代表每只跳蚤的弹跳力。
第三行一个正整数q，表示下面有多少个操作。
下面一共q行，一共三种操作对原序列的操作：（假设此时一共m只跳蚤）
1. Q x y k: 询问从左至右第x只跳蚤到从左至右第y只跳蚤中，弹跳力第k小的跳蚤的弹跳力是多少。
(1 <= x <= y <= m, 1 <= k <= y – x + 1)
2. M x val: 将从左至右第x只跳蚤的弹跳力改为val。
(1 <= x <= m)
3. I x val: 在从左至右第x只跳蚤的前面插入一只弹跳力为val的跳蚤。即插入后从左至右第x只跳蚤是我刚插入的跳蚤。
(1 <= x <= m + 1)

为了体现在线操作，设lastAns为上一次查询的时候程序输出的结果，如果之前没有查询过，则lastAns = 0。
则输入的时候实际是：
Q _x _y _k ——> 表示 Q _x^lastAns _y^lastAns _k^lastAns
M _x _val ——> 表示 M _x^lastAns _val^lastAns
I _x _val ——> 表示 I _x^lastAns _val^lastAns
简单来说就是操作中输入的整数都要异或上一次询问的结果进行解码。

(祝Pascal的同学早日转C++，就不提供pascal版的描述了。)

Output

对于每个询问输出回答，每行一个回答。

Sample Input

10
10 5 8 28 0 19 2 31 1 22
30
I 6 9
M 1 11
I 8 17
M 1 31
M 6 26
Q 2 7 6
I 23 30
M 31 7
I 22 27
M 26 18
Q 26 17 31
I 5 2
I 18 13
Q 3 3 3
I 27 19
Q 23 23 30
Q 5 13 5
I 3 0
M 15 27
Q 0 28 13
Q 3 29 11
M 2 8
Q 12 5 7
I 30 19
M 11 19
Q 17 8 29
M 29 4
Q 3 0 12
I 7 18
M 29 27

Sample Output

28
2
31
0
14
15
14
27
15
14

HINT

此题作为一个小小的研究来搞吧～做法有很多～不知道这题究竟有多少种做法。
请自觉O(log^2n)，我故意卡块状链表，块链A了的请受我深情一拜……
A掉的同学请在Discuss里面简要说下自己的做法吧～
原序列长度 <= 35000
插入个数 <= 35000，修改个数 <= 70000，查询个数 <= 70000 ,0 <= 每时每刻的权值 <= 70000
由于是OJ上的题，所以数据无梯度。为了防止卡OJ，本题只有4组数据。

题解

学习了一下替罪羊树，具体参见WJMZBMR《重量平衡树和后缀平衡树在信息学奥赛中的应用》

替罪羊树是一种不用旋转的平衡树，若一棵子树的左或右子树大小超过其大小55%-80%则暴力重构这棵子树，以此来维护平衡性，每个结点的期望重构次数是logn，实现可以自己脑补一下

在替罪羊树每个结点放一棵包含该子树所有结点的权值线段树，也就是平衡树套权值线段树

1、由于外层是平衡树，那么就能实现插入一个结点：找到它的位置，在根到其路径上所有结点的线段树中插入这个值

2、查询区间第K大：找到这个区间包含若干棵子树，拿出他们的根的权值线段树，一起做个二分

3、修改与插入类似

4、当外层平衡树失衡的时候重构之，将某个子树自下而上线段树合并

然后就是考验数据结构的能力了QAQ

由于内存不够，我们还需要回收垃圾，即对数组的重复使用

写的时候遇到了点麻烦，重构的时候我所有结点暴力插入了，所以我的复杂度是qlog^3n，否则应是qlog^2n

代码略长

#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define alpha 0.75
#define N 10000005
using namespace std;
inline int read()
{
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x;
}
int tmp;
int n,m,sz,lastans,root;
int v[70005],dfn[70005],rt[70005],ls[70005],rs[70005];
struct seg{int l,r,sum;}a[N];
vector<int> rec,t,p;
inline int newnode()
{
	if(!rec.size())return ++sz;
	else 
	{
		int k=rec.back();rec.pop_back();
		return k;
	}
}
void reclaim(int &x)
{
	if(!x)return;
	rec.push_back(x);
	reclaim(a[x].l);reclaim(a[x].r);
	a[x].sum=0;x=0;
}
void insert(int &k,int l,int r,int val,int f)
{
	if(!k)k=newnode();
	if(l==r){a[k].sum+=f;return;}
	int mid=(l+r)>>1;
	if(val<=mid)insert(a[k].l,l,mid,val,f);
	else insert(a[k].r,mid+1,r,val,f);
	a[k].sum=a[a[k].l].sum+a[a[k].r].sum;
	if(!a[k].sum)reclaim(k);
}
void build(int &k,int l,int r)
{
	if(l>r)return;
	if(l==r)
	{
		k=dfn[l];insert(rt[k],0,70000,v[k],1);return;
	}
	int mid=(l+r)>>1;k=dfn[mid];
	build(ls[k],l,mid-1);build(rs[k],mid+1,r);
    for(int i=l;i<=r;i++)
		insert(rt[k],0,70000,v[dfn[i]],1);
}
void del(int &x)
{
	if(!x)return;reclaim(rt[x]);
	del(ls[x]);p.push_back(x);del(rs[x]);
	x=0;
}
void rebuild(int &x)
{
	del(x);int s1=p.size();
	for(int i=1;i<=s1;i++)dfn[i]=p[i-1];
	build(x,1,s1);
	p.clear();
}
int modify(int k,int x,int val)
{
	insert(rt[k],0,70000,val,1);
	int t,L=a[rt[ls[k]]].sum;
	if(L+1==x){t=v[k];v[k]=val;}	
	else if(L>=x)t=modify(ls[k],x,val);
	else t=modify(rs[k],x-L-1,val);
	insert(rt[k],0,70000,t,-1);
	return t;
}
void query(int k,int l,int r)
{
	int L=a[rt[ls[k]]].sum,R=a[rt[k]].sum;
	if(l==1&&r==R){t.push_back(rt[k]);return;}
	if(l<=L+1&&r>=L+1)p.push_back(v[k]);
	if(r<=L)query(ls[k],l,r);
	else if(l>L+1)query(rs[k],l-L-1,r-L-1);
	else 
	{
		if(l<=L)query(ls[k],l,L);
		if(R>L+1)query(rs[k],1,r-L-1);
	}
}
int solve_query(int L,int R,int K)
{
	query(root,L,R);K--;
	int l=0,r=70000,s1=t.size(),s2=p.size();
	while(l<r)
	{
		int mid=(l+r)>>1,sum=0;
		for(int i=0;i<s1;i++)sum+=a[a[t[i]].l].sum;
		for(int i=0;i<s2;i++)
			if(p[i]>=l&&p[i]<=mid)sum++;
		if(K<sum)
		{
			for(int i=0;i<s1;i++)t[i]=a[t[i]].l;
			r=mid;
		}
		else 
		{
			for(int i=0;i<s1;i++)t[i]=a[t[i]].r;
			l=mid+1;K-=sum;
		}
	}
	t.clear();p.clear();
	return l;
}
void insert(int &k,int x,int val)
{
	if(!k)
	{
		k=++n;
		insert(rt[k],0,70000,val,1);
		v[k]=val;
		return;
	}
	insert(rt[k],0,70000,val,1);
	int L=a[rt[ls[k]]].sum;
	if(L>=x)insert(ls[k],x,val);
	else insert(rs[k],x-L-1,val);
	if(a[rt[k]].sum*alpha>max(a[rt[ls[k]]].sum,a[rt[rs[k]]].sum))
	{
		if(tmp)
		{
			if(ls[k]==tmp)rebuild(ls[k]);
			else rebuild(rs[k]);
			tmp=0;
		}
	}
	else tmp=k;
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)v[i]=read();
	for(int i=1;i<=n;i++)dfn[i]=i;
	build(root,1,n);
	m=read();
	char ch[2];int x,y,K;
	while(m--)
	{
		scanf("%s",ch);
		x=read();y=read();x^=lastans;y^=lastans;
		switch(ch[0])
		{
		case 'Q':K=read();K^=lastans;lastans=solve_query(x,y,K);printf("%d\n",lastans);break;
		case 'M':modify(root,x,y);break;
		case 'I':tmp=0;insert(root,x-1,y);if(tmp){tmp=0;rebuild(root);}break;
		}
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

#include<cstdio>

#include<vector>

#include<cstring>

#include<iostream>

#include<algorithm>

#define alpha 0.75

#define N 10000005

using namespace std;

inline int read()

{

int x=0;char ch=getchar();

while(ch<'0'||ch>'9')ch=getchar();

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x;

}

int tmp;

int n,m,sz,lastans,root;

int v[70005],dfn[70005],rt[70005],ls[70005],rs[70005];

struct seg{int l,r,sum;}a[N];

vector<int> rec,t,p;

inline int newnode()

{

if(!rec.size())return ++sz;

else

{

int k=rec.back();rec.pop_back();

return k;

}

void reclaim(int &x)

{

if(!x)return;

rec.push_back(x);

reclaim(a[x].l);reclaim(a[x].r);

a[x].sum=0;x=0;

}

void insert(int &k,int l,int r,int val,int f)

{

if(!k)k=newnode();

if(l==r){a[k].sum+=f;return;}

int mid=(l+r)>>1;

if(val<=mid)insert(a[k].l,l,mid,val,f);

else insert(a[k].r,mid+1,r,val,f);

a[k].sum=a[a[k].l].sum+a[a[k].r].sum;

if(!a[k].sum)reclaim(k);

}

void build(int &k,int l,int r)

{

if(l>r)return;

if(l==r)

{

k=dfn[l];insert(rt[k],0,70000,v[k],1);return;

}

int mid=(l+r)>>1;k=dfn[mid];

build(ls[k],l,mid-1);build(rs[k],mid+1,r);

for(int i=l;i<=r;i++)

insert(rt[k],0,70000,v[dfn[i]],1);

}

void del(int &x)

{

if(!x)return;reclaim(rt[x]);

del(ls[x]);p.push_back(x);del(rs[x]);

x=0;

}

void rebuild(int &x)

{

del(x);int s1=p.size();

for(int i=1;i<=s1;i++)dfn[i]=p[i-1];

build(x,1,s1);

p.clear();

}

int modify(int k,int x,int val)

{

insert(rt[k],0,70000,val,1);

int t,L=a[rt[ls[k]]].sum;

if(L+1==x){t=v[k];v[k]=val;}

else if(L>=x)t=modify(ls[k],x,val);

else t=modify(rs[k],x-L-1,val);

insert(rt[k],0,70000,t,-1);

return t;

}

void query(int k,int l,int r)

{

int L=a[rt[ls[k]]].sum,R=a[rt[k]].sum;

if(l==1&&r==R){t.push_back(rt[k]);return;}

if(l<=L+1&&r>=L+1)p.push_back(v[k]);

if(r<=L)query(ls[k],l,r);

else if(l>L+1)query(rs[k],l-L-1,r-L-1);

else

{

if(l<=L)query(ls[k],l,L);

if(R>L+1)query(rs[k],1,r-L-1);

}

int solve_query(int L,int R,int K)

{

query(root,L,R);K--;

int l=0,r=70000,s1=t.size(),s2=p.size();

while(l<r)

{

int mid=(l+r)>>1,sum=0;

for(int i=0;i<s1;i++)sum+=a[a[t[i]].l].sum;

for(int i=0;i<s2;i++)

if(p[i]>=l&&p[i]<=mid)sum++;

if(K<sum)

{

for(int i=0;i<s1;i++)t[i]=a[t[i]].l;

r=mid;

}

else

{

for(int i=0;i<s1;i++)t[i]=a[t[i]].r;

l=mid+1;K-=sum;

}

t.clear();p.clear();

return l;

}

void insert(int &k,int x,int val)

{

if(!k)

{

k=++n;

insert(rt[k],0,70000,val,1);

v[k]=val;

return;

}

insert(rt[k],0,70000,val,1);

int L=a[rt[ls[k]]].sum;

if(L>=x)insert(ls[k],x,val);

else insert(rs[k],x-L-1,val);

if(a[rt[k]].sum*alpha>max(a[rt[ls[k]]].sum,a[rt[rs[k]]].sum))

{

if(tmp)

{

if(ls[k]==tmp)rebuild(ls[k]);

else rebuild(rs[k]);

tmp=0;

}

else tmp=k;

}

int main()

{

n=read();

for(int i=1;i<=n;i++)v[i]=read();

for(int i=1;i<=n;i++)dfn[i]=i;

build(root,1,n);

m=read();

char ch[2];int x,y,K;

while(m--)

{

scanf("%s",ch);

x=read();y=read();x^=lastans;y^=lastans;

switch(ch[0])

{

case 'Q':K=read();K^=lastans;lastans=solve_query(x,y,K);printf("%d\n",lastans);break;

case 'M':modify(root,x,y);break;

case 'I':tmp=0;insert(root,x-1,y);if(tmp){tmp=0;rebuild(root);}break;

}

return 0;

}

« 「BZOJ3674」可持久化并查集加强版「BZOJ3110」[ZJOI2013] K大数查询 »

何肥

黄学长好，我是HN的hf，求问还有其他的做法么？？

肚子

貌似还可以treap套线段树吧。。。你可以去参考vfk的博客。。。

O(n!)

黄学长，请问这个代码为什么是log三方的呢？log方的怎么改呢？

hzwer

我重构的时候暴力插入了，线段树合并是log方的

O(n!)

可是感觉这个线段树不算主席树，不能复用空间，怎么启发式合并呢？

O(n!)

Orz黄学长原来还可以这样合并谢谢

黄维

学长求教log方的线段树合并呀

hzwer

http://wenku.baidu.com/link?url=k8_Jh515k1qjxXKu5Vxug-5jqTOXY9e4QBmCfl-BGi1a2uu-K3ldXpleMFmeeozdKx44n6KvGY7z4FK7xKQBzvrXIS25ir0aChwWN9yXHBW

黄维

QAQ

if(a[rt[k]].sum*alpha>max(a[rt[ls[k]]].sum,a[rt[rs[k]]].sum))这是为什么呢

hzwer

这是判断平衡树的某个子树是否失去平衡

hzwer

QAQ

sqd

蒟蒻求(稍微详一点点, 就一点点嘛, 至少给个搜索关键字嘛)解Orz

hzwer

0.0 之前没看到。。。我补充了一些

hzwer.com _ Home | http://hzwer.com

「BZOJ3065」带插入区间K小值

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论