关键词:  线段树  树状数组  Treap(可持久化平衡树) 相关题目:  线段树   Treap(普通化平衡树)

线段树 1

题目描述

    如题,已知一个数列,你需要进行下面两种操作:     1.将某区间每一个数加上x     2.求出某区间每一个数的和

输入输出格式

输入格式:     第一行包含两个整数N、M,分别表示该数列数字的个数和操作的总个数。
    第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。
    接下来M行每行包含3或4个整数,表示一个操作,具体如下:
    操作1: 格式:1 x y k 含义:将区间[x,y]内每个数加上k
    操作2: 格式:2 x y 含义:输出区间[x,y]内每个数的和

输出格式:
    输出包含若干行整数,即为所有操作2的结果。

模板代码

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
/*----------线段树----------
-----区间修改+区间查询-----
------lazytag 递归版------*/

typedef long long ll;
ll ans,a[100010];

struct Segtree{
int l[400010],r[400010];
ll lazy[400010],sum[400010];

inline void push(int k){
int mid=(l[k]+r[k])>>1;
lazy[k<<1]+=lazy[k],lazy[k<<1|1]+=lazy[k];//传递lazy
sum[k<<1]+=(mid-l[k]+1)*lazy[k],sum[k<<1|1]+=(r[k]-mid)*lazy[k];//更新值
lazy[k]=0;
}//调整lazytag

inline void build(int index,int left,int right){
l[index]=left,r[index]=right;
if(left==right){
sum[index]=a[left];
return ;
}
int mid=(left+right)>>1;
build(index<<1,left,mid);
build(index<<1|1,mid+1,right);
sum[index]=sum[index<<1]+sum[index<<1|1];
}//构造线段树

inline void modify(int index,int left,int right,ll k){
if(l[index]==left && r[index]==right){
sum[index]+=k*(right-left+1);
lazy[index]+=k;
return ;
}//找到目标
if(lazy[index]) push(index);

int mid=(l[index]+r[index])>>1;
if(mid>=right) modify(index<<1,left,right,k);else
if(mid<left) modify(index<<1|1,left,right,k);//一种方案不符合
else {
modify(index<<1,left,mid,k);
modify(index<<1|1,mid+1,right,k);
}
sum[index]=sum[index<<1]+sum[index<<1|1];
}//修改区间

inline void query(int index,int left,int right){
if(l[index]==left && r[index]==right){
ans+=sum[index];
return ;
}//找到目标区间
if(lazy[index]) push(index);

int mid=(l[index]+r[index])>>1;
if(mid>=right) query(index<<1,left,right);else
if(mid<left) query(index<<1|1,left,right);
else {
query(index<<1,left,mid);
query(index<<1|1,mid+1,right);
}
}//修改区间
};
Segtree T;

线段树 2

题目描述

    如题,已知一个数列,你需要进行下面三种操作:

  1. 将某区间每一个数乘上x
  2. 将某区间每一个数加上x
  3. 求出某区间每一个数的和

输入输出格式

输入格式:     第一行包含三个整数N、M、P,分别表示该数列数字的个数、操作的总个数和模数。
    第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。
    接下来M行每行包含3或4个整数,表示一个操作,具体如下:

    操作1: 格式:1 x y k 含义:将区间[x,y]内每个数乘上k
    操作2: 格式:2 x y k 含义:将区间[x,y]内每个数加上k
    操作3: 格式:3 x y 含义:输出区间[x,y]内每个数的和对P取模所得的结果

输出格式:
    输出包含若干行整数,即为所有操作3的结果。

模板代码

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
#include<cstdio>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)
typedef long long ll;
template <typename T>inline void read(T &x){
x=0;
int f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while ('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
x*=f;
}
template <typename T>inline void put(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) put(x/10);
putchar(x%10+48);
}

int n,m,x,y,k,opt,p;
ll ans,a[100020];

struct node{
int l,r;
ll lazy1,lazy2,num;
}t[400200];

