抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

P3380 【模板】二逼平衡树（树套树）

发布于：2019年7月13日

传送门
树套树模板题（线段树套FHQTreap\rm FHQ Treap）
一开始听说FHQTreap\rm FHQ Treap常数大，会TLE\rm TLE，就没敢写，最后发现FHQTreap\rm FHQ Treap还是能过的。

好了步入正题：
考虑在线段树的每个节点开一棵FHQTreap\rm FHQ Treap，维护的是线段树左右端点[l,r][l,r]所代表的区间al...ara_l...a_r
这样不会MLE\rm MLE，因为线段树最多有log⁡n\log n层，而每一层就算填满也只有O(n)O(n)的空间，所以总空间复杂度是O(nlog⁡n)O(n \log n)，注意数组要开这么大

1.1.建树：对于节点[l,r][l,r]，暴力插入a[l]...a[r]a[l]...a[r]，时间复杂度O(nlog⁡2n)O(n\log^2n)。
2.2.替换a[pos]a[pos]为kk：对于包含pospos的区间[l,r][l,r]，先删除a[pos]a[pos]，再加入kk，时间复杂度O(log⁡2n)O(\log^2n)。
3.3.查询区间中numnum的排名：我们发现：numnum的排名为区间中小于numnum的数的数量+1+1，又发现线段树的区间查询操作其实将查询区间[L,R][L,R]分成许多不相交的小区间，根据这个，我们把numnum在小区间的排名−1-1，得到在小区间中小于numnum的数的数量，最后相加，发现小于numnum的数的数量不会重复计算，于是把和+1+1，得到numnum在区间[L,R][L,R]的排名，时间复杂度O(log⁡2n)O(\log^2n)
这里很容易跳进的坑：不能把numnum在小区间中的排名相加，否则numnum会重复算很多次
4.4.查询区间第kk大的数：因为FHQTreap\rm FHQ Treap只能查询numnum的排名，所以考虑二分numnum，时间复杂度O(log⁡3n)O(\log^3n)，查询numnum排名O(log⁡2n)O(\log^2n)，二分O(log⁡n)O(\log n)。
（当然按照子树大小Split\rm Split，FHQTreap\rm FHQTreap也阔以支持查询第kk大，详情请戳这里）
5.5.查询区间中，numnum的前驱：直接把小区间中numnum的所有前驱取个maxmax。
6.6.查询区间中，numnum的后继：类似5.5.

