OI题解 - K小值查询[BZOJ 4923] | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI题解 - K小值查询[BZOJ 4923]

发表于 更新于 分类于 Valine：

老师开的“新年大礼包”的第一个礼物~

『题目』

（终于不用翻译题目了……）

〔传送门〕

『解析』

因为要求第 k 小，属于平衡树一类的操作（虽然SPLAY并不是平衡树）；又因为有类似于“区间减”的操作，像线段树一样，所以我们用到了SPLAY。

因为要用查找第 k 小的函数 Select()，这里的 SPLAY 还必须维护二叉排序树性质。然后又因为有区间操作，我们要用到类似于线段树的“懒标记”操作 lzy。

我们发现在对于操作2，不难想到先把 $k+1$ 的前驱（就是小于等于 $k$ 的最大点）splay到根节点，这样的话根节点的右子树就是严格大于 $k$ 的数了。但是我们发现区间 $(k,2k]$ 的数在减去 $k$ 后会小于 $k$ ，也就是与 $k$ 相对大小改变，而 $(2k,\infty)$ 内的数与 $k$ 的相对大小并不会改变。

看来要分成两类讨论——
① 因为 $(k,2k]$ 的数会从 $k$ 的右子树转移到 $k$ 的左子树（因为相对大小转变了嘛），所以我们不如把 $(k,2k]$ 的数全部拿出来后将它们从 SPLAY 里删去，将值减去 $k$ 后再插入到 SPLAY 里；
② 因为 $(2k,\infty)$ 内的数还是在 $k$ 的右子树，所以只需要打一个懒标记就可以了。

至于怎么把 $(k,2k]$,$(2k,\infty)$ 拿出来，我们可以先把 $k+1$ 的前驱SPLAY到根的位置，再把 $2k$ SPLAY 到根的下面，然后“根 的 右儿子 的左子树”就是 $(k,2k]$ 的数，“左子树”就是 $(2k,\infty)$ 的数。

一些细节问题：
① 因为打了懒标记，所以 SPLAY 里有一个懒标记下传 PushDown() 操作，记得在每次进行与值相关的计算时将当前点 PushDown！
② 在这里我采用的是“如果有两个数相同，则较早被插入到 SPLAY 里的数在另一个数的左子树内”。
③ 不知道如果直接开这么多的节点会不会爆炸……我采用了删点回收的方式，即在操作 2 删除节点后将删除节点的位置储存下来，再将这些位置重新利用~
④ 为了防止找最小值的前驱或最大值的后继找到空节点会 RE，插入极大值和极小值作哨兵节点！