inline void push(int k){
int mid=(t[k].l+t[k].r)>>1;
t[k<<1].num=(t[k<<1].num*t[k].lazy2+t[k].lazy1*(mid-t[k].l+1))%p;
t[k<<1|1].num=(t[k<<1|1].num*t[k].lazy2+t[k].lazy1*(t[k].r-mid))%p;//传递num
t[k<<1].lazy1=(t[k<<1].lazy1*t[k].lazy2+t[k].lazy1)%p;
t[k<<1|1].lazy1=(t[k<<1|1].lazy1*t[k].lazy2+t[k].lazy1)%p;//传递lazy1
t[k<<1].lazy2=(t[k<<1].lazy2*t[k].lazy2)%p;
t[k<<1|1].lazy2=(t[k<<1|1].lazy2*t[k].lazy2)%p;//传递lazy2
t[k].lazy1=0,t[k].lazy2=1;
}//调整lazytag+num传递

inline void build(int index,int left,int right){
t[index].l=left,t[index].r=right,t[index].lazy2=1;
if(left==right){
t[index].num=a[left];
return ;
}
int mid=(left+right)>>1;
build(index<<1,left,mid);
build(index<<1|1,mid+1,right);
t[index].num=(t[index<<1].num+t[index<<1|1].num)%p;
}//构造线段树

inline void mdy1(int index,int left,int right,ll k){
if(t[index].l==left && t[index].r==right){
t[index].num=t[index].num*k%p;
t[index].lazy1=t[index].lazy1*k%p;
t[index].lazy2=t[index].lazy2*k%p;
return ;
}
push(index);
int mid=(t[index].l+t[index].r)>>1;
if(mid>=right) mdy1(index<<1,left,right,k);else
if(mid<left) mdy1(index<<1|1,left,right,k);
else {
mdy1(index<<1,left,mid,k);
mdy1(index<<1|1,mid+1,right,k);
}
t[index].num=(t[index<<1].num+t[index<<1|1].num)%p;
}//修改区间(+)

inline void mdy2(int index,int left,int right,ll k){
if(t[index].l==left && t[index].r==right){
t[index].num=(t[index].num+k*(right-left+1))%p;
t[index].lazy1=(t[index].lazy1+k)%p;
return ;
}
push(index);
int mid=(t[index].l+t[index].r)>>1;
if(mid>=right) mdy2(index<<1,left,right,k);else
if(mid<left) mdy2(index<<1|1,left,right,k);
else {
mdy2(index<<1,left,mid,k);
mdy2(index<<1|1,mid+1,right,k);
}
t[index].num=(t[index<<1].num+t[index<<1|1].num)%p;
}//区间修改(*)

inline void query(int index,int left,int right){
if(t[index].l==left && t[index].r==right){
ans=(ans+t[index].num)%p;
return ;
}//找到目标区间
push(index);
int mid=(t[index].l+t[index].r)>>1;
if(mid>=right) query(index<<1,left,right);else
if(mid<left) query(index<<1|1,left,right);
else {
query(index<<1,left,mid);
query(index<<1|1,mid+1,right);
}
}//修改区间

int main(){
read(n),read(m),read(p);
rep(i,1,n) read(a[i]);
build(1,1,n);
while(m--){
read(opt);
switch(opt){
case 1:{
read(x),read(y),read(k);
mdy1(1,x,y,k);
break;
}
case 2:{
read(x),read(y),read(k);
mdy2(1,x,y,k);
break;
}
case 3:{
read(x),read(y);
ans=0; query(1,x,y);
put(ans);putchar('\n');
break;
}
}
}
}

Treap(普通平衡树)

题目描述

    您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作:
    插入x数
    删除x数(若有多个相同的数,因只删除一个)
    查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数,因输出最小的排名)
    查询排名为x的数
    求x的前驱(前驱定义为小于x,且最大的数)
    求x的后继(后继定义为大于x,且最小的数)

输入输出格式

输入格式:
    第一行为n,表示操作的个数,下面n行每行有两个数opt和x,opt表示操作的序号( 1≤opt≤6 )

输出格式:
    对于操作3,4,5,6每行输出一个数,表示对应答案

构造思路

    Treap=tree+heap 即用一棵二叉树维护其中序遍历为升序的性质,这时可以用权值 v 保证,但考虑到最坏的情况,可能排成一条链的形式,此时复杂度为 Θ(n)(n) 。所以用heap维护堆的性质,用每个节点的随机值 rnd 保证。最后的复杂度近似于 Θ(log(log n)n)
    维护堆的性质的核心操作为 旋转

