「Solution」宠物收留所 & GSS6

Posted on Edited on In

At the Beginning

写平衡树有点想吐，过来码两篇题解

最近写题写得有点儿乱，整理一下。。。

宠物收留所

link

分析

乍一看，好像要两个平衡树。

但仔细读题可以发现：

在任意时刻，平衡树里只会全部保留其中一类（人 或 宠物） 那么用一颗平衡树维护即可

并且对于人和动物，操作都一样。

具体如下：

若当前是人，如果没有宠物，直接加入平衡树，否则就直接查询前驱|后继统计即可，宠物同理

代码

代码略丑。。。fhq_treap跑得很慢。。。

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
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e5 + 5;
const int Mod = 1000000;

int n, tot, root, tmp1, tmp2, tmp3, ans;

struct Treap {
    int l, r, val, key, siz;
} s[MAXN];

int newnode (int val) {
    s[++tot].val = val, s[tot].key = rand (), s[tot].siz = 1;
    return tot;
}
void push_up (int p) {
    s[p].siz = s[s[p].l].siz + s[s[p].r].siz + 1;
}
void split (int p, int val, int& x, int& y) {
    if (p == 0) { x = y = 0; return; }
    if (s[p].val <= val) {
        x = p, split (s[p].r, val, s[p].r, y);
    } else {
        y = p, split (s[p].l, val, x, s[p].l);
    }
    push_up (p);
}
int merge (int x, int y) {
    if (!x || !y) return x + y;
    if (s[x].key < s[y].key) {
        s[x].r = merge (s[x].r, y);
        push_up(x);
        return x;
    } else {
        s[y].l = merge (x, s[y].l);
        push_up(y);
        return y;
    }
}
void insert (int val) {
    split (root, val, tmp1, tmp2);
    root = merge (merge (tmp1, newnode (val)), tmp2);
}
void remove (int val) {
    split (root, val, tmp1, tmp3);
    split (tmp1, val - 1, tmp1, tmp2);
    tmp2 = merge (s[tmp2].l, s[tmp2].r);
    root = merge (merge(tmp1, tmp2), tmp3);
}
int queryrnk (int val) {
    split (root, val - 1, tmp1, tmp2);
    int res = s[tmp1].siz + 1;
    root = merge (tmp1, tmp2);
    return res;
}
int querykth (int p, int k) {
    while (1) {
        if (s[s[p].l].siz >= k) {
            p = s[p].l;
            continue;
        }
        if (s[s[p].l].siz + 1 == k) {
            return p;
        }
        k -= s[s[p].l].siz + 1, p = s[p].r;
    }
}
int querypre (int val) {
    split (root, val - 1, tmp1, tmp2);
    if (tmp1 == 0) return INF;
    int res = s[querykth (tmp1, s[tmp1].siz)].val;
    root = merge (tmp1, tmp2);
    return res;
}
int querynxt (int val) {
    split (root, val, tmp1, tmp2);
    if (tmp2 == 0) return INF;
    int res = s[querykth (tmp2, 1)].val;
    root = merge (tmp1, tmp2);
    return res;
}

int Abs (int x) {
    return (x < 0) ? -x : x;
}

int main () {
    scanf ("%d", &n);
    int cnt1, cnt2;
    cnt1 = cnt2 = 0;
    while (n--) {
        int opt, k;
        scanf ("%d %d", &opt, &k);
        if (opt == 0) {
            if (cnt2 == 0) {
                insert (k);
                cnt1++;
            } else {
                int pre = querypre (k);
                int nxt = querynxt (k);
                int val = (Abs (pre - k) <= Abs (nxt - k)) ? pre : nxt;
                remove (val);
                ans = (ans + Abs (val - k)) % Mod;
                cnt2--;
            }
        } else {
            if (cnt1 == 0) {
                insert (k);
                cnt2++;
            } else {
                int pre = querypre (k);
                int nxt = querynxt (k);
                int val = (Abs (pre - k) <= Abs (nxt - k)) ? pre : nxt;
                remove (val);
                ans = (ans + Abs (val - k)) % Mod;
                cnt1--;
            }
        }
        // printf ("ans = %d\n", ans);
    }
    printf ("%d\n", ans);
    return 0;
}

​

GSS 6 - Can you answer these queries VI

link

分析

其实就是个最大字段和问题，和GSS1类似。

关于线段树维护最大字段和的方式再写一遍吧。

...

看图应该可以理解，即是对于当前区间，它的最大字段和可以由三种方式去更新：

  • 当前节点的左儿子的最大字段和

  • 当前节点的右儿子的最大字段和

  • 当前节点的左儿子的右端连续最大和加右儿子的左端连续最大和

那么再去多维护两个值即可(lmax, rmax)

feNC5j.png

对于维护lmax，有两种方式去更新：

  • 当前节点的左儿子的lmax
    • 当前节点的左儿子的区间和加当前节点的右儿子的lmax

对于rmax也同理

push_up的代码不难写出 

1
2
3
4
5
6
void push_up (int p) {
	s[p].sum = s[p * 2].sum + s[p * 2 + 1].sum;
	s[p].lmax = max(s[p * 2].lmax, s[p * 2].sum + s[p * 2 + 1].lmax);
	s[p].rmax = max(s[p * 2 + 1].rmax, s[p * 2 + 1].sum + s[p * 2].rmax);
	s[p].dat = max(s[p * 2].dat, max(s[p * 2 + 1].dat, s[p * 2].rmax + s[p * 2 + 1].lmax));
}

然后GSS1就可以顺利AC,GSS6也同理，只是将线段树的操作搬到了平衡树上。

