Post 40

Veröffentlicht am

以前经常听说树套树很难写，今天写了一下感觉挺简单的啊。

最起码是1A233.

3196: Tyvj 1730 二逼平衡树

Description

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：
1.查询k在区间内的排名
2.查询区间内排名为k的值
3.修改某一位值上的数值
4.查询k在区间内的前驱(前驱定义为小于x，且最大的数)
5.查询k在区间内的后继(后继定义为大于x，且最小的数)

Input

第一行两个数 n,m 表示长度为n的有序序列和m个操作
第二行有n个数，表示有序序列
下面有m行，opt表示操作标号
若opt=1 则为操作1，之后有三个数l,r,k 表示查询k在区间[l,r]的排名
若opt=2 则为操作2，之后有三个数l,r,k 表示查询区间[l,r]内排名为k的数
若opt=3 则为操作3，之后有两个数pos,k 表示将pos位置的数修改为k
若opt=4 则为操作4，之后有三个数l,r,k 表示查询区间[l,r]内k的前驱
若opt=5 则为操作5，之后有三个数l,r,k 表示查询区间[l,r]内k的后继

Output

对于操作1,2,4,5各输出一行，表示查询结果

Sample Input

9 6
4 2 2 1 9 4 0 1 1
2 1 4 3
3 4 10
2 1 4 3
1 2 5 9
4 3 9 5
5 2 8 5

Sample Output

2
4
3
4
9

HINT

1.n和m的数据范围：n,m<=50000

2.序列中每个数的数据范围：[0,1e8]

3.虽然原题没有，但事实上5操作的k可能为负数

题解

这道题暂时学习的是经典的线段树套平衡树(Treap)的做法。

重在理解和认识这个数据结构。

我们对于线段树的每一个区间，用一颗Treap来维护，由于每个节点只在线段树的$\Theta(logn)$个区间里，所以平衡树最多也只需要维护$\Theta(nlogn)$，我一开始听说这种东西还不明白这到底是怎么搞得，看了看别人的实现发现非常简单。HPD也没有每条链单独开一颗线段树而是放在一颗线段树里处理的啊。

同样我们用一片Treap森林维护每个区间就可以啦。

由于每次查询只会分成$\Theta(logn)$个区间，每个区间用Treap做到$O(logn)$处理即可。

所以好像能用树套树维护的最重要一点和线段树一样依旧是满足可合并性。。这样一来就能想到根号算法的适用性之广了。。

具体来说：
操作一：查询区间内数的排名

满足子区间可加性，及查每个小区间有多少个比当前数小的，加起来+1即为排名

将查询区间分成$O(logn)$个区间，每个区间用Treap查询多少个比当前数小的（和查排名略有不同）

时间复杂度$O(log^2n)$

操作二：查询区间第k大

由于这个不满足区间可加性，因此不能直接利用树套树完成。

但是我们知道答案随k增大而增大，因此二分权值查询的排名有单调性。可以二分查找转化为第一问。

时间复杂度$O(log^3n)$

巨慢无比。。。

操作三：单点修改。

转化成删除原数加入新数。

由于每个元素最多在$O(logn)$个线段树区间内，每个区间的平衡树可以在$O(logn)$的时间里完成插入删除，所以时间复杂度是$O(log^2n)$

操作四和五

均满足子区间答案的可合并性质，因此对$O(logn)$个区间$O(logn)$查询前驱后继再分别取最大最小即可。

时间复杂度$O(log^2n)$

这样我们就完美的解决了这道问题。

当然200行代码才是最重要的233

Code：

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
187
188
189
190
191
192
193
194
195
196
197
198
199
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 100005
#define ls ch[0][x]
#define rs ch[1][x]
#define INF 2147483647

int val[maxn] , n , m;
namespace Treap
{
    int ch[2][maxn<<4] , sz[maxn<<4] , tot , ct[maxn<<4] , v[maxn<<4] , p[maxn<<4];
    inline void pushup(int x){
        sz[x] = ct[x] + sz[ls] + sz[rs];
    }
    inline int newnode(int k)
    {
        ++tot;
        sz[tot] = ct[tot] = 1 , v[tot] = k , p[tot] = rand()%998244353;
        return tot;
    }
    inline void rotate(int& x , int tp)
    {
        int s = ch[tp][x];
        ch[tp][x] = ch[tp^1][s];
        ch[tp^1][s] = x;
        sz[s] = sz[x];
        pushup(x);
        x = s;
    }
    void ins(int& x , int k)
    {
        if(!x){
            x = newnode(k);
            return ;
        }
        else ++sz[x];
        if(v[x] == k) ++ct[x];
        else if(v[x] > k) {
            ins(ls , k);
            if(p[ls] < p[x]) rotate(x , 0);
        }
        else{
            ins(rs , k);
            if(p[rs] < p[x]) rotate(x , 1);
        }
    }
    void del(int& x , int k)
    {
        if(!x) return ;
        if(v[x] == k)
        {
            if(ct[x] > 1) --ct[x] , --sz[x];
            else if(!ls || !rs) x = ls + rs;
            else if(p[ls] <= p[rs]) rotate(x,0) , del(x, k);
            else rotate(x,1) , del(x , k);
            return ;
        }
        --sz[x];
        if(v[x] > k) del(ls , k);
        else del(rs , k);
    }
    inline int qPre(int k , int x)
    {
        int ans = -INF;
        while(x)
        {
            if(v[x] < k) ans = v[x] , x = rs;
            else x = ls;
        }
        return ans;
    }
    inline int qNxt(int k , int x)
    {
        int ans = INF;
        while(x)
        {
            if(v[x] > k) ans = v[x] , x = ls;
            else x = rs;
        }
        return ans;
    }
    inline int Rank(int k , int x)
    {
        while(x)
        {
            if(sz[ls] < k && sz[ls] + ct[x] >= k) return v[x];
            if(sz[ls] < k)
               k -= sz[ls] + ct[x] , x = rs;
            else x = ls;
        }
        return INF;
    }
    inline int getRank(int k , int x)
    {
        int ans = 0;
        while(x)
        {
            if(v[x] == k) return ans + sz[ls];
            else if(v[x] > k) x = ls;
            else ans += sz[ls] + ct[x] , x = rs;
        }
        return ans;
    }
}