模板代码

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
#include <cstdio>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)

struct node {
int l, r, rnd, v;
int size, w;
}t[100020];
int n, cnt=0, root, ans;
#define lson(k) t[t[k].l]
#define rson(k) t[t[k].r]

inline int rand(){
static int seed=2333;
return seed=(int)((((seed^998244353)+19260817ll)*19890604ll)%1000000007);
}

inline void update(int k) {
t[k].size = lson(k).size + rson(k).size + t[k].w;
}

inline void lturn(int &k) {
int tmp = t[k].r; //旋转节点
t[k].r = t[tmp].l;
t[tmp].l = k;
t[tmp].size = t[k].size;
update(k);
k=tmp;
}

inline void rturn(int &k) {
int tmp = t[k].l;
t[k].l = t[tmp].r;
t[tmp].r = k;
t[tmp].size = t[k].size;
update(k);
k=tmp;
}

inline void insert(int &k, int x) {
if(k==0) {
k = ++cnt;
t[k].size = t[k].w = 1;
t[k].v = x;
t[k].rnd = rand();
return ;
}
++t[k].size;
if(t[k].v == x) ++t[k].w;
else if(x > t[k].v) {
insert(t[k].r, x);
if(rson(k).rnd < t[k].rnd) lturn(k);
}
else {
insert(t[k].l, x);
if(lson(k).rnd < t[k].rnd) rturn(k);
}
} //插入

inline void del(int &k,int x){
if(k==0) return ;
if(t[k].v == x){
if(t[k].w > 1){
--t[k].w,--t[k].size;
return ;
}
if(t[k].l*t[k].r == 0) k=t[k].l+t[k].r;
else if(lson(k).rnd < rson(k).rnd)
rturn(k), del(k, x);
else lturn(k), del(k, x);
} //重点
else if(x > t[k].v)
--t[k].size, del(t[k].r, x);
else --t[k].size, del(t[k].l, x);
} //删除

inline int qurank(int k, int x) {
if(k==0) return 0;
if(x == t[k].v) return lson(k).size+1;
else if(x > t[k].v) return (lson(k).size + t[k].w) + qurank(t[k].r, x);
else return qurank(t[k].l, x);
} //排名查询

inline int qunum(int k, int x) {
if(k==0) return 0;
if(x <= lson(k).size) return qunum(t[k].l, x);
else if(x > lson(k).size+t[k].w) return qunum(t[k].r, x-lson(k).size-t[k].w);
else return t[k].v;
} //数查询

inline void qupro(int k, int x) {
if(k==0) return ;
if(t[k].v < x) {
ans = t[k].v;
qupro(t[k].r, x);
}
else qupro(t[k].l, x);
} //前驱查询

inline void qusub(int k, int x) {
if(k==0) return ;
if(t[k].v > x) {
ans = t[k].v;
qusub(t[k].l, x);
}
else qusub(t[k].r, x);
} //后继查询

int main() {
int T;
scanf("%d", &T);
int opt, x;
while(T--) {
scanf("%d%d", &opt, &x);
switch(opt) {
case 1: insert(root, x); break;
case 2: del(root, x); break;
case 3: printf("%d\n", qurank(root, x)); break;
case 4: printf("%d\n", qunum(root, x)); break;
case 5: qupro(root, x); printf("%d\n", ans); break;
case 6: qusub(root, x); printf("%d\n", ans); break;
}
}
}

FHQ_Treap

构造思路

FHQ_TreapTreap 的加强版,性质与 Treap 相同。核心操作有两个:

  1. 分裂操作:split(k, pos) ,以 k 为根节点将前 pos 个节点分裂成一棵子树。返回值为两个根节点
  2. 合并操作:merge(u, v) ,将根节点分别为 u, v 的两棵树合并。返回值为合并后的根节点。(保证树 u 的所有节点小于 v

加强版优势:可持久化

模板代码

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)
#define inf 0x3f3f3f3f
#define min(a,b) ((a)<(b)?(a):(b))
#define mpar make_pair
typedef pair<int,int> par;

struct node {
int l, r, rnd, v;
int size;
}t[100020];
#define lson(k) t[t[k].l]
#define rson(k) t[t[k].r]
int cnt=0, root, ans;