『源代码』

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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
/*Lucky_Glass*/
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=100000;
struct SPLAYTREE{
	struct NODE{
		NODE *ch[2],*fa;
		ll key,lzy; //键值、懒标记
		int siz; //大小
	}nod[N+7],*root,*ncnt,*NIL;
	inline void Rebuild(){ //初始化
		NIL=ncnt=&nod[0];
		root=NIL->ch[0]=NIL->ch[1]=NIL->fa=NIL;
	}
	inline NODE *NewNode(ll key){ //新建节点
		NODE *p=++ncnt;
		p->ch[0]=p->ch[1]=p->fa=NIL;
		p->key=key;p->lzy=0;p->siz=1;
		return p;
	}
	inline void PushUp(NODE *rt){ //统计大小
		rt->siz=rt->ch[1]->siz+rt->ch[0]->siz+1;
	}
	inline void PushDown(NODE *rt){ //懒标记下传
		if(rt->lzy){
			rt->key-=rt->lzy; //注意操作顺序
			if(rt->ch[0]!=NIL) rt->ch[0]->lzy+=rt->lzy;
			if(rt->ch[1]!=NIL) rt->ch[1]->lzy+=rt->lzy;
			rt->lzy=0;
		}
	}
	inline void Rotate(NODE *x){
		NODE *y=x->fa;
		int dir=(y->ch[0]==x);
		x->fa=y->fa;if(y->fa!=NIL) y->fa->ch[y->fa->ch[1]==y]=x;
		y->ch[!dir]=x->ch[dir];if(x->ch[dir]!=NIL) x->ch[dir]->fa=y;
		x->ch[dir]=y;y->fa=x;
		if(root==y) root=x;
		PushUp(y);
	}
	void Splay(NODE *x,NODE *rt){
		NODE *y,*z;
		while(x->fa!=rt){
			y=x->fa;z=y->fa;
			if(z==rt) Rotate(x);
			else{
				if((z->ch[0]==y)^(y->ch[0]==x)) Rotate(x);
				else Rotate(y);
				Rotate(x);
			}
		}
	}
	NODE *renod; //要用来回收利用的节点的位置
	inline NODE *ReNode(ll key){ //回收利用节点（即用新的信息替换掉回收的节点的信息）
		NODE *p=renod;
		p->ch[0]=p->ch[1]=p->fa=NIL;
		p->key=key;p->lzy=0;p->siz=1;
		return p;
	}
	inline void Insert(NODE *&rt,NODE *pre,ll key,bool rebegin){
		if(rt==NIL){
			if(rebegin) rt=ReNode(key); //rebegin 标记了当前是否要新建节点或是要回收一个节点
			else rt=NewNode(key);
			rt->fa=pre;
			Splay(rt,NIL);
			return;
		}
		PushDown(rt); /*!!!*/
		rt->siz++;
		int dir=(key>rt->key);
		Insert(rt->ch[dir],rt,key,rebegin);
	}
	inline NODE *FindPre(NODE *rt,ll key){ //找前驱（严格小于）
        NODE *p;
        PushDown(rt); /*!!!*/
        if(rt==NIL) return NIL;
        if(key>rt->key){
            p=FindPre(rt->ch[1],key);
            if(p==NIL) p=rt,Splay(p,NIL);
        }
        else p=FindPre(rt->ch[0],key);
        return p;
    }
    inline NODE *FindNxt(NODE *rt,ll key){ //找后继（严格大于）
        NODE *p;
        PushDown(rt); /*!!!*/
        if(rt==NIL) return NIL;
        if(key<rt->key){
            p=FindNxt(rt->ch[0],key);
            if(p==NIL) p=rt,Splay(p,NIL);
        }
        else p=FindNxt(rt->ch[1],key);
        return p;
    }
	NODE *lst[N+7];int lstsiz; //储存删除的点的位置
	inline void GetList(NODE *rt){ //找到将要删除的点并储存位置
		if(rt==NIL) return;
		PushDown(rt);
		lst[lstsiz++]=rt;
		GetList(rt->ch[0]);
		GetList(rt->ch[1]);
	}
	void Modify(ll k){ //操作2
		NODE *x=FindPre(root,k+1),*y=FindNxt(root,2*k);
		Splay(x,NIL);Splay(y,x);
		lstsiz=0;
		GetList(y->ch[0]);
		int delsiz=y->ch[0]->siz; //删去的节点总数
		NODE *pos=y->ch[0];y->ch[0]=NIL; //其实只用断开 y 和 y的左儿子
		pos=pos->fa;
		while(pos!=NIL) pos->siz-=delsiz,pos=pos->fa; //更新节点的子树大小
		for(int i=0;i<lstsiz;i++)
			renod=lst[i],Insert(root,NIL,lst[i]->key-k,true); //将值减去k再插入
		y->key-=k;
		y->ch[1]->lzy+=k; //右子树只用打懒标记
	}
	NODE *Select(int rnk,NODE *rt){
		NODE *p=root;
		while(true){
			PushDown(p); /*!!!*/
			if(rnk==p->ch[0]->siz+1) break;
			if(rnk<p->ch[0]->siz+1) p=p->ch[0];
			else rnk-=p->ch[0]->siz+1,p=p->ch[1];
		}
		Splay(p,rt);
		return p;
	}
}splay;
int main(){
	int n,m;scanf("%d%d",&n,&m);
	splay.Rebuild();
	splay.Insert(splay.root,splay.NIL,-(1ll<<50),false);
	splay.Insert(splay.root,splay.NIL,(1ll<<50),false);
	for(int i=0,key;i<n;i++){
		scanf("%d",&key);
		splay.Insert(splay.root,splay.NIL,key,false);
	}
	while(m--){
		int opt;ll x;scanf("%d%lld",&opt,&x);
		if(opt==1){
			x++;
			SPLAYTREE::NODE *res=splay.Select(x,splay.NIL);
			printf("%lld\n",res->key);
		}
		else splay.Modify(x);
	}
	return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com ，欢迎提问~