namespace SegmentTree
{
    int seg[maxn<<2] , sl[maxn<<2] , sr[maxn<<2];
    void build(int p , int l , int r)
    {
        sl[p] = l , sr[p] = r;
        for(int i = l ; i <= r ; ++i)
            Treap::ins(seg[p] , val[i]);
        if(l == r) return ;
        int mid = l + r >> 1;
        build(p << 1 , l , mid);
        build(p << 1 | 1 , mid + 1 , r);
    }
    void upd(int p , int pos , int v)
    {
        Treap::del(seg[p] , val[pos]);
        Treap::ins(seg[p] , v);
        if(sl[p] == sr[p]) return;
        int mid = sl[p] + sr[p] >> 1;
        if(pos <= mid) upd(p << 1 , pos , v);
        else upd(p << 1 | 1 , pos , v);
    }
    int qPre(int p , int l , int r , int v)
    {
        int mid = sl[p] + sr[p] >> 1 , ans = -INF;
        if(l <= sl[p] && sr[p] <= r)	return Treap::qPre(v , seg[p]);
        if(l <= mid) ans = std::max(ans , qPre(p << 1 , l , r , v));
        if(r > mid) ans = std::max(ans , qPre(p << 1 | 1 , l , r , v));
        return ans;
    }
    int qNxt(int p , int l , int r , int v)
    {
        int mid = sl[p] + sr[p] >> 1 , ans = INF;
        if(l <= sl[p] && sr[p] <= r) return Treap::qNxt(v , seg[p]);
        if(l <= mid) ans = std::min(ans , qNxt(p << 1 , l , r , v));
        if(r > mid ) ans = std::min(ans , qNxt(p << 1 | 1 , l , r , v));
        return ans;
    }
    int getRank(int p , int l , int r , int v)
    {
        if(l <= sl[p] && sr[p] <= r)	return Treap::getRank(v , seg[p]);
        int mid = sl[p] + sr[p] >> 1 , ans = 0;
        if(l <= mid) ans += getRank(p << 1 , l , r , v);
        if(r > mid ) ans += getRank(p << 1 | 1 , l , r , v);
        return ans;
    }
    int Rank(int l , int r , int v)
    {
        int L = 0 , R = INF , ans = INF;
        while(L <= R)
        {
            int mid = L + R >> 1;
            if(getRank(1 , l , r , mid) < v)
                ans = mid , L = mid + 1;
            else R = mid - 1;
        }
        return ans;
    }
    void print(int l , int r , int p)
    {
        if(l == r) 
        {
            printf("LEAF : %d %d %d\n",seg[p] , sl[p] , sr[p]);
            return ;
        }
        int mid = l + r >> 1;
        print(l,mid,p<<1);
        printf("THE RANGE: %d %d INFO : %d %d %d\n",l,r,seg[p],sl[p],sr[p]);
        print(mid+1,r,p<<1|1);
    }

}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1 ; i <= n ; ++i)
        scanf("%d",&val[i]);
    SegmentTree::build(1,1,n); // 1 is the root of SegmentTree
//	SegmentTree::print(1,n,1);
//	return 0;
    for(int i = 1; i <= m ; ++i)
    {
        int op , l , r , v;
        scanf("%d%d%d",&op,&l,&r);
        if(op == 1) scanf("%d",&v), printf("%d\n",SegmentTree::getRank(1,l,r,v) + 1);// the v rank number
        if(op == 2)  scanf("%d",&v),  printf("%d\n",SegmentTree::Rank(l,r,v));//the v biggest number,O(log^3n)
        if(op == 3)  SegmentTree::upd(1,l,r) , val[l] = r;
        if(op == 4) scanf("%d",&v) , printf("%d\n",SegmentTree::qPre(1,l,r,v));
        if(op == 5) scanf("%d",&v) , printf("%d\n",SegmentTree::qNxt(1,l,r,v));
    }
}

不过就是写的时间有点长，毕竟谨慎，用了将近三个小时写完qvq。

看看NOI组别还有什么是需要提前学习学习的qwq。