inline int rand(){
static int seed=2333;
return seed=(int)((((seed^998244353)+19260817ll)*19890604ll)%1000000007);
}

inline void update(int k) {
t[k].size = lson(k).size + rson(k).size + 1;
}

inline par split(int k, int pos) {
if(pos==0) return mpar(0, k);

int ls = t[k].l, rs = t[k].r;
if (t[ls].size == pos)
return t[k].l=0, update(k), mpar(ls, k);
else if (t[ls].size + 1 == pos)
return t[k].r=0, update(k), mpar(k, rs);
else if (pos < t[ls].size) {
par rt = split(t[k].l, pos);
return t[k].l=rt.second, update(k), mpar(rt.first, k);
}
else {
par rt = split(t[k].r, pos-t[ls].size-1);
return t[k].r=rt.first, update(k), mpar(k, rt.second);
}
} //分裂

inline int merge(int u, int v) {
if(u==0 || v==0) return u+v;
if(t[u].rnd < t[v].rnd)
return t[u].r=merge(t[u].r, v), update(u), u;
else
return t[v].l=merge(u, t[v].l), update(v), v;
} //合并

inline int qurank(int x){
int k = root, nex = 0, res = inf;
while(k){
if(x == t[k].v) res = min(res, nex + lson(k).size + 1);

if(x > t[k].v) nex += lson(k).size + 1, k = t[k].r;
else k = t[k].l;
}
return res != inf ? res : nex;
} //查rank(靠前)

inline int qunum(int k, int x) {
if(k==0) return 0;
if(lson(k).size + 1 == x) return t[k].v;
else if(x <= lson(k).size) return qunum(t[k].l, x);
else return qunum(t[k].r, x-lson(k).size-1);
} //查数

inline void insert(int x) {
int k = qurank(x);
par rt = split(root, k);
t[++cnt].size = 1, t[cnt].v = x, t[cnt].rnd = rand();

root = merge(rt.first, cnt),
root = merge(root, rt.second);
} //插入

inline void del(int x) {
int k = qurank(x);
par rt1 = split(root, k);
par rt2 = split(rt1.first, k-1);
root = merge(rt2.first, rt1.second);
} //删除

inline void qupro(int k, int x) {
if(k==0) return ;
if(t[k].v < x) {
ans = t[k].v;
qupro(t[k].r, x);
}
else qupro(t[k].l, x);
} //前驱查询

inline void qusub(int k, int x) {
if(k==0) return ;
if(t[k].v > x) {
ans = t[k].v;
qusub(t[k].l, x);
}
else qusub(t[k].r, x);
} //后继查询

int main() {
int T, opt, x;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &opt, &x);
switch(opt) {
case 1: insert(x); break;
case 2: del(x); break;
case 3: printf("%d\n", qurank(x)); break;
case 4: printf("%d\n", qunum(root, x)); break;
case 5: qupro(root, x), printf("%d\n", ans); break;
case 6: qusub(root, x), printf("%d\n", ans); break;
}
}
}

Splay(文艺平衡树)

题目描述

    您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作:
    插入x数
    删除x数(若有多个相同的数,因只删除一个)
    查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数,因输出最小的排名)
    查询排名为x的数
    求x的前驱(前驱定义为小于x,且最大的数)
    求x的后继(后继定义为大于x,且最小的数)

输入输出格式

输入格式:
    第一行为n,表示操作的个数,下面n行每行有两个数opt和x,opt表示操作的序号( 1≤opt≤6 )

输出格式:
    对于操作3,4,5,6每行输出一个数,表示对应答案

构造思路

百度百科-伸展树-存在的意义 假设想要对一个二叉查找树执行一系列的查找操作。为了使整个查找时间更小,被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法, 在每次查找之后对树进行重构,把被查找的条目搬移到离树根近一些的地方。splay tree应运而生。splay tree是一种自调整形式的二叉查找树,它会沿着从某个节点到树根之间的路径,通过一系列的旋转把这个节点搬移到树根去。

核心操作:splay(k, goal) 将节点 k 旋转到节点 goal

模板代码

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
#include <cstdio>