注意要判断numnum的前驱后继是否存在，若不存在，相应地输出INF/−INF\rm INF/-INF。
还有修改操作做完后，要执行a[pos]=ka[pos]=k，修改aa数组。

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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
#include <bits/stdc++.h>
#define MAXN 50005
#define MAXM 10000005
#define INF 0x7fffffff
using namespace std;
inline int read() {
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9') {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9') {
        x=(x*10)+(ch-'0');
        ch=getchar();
    }
    return x*f;
}
int a[MAXN];
struct node{
	int l,r;
	int val;//每个点的权值 
	int pri;//优先级（随机生成）
	int sz;
}tree[MAXM];
int tot;
struct FHQ_Treap{
	#define lc(i) tree[i].l
	#define rc(i) tree[i].r
	inline void Update(int x){tree[x].sz=tree[lc(x)].sz+tree[rc(x)].sz+1;}
	inline int New(int v){
		tree[++tot].val=v,tree[tot].pri=rand(),tree[tot].sz=1;
		return tot;
	}
	int Merge(int x,int y){
		if (!x||!y) return x+y;
		if (tree[x].pri<tree[y].pri){
            rc(x)=Merge(rc(x),y),Update(x);
            return x;
        }
		else{
            lc(y)=Merge(x,lc(y)),Update(y);
			return y;
        }
	}
	void Split(int i,int k,int &x,int &y){
		if (!i) x=y=0;
		else {
			if (tree[i].val<=k){x=i,Split(rc(i),k,rc(i),y);}
			else{y=i,Split(lc(i),k,x,lc(i));}
			Update(i);
		}
	}
    int root,x,y,z;
    inline void Add(int num){
		Split(root,num,x,y);
		root=Merge(x,Merge(New(num),y));
    }
    inline void Del(int num){
		Split(root,num,x,z);
		Split(x,num-1,x,y);
		y=Merge(lc(y),rc(y));
		root=Merge(Merge(x,y),z);
    }
    inline int Rank(int num){//获得num排名
        Split(root,num-1,x,y);
        int temp=tree[x].sz+1;
		root=Merge(x,y);
        return temp;
    }
    inline int Kth(int i,int rk){
    	if (rk<=tree[lc(i)].sz) return Kth(lc(i),rk);
    	if (rk==tree[lc(i)].sz+1) return tree[i].val;
    	return Kth(rc(i),rk-tree[lc(i)].sz-1);
	}
	inline int Pre(int num){
		Split(root,num-1,x,y);
		int ans=tree[x].sz?Kth(x,tree[x].sz):-INF;
		root=Merge(x,y);
		return ans;
	}
	inline int Nex(int num){
		Split(root,num,x,y);
		int ans=tree[y].sz?Kth(y,1):INF;
		root=Merge(x,y);
		return ans;
	}
    inline void BuildTree(int l,int r){
        for (register int i=l;i<=r;++i){Add(a[i]);}
    }
    #undef lc
    #undef rc
}T[MAXN<<2];
int n;
namespace SegmentTree{
    #define lc i<<1
    #define rc i<<1|1
    void Build(int i,int l,int r){
        T[i].BuildTree(l,r);
        if (l==r) return ;
        int mid=(l+r)>>1;
        Build(lc,l,mid);
        Build(rc,mid+1,r);
    }
    int qrank(int i,int l,int r,int L,int R,int val){
        if (L<=l&&r<=R) {
            return T[i].Rank(val)-1;
        }
        int mid=(l+r)>>1;
        int ans=0;
        if (L<=mid) ans+=qrank(lc,l,mid,L,R,val);
        if (mid<R) ans+=qrank(rc,mid+1,r,L,R,val);
        return ans;
    } 
    inline int qval(int l,int r,int rk){
        int L=0,R=0x7fffffff;
        int ans=-1;
        while (L<=R){
            int mid=(L+R)>>1;
            if (qrank(1,1,n,l,r,mid)<rk) ans=mid,L=mid+1;
            else R=mid-1;
        }
        return ans;
    }
    void Update(int l,int r,int i,int k,int pos){//a[pos]=>k
        T[i].Del(a[pos]),T[i].Add(k);
        if (l==r) return ;
        int mid=(l+r)>>1;
        if (pos<=mid) Update(l,mid,lc,k,pos);
        else Update(mid+1,r,rc,k,pos);
    }
    int qpre(int i,int l,int r,int L,int R,int val){
        if (L<=l&&r<=R){
            return T[i].Pre(val);
        }
        int mid=(l+r)>>1;
        int ans=-0x7fffffff;
        if (L<=mid) ans=max(ans,qpre(lc,l,mid,L,R,val));
        if (mid<R) ans=max(ans,qpre(rc,mid+1,r,L,R,val));
        return ans;
    }
    int qnex(int i,int l,int r,int L,int R,int val){
        if (L<=l&&r<=R){
            return T[i].Nex(val);
        }
        int mid=(l+r)>>1;
        int ans=0x7fffffff;
        if (L<=mid) ans=min(ans,qnex(lc,l,mid,L,R,val));
        if (mid<R) ans=min(ans,qnex(rc,mid+1,r,L,R,val));
        return ans;
    }
    #undef lc
    #undef rc
}
using namespace SegmentTree;
int main(){
    n=read();int m=read();
    for (register int i=1;i<=n;++i){
        a[i]=read();
    }
    Build(1,1,n);
    while (m--){
        int opr=read();
        if (opr==1){
            int l=read(),r=read(),k=read();
            printf("%d\n",qrank(1,1,n,l,r,k)+1);
        }
        else if (opr==2){
            int l=read(),r=read(),k=read();
            printf("%d\n",qval(l,r,k));
        }
        else if (opr==3){
            int pos=read(),k=read();
            Update(1,n,1,k,pos),a[pos]=k;
        }
        else if (opr==4){
            int l=read(),r=read(),k=read();
            printf("%d\n",qpre(1,1,n,l,r,k));
        }
        else if (opr==5){
            int l=read(),r=read(),k=read();
            printf("%d\n",qnex(1,1,n,l,r,k));
        }
    }
}

相关文章
CF280D k-Maximum Subsequence Sum 线段树SP19543 GSS8 - Can you answer these queries VIIIP3919 【模板】可持久化数组（可持久化线段树/平衡树）BZOJ 4025 二分图基本概念

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://gaisaiyuno.github.io/archives/48c38374.html

更新于：2022年6月14日

题解

线段树

毒瘤

模板

FHQ Treap

评论