push_up的代码变成 

1
2
3
4
5
6
7
void push_up (int p) {
	s[p].siz = s[s[p].l].siz + s[s[p].r].siz + 1;
	s[p].sum = s[s[p].l].sum + s[s[p].r].sum + s[p].val;
	s[p].pre = max (s[s[p].l].pre, s[s[p].l].sum + s[p].val + s[s[p].r].pre);
	s[p].nxt = max (s[s[p].r].nxt, s[s[p].r].sum + s[p].val + s[s[p].l].nxt);
	s[p].maxl = max (max (s[s[p].l].maxl, s[s[p].r].maxl), s[s[p].l].nxt + s[p].val + s[s[p].r].pre);
}

然后需要注意的是平衡树要写成区间树，即要用下标作为分裂的标准，在线段树的基础上要加上自身的权值，且要在初始的时候塞一个空节点，权值为-INF。

split的代码较按权值分裂略有不同。 

1
2
3
4
5
6
7
8
9
10
11
void split (int p, int k, int& x, int& y) {
	if (p == 0) {
		x = y = 0; return;
	}
	if (s[s[p].l].siz < val) {
		x = p, split (s[p].r, val - s[s[p].l].siz - 1, s[p].r, y);
	} else {
		y = p, split (s[p].l, val, x, s[p].l);
	}
	push_up (p);
}

代码

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
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 2e5 + 5;
const int INF = 0x3f3f3f3f;

int n, m, root, tot, tmp1, tmp2, tmp3;

struct Treap {
	int l, r, val, key, siz;
	int pre, nxt; // 区间前(后)缀 
	int maxl, sum; // 区间最大字段和 | 区间和 
} s[MAXN]; 

int newnode (int val) {
	tot++;
	s[tot].sum = s[tot].maxl = s[tot].val = val, s[tot].key = rand (), s[tot].siz = 1;
	s[tot].pre = s[tot].nxt = max (val, 0);
	return tot;
}

void push_up (int p) {
	s[p].siz = s[s[p].l].siz + s[s[p].r].siz + 1;
	s[p].sum = s[s[p].l].sum + s[s[p].r].sum + s[p].val;
	s[p].pre = max (s[s[p].l].pre, s[s[p].l].sum + s[p].val + s[s[p].r].pre);
	s[p].nxt = max (s[s[p].r].nxt, s[s[p].r].sum + s[p].val + s[s[p].l].nxt);
	s[p].maxl = max (max (s[s[p].l].maxl, s[s[p].r].maxl), s[s[p].l].nxt + s[p].val + s[s[p].r].pre);
}

void split (int p, int val, int& x, int& y) {
	if (p == 0) {
		x = y = 0; return;
	}
	if (s[s[p].l].siz < val) {
		x = p, split (s[p].r, val - s[s[p].l].siz - 1, s[p].r, y);
	} else {
		y = p, split (s[p].l, val, x, s[p].l);
	}
	push_up (p);
}

int merge (int x, int y) {
	if (!x || !y) return x + y;
	if (s[x].key < s[y].key) {
		s[x].r = merge (s[x].r, y);
		push_up (x);
		return x;
	} else {
		s[y].l = merge (x, s[y].l);
		push_up (y);
		return y;
	}
}

void insert (int p, int val) {
	split (root, p, tmp1, tmp2);
	root = merge (merge (tmp1, newnode (val)), tmp2);
}

void remove (int p) {
	split (root, p, tmp1, tmp3);
	split (tmp1, p - 1, tmp1, tmp2);
	tmp2 = merge (s[tmp2].l, s[tmp2].r);
	root = merge (tmp1, merge (tmp2, tmp3));
}

void change (int p, int val) {
	split (root, p, tmp1, tmp3);
	split (tmp1, p - 1, tmp1, tmp2);
	s[tmp2].sum = s[tmp2].maxl = s[tmp2].val = val;
	s[tmp2].pre = s[tmp2].nxt = max (val, 0);
	root = merge (merge (tmp1, tmp2), tmp3);
}

int query (int l, int r) {
	split (root, r, tmp1, tmp3);
	split (tmp1, l - 1, tmp2, tmp1);
	int res = s[tmp1].maxl;
	root = merge (merge (tmp2, tmp1), tmp3);
	return res;
}

void print (int p) {
    if (!p)
        return;
    print (s[p].l);
    printf ("p = %d, val = %d, l = %d, r = %d, siz = %d\n", p, s[p].val, s[p].l, s[p].r, s[p].siz);
    print (s[p].r);
}

void debug () {
    printf ("\n----------------WAll---------------\n");
    print (root);
    printf ("\n----------------WAll---------------\n\n");
}

int main () {
	scanf ("%d", &n);
	s[0].maxl = -INF;
	for (int i = 1, x; i <= n; i++) {
		scanf ("%d", &x);
		root = merge (root, newnode (x));
	}
	scanf ("%d", &m);
	while (m--) {
		char opt;
		cin >> opt;
		int l, r, p, x;
		switch (opt) {
			case 'I' : {
				scanf ("%d %d", &p, &x); insert (p - 1, x);
				break;
			}
			case 'D' : {
				scanf ("%d", &p); remove (p);
				break;
			}
			case 'R' : {
				scanf ("%d %d", &p, &x); change (p, x);
				break;
			}
			case 'Q' : {
				scanf ("%d %d", &l, &r); printf ("%d\n", query (l, r));
				break;
			}
		}
//		debug ();
	}
	return 0;
}
The End
「Ô mon âme, n'aspire pas à la vie immortelle, mais épuise le champ du possible.」