struct node {
int v, size, w;
int fa, s[2];
}t[100020];
int cnt=0, root;
#define lson(k) t[t[k].s[0]]
#define rson(k) t[t[k].s[1]]

inline int Chkson(int k) {
return t[t[k].fa].s[1] == k;
}
inline void update(int k) {
t[k].size = lson(k).size + rson(k).size + t[k].w;
}
inline void connect(int u, int v, int z) {
t[u].s[z] = v, t[v].fa = u;
} //在u下面连接v

inline void rotate(int k) {
int p = t[k].fa;
int d = Chkson(k);
connect(t[p].fa, k, Chkson(p));
connect(p, t[k].s[d^1], d) ,update(p);
connect(k, p, d^1), update(k);
if (t[k].fa == 0) root = k;
} //旋转

inline void splay(int k, int goal) {
while(t[k].fa != goal)
{
if(t[t[k].fa].fa != goal) {
if (Chkson(k) == Chkson(t[k].fa)) rotate(t[k].fa);
else rotate(k);
}
rotate(k);
}
if(goal==0)
root = k;
} //splay操作

inline void insert(int x) {
int u = root, f = 0;
while(u && t[u].v!=x)
f = u, u = t[u].s[x>t[u].v];

if(u) ++t[u].w;
else {
u = ++cnt;
if(f) t[f].s[x>t[f].v] = u; //非空
t[cnt].s[0] = t[cnt].s[1] = 0;
t[cnt].w = t[cnt].size = 1;

t[cnt].v = x, t[cnt].fa = f;
}
splay(u, 0);
} //插入

inline void find(int x) {
int u = root;
if(!u) return ;
while(t[u].s[x>t[u].v] && x != t[u].v) //可能x不存在
u = t[u].s[x>t[u].v];
splay(u, 0);
} //找x位置

inline int quner(int x, int f) {
find(x);
int u = root;
if((t[u].v>x && f) || (t[u].v<x && !f)) return u;
u = t[u].s[f];
while(t[u].s[f^1]) u = t[u].s[f^1];
return u;
} // 前驱/后继

inline void del(int x) {
int pro = quner(x, 0), sub = quner(x, 1);
splay(pro, 0), splay(sub, pro);
int rt = t[sub].s[0];
if (t[rt].w > 1)
--t[rt].w, splay(rt, 0);
else t[sub].s[0] = 0;
}

inline int qunum(int k) {
int u = root;
if(t[u].size < k) return 0;
while(1) {
if (k > lson(u).size + t[u].w)
k -= lson(u).size+t[u].w,
u = t[u].s[1];
else if (lson(u).size >= k)
u = t[u].s[0];
else return t[u].v;
}
}

int T, opt, x;

int main() {
insert(-2147483647), insert(+2147483647);
scanf("%d", &T);
while(T--) {
scanf("%d%d", &opt, &x);
switch(opt) {
case 1: insert(x); break;
case 2: del(x); break;
case 3: find(x), printf("%d\n", lson(root).size); break;
case 4: printf("%d\n", qunum(x+1)); break;
case 5: printf("%d\n", t[quner(x, 0)].v); break;
case 6: printf("%d\n", t[quner(x, 1)].v); break;
}
}
}

参考论文:左偏树的特点及其应用

左偏树(可并堆)

定义和性质

  • 基本性质:左偏树(可并堆)支持优先队列的操作,还支持一个额外的操作——合并操作,即可以将两个优先队列合并。

  • 定义:左偏树(Leftist Tree)是一种可并堆的实现,带有4个属性:

Left son 左孩子 Right son 右孩子 Key 键值 dist 距离

(我们约定 ii外节点当且仅当节点 ii 的左子树或右子树为空)

额外地,我们定义 dist 为 ii 到它的后代中离外节点最近的距离。

  • 左偏树的性质:

1.节点的键值 左右子节点的性质(堆性质)
2.节点的左子节点的 distdist 右子节点的距离 (左偏性质)

性质 2. 的作用:使插入和删除的时候花费的代价更小。

3.节点的距离等于右子节点的距离+1

合并&删除操作

我们规定,将根节点小的树放左边(u),根节点大的树放右边(v)。接着用 u 的右孩子去合并 v,即 rs[u]=merge(rs[u],v)rs[u] = merge(rs[u],v)。每次合并后都返回根节点。
返回时 u 的 distdist 值 = v 的 distdist 值 + 1,如果 dis[ls[u]]<dis[rs[u]]dis[ls[u]] < dis[rs[u]] 则交换左右孩子,保持左偏树性质。

删除最小节点 u 只需要更改 ls[u]ls[u]rs[u]rs[u] 的父亲节点,再将 ls[u]ls[u]rs[u]rs[u] 两个子树合并。

(详见代码)

【模板】左偏树(可并堆)

题目链接

题目描述

如题,一开始有N个小根堆,每个堆包含且仅包含一个数。接下来需要支持两种操作:

操作1: 1 x y

将第x个数和第y个数所在的小根堆合并(若第x或第y个数已经被删除或第x和第y个数在用一个堆内,则无视此操作)

操作2: 2 x

输出第x个数所在的堆最小数,并将其删除(若第x个数已经被删除,则输出-1并无视删除操作)

输入输出格式

输入格式:

第一行包含两个正整数N、M,分别表示一开始小根堆的个数和接下来操作的个数。
第二行包含N个正整数,其中第i个正整数表示第i个小根堆初始时包含且仅包含的数。
接下来M行每行2个或3个正整数,表示一条操作,格式如下:

操作1 : 1 x y 操作2 : 2 x

输出格式:

输出包含若干行整数,分别依次对应每一个操作2所得的结果。

输入样例:

5 5
1 5 4 2 3
1 1 5
1 2 5
2 2
1 4 2
2 2

输出样例:

1
2

说明

当堆里有多个最小值时,优先删除原序列的靠前的,否则会影响后续操作1导致WA。 时空限制:1000ms,128M

数据规模:

对于30%的数据:N<=10,M<=10
对于70%的数据:N<=1000,M<=1000
对于100%的数据:N<=100000,M<=100000

样例说明

初始状态下,五个小根堆分别为:{1}、{5}、{4}、{2}、{3}。

  • 第一次操作,将第1个数所在的小根堆与第5个数所在的小根堆合并,故变为四个小根堆:{1,3}、{5}、{4}、{2}。
  • 第二次操作,将第2个数所在的小根堆与第5个数所在的小根堆合并,故变为三个小根堆:{1,3,5}、{4}、{2}。
  • 第三次操作,将第2个数所在的小根堆的最小值输出并删除,故输出1,第一个数被删除,三个小根堆为:{3,5}、{4}、{2}。
  • 第四次操作,将第4个数所在的小根堆与第2个数所在的小根堆合并,故变为两个小根堆:{2,3,5}、{4}。
  • 第五次操作,将第2个数所在的小根堆的最小值输出并删除,故输出2,第四个数被删除,两个小根堆为:{3,5}、{4}。

故输出依次为1、2。

AC代码

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
#include <cstdio>
#include <memory>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)
const int N = 100020;

int n, m;
int val[N], ls[N], rs[N], fa[N], dis[N];

inline int merge(int u, int v) {
if(u==0 || v==0) return u+v;
if(val[u] > val[v] || (val[u]==val[v] && u>v)) swap(u, v);
rs[u] = merge(rs[u], v);
fa[rs[u]] = u;
if(dis[ls[u]] < dis[rs[u]]) swap(ls[u], rs[u]);
dis[u] = dis[rs[u]] + 1;
return u;
}

inline void erase(int u) {
val[u] = -1, fa[ls[u]] = fa[rs[u]] = 0;
merge(ls[u], rs[u]);
}

inline int find(int x) {
return fa[x] ? find(fa[x]) : x;
}

int main() {
scanf("%d%d", &n, &m);
rep(i,1,n) scanf("%d", val+i);
int opt, x, y;
while(m--) {
scanf("%d", &opt);
if(opt == 1) {
scanf("%d%d", &x, &y);
if(val[x]!=-1 && val[y]!=-1) {
int p=find(x), q=find(y);
if(p!=q) merge(p, q);
}
}
else {
scanf("%d", &x);
if(val[x]==-1) puts("-1");
else {
int p = find(x);
printf("%d\n", val[p]);
erase(p);
}
}
}
}

题目推荐:Monkey King


主席树(可持久化线段树)

因排版问题已转移到 链接

FlashHu的博客-cnblogs