Jumat, 30 Juni 2017

SPOJ QMAX3VN - BST Sebagai Segment Tree

Berikut adalah kelanjutan dari tulisan saya tentang penggunaan BST untuk menjawab dynamic range query. Soal yang dibahas adalah SPOJ QMAX3VN.

Ide solusi

Soal ini merupakan implementasi langsung dari konsep BST sebagai "segment tree" yang saya bahas sebelumnya. Pilihlah suatu jenis BBST yang Anda sukai, baik itu AVL Tree, Red Black Tree, Treap, atau Splay Tree.

Nilai agregat pada soal ini jelas adalah nilai terbesar yang ada pada suatu subtree. Anda juga perlu menyimpan banyaknya elemen yang ada pada suatu subtree, supaya dapat menentukan apakah suatu node/subtree berada dalam rentang query.

Tips untuk mengimplementasikannya:
  1. Definisikan fungsi updateAggregate untuk melakukan update pada nilai agregat suatu node, menggunakan data dari anak kiri dan anak kanannya. Aktivitas updateAggregate akan digunakan di banyak tempat, sehingga mendefinisikannya sebagai fungsi akan mempermudah penulisan kode. Pastikan kompleksitasnya O(1).
  2. Jika BST Anda menggunakan rotasi, pastikan pemanggilan updateAggregate sesuai urutannya, yaitu dari node anak-anak dulu, baru ke orang tuanya.
  3. Definisikan fungsi getMax dan getCount untuk mendapatkan nilai terbesar dan banyaknya node pada suatu subtree, yang mampu menangani kasus ketika node yang diberikan adalah null. Pendefinisian fungsi ini sangat membantu dalam mengeliminasi if statement untuk null di banyak tempat. Pastikan juga kompleksitasnya O(1).

Implementasi

Berikut adalah implementasi saya dalam C++ menggunakan BBST kesukaan saya, yaitu 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
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
 
#define INF 2123123123
#define MAXN 1000002
 
using namespace std;
 
struct node{
   int prior, cnt, maxVal, val;
   node *l, *r;
   node(){}
   node(int _val) : prior(rand()), cnt(1), l(0), r(0), maxVal(_val), val(_val){}
};
 
inline int max3(int a, int b, int c){
   return max(max(a,b),c);
}
 
/////////////////////////////
// BEGIN OF TREAP ROUTINES //
/////////////////////////////
inline int getCnt(node* v){
   return v ? v->cnt : 0;
}
 
inline int getMax(node* v){
   return v ? v->maxVal : -INF;
}
 
inline void updateAggregate(node* v){
   if (v){
      v->cnt = 1 + getCnt(v->l) + getCnt(v->r);
      v->maxVal = max3(v->val,  getMax(v->l), getMax(v->r));
   }
}
 
void split(node* v, int pos, node* &l, node* &r){
   if (!v){
      l = r = 0;
   }else if (pos <= getCnt(v->l)+1){
      split(v->l, pos, l, v->l);
      r = v;
   }else{
      split(v->r, pos - getCnt(v->l) - 1, v->r, r);
      l = v;
   }
 
   updateAggregate(v);
}
 
void insert(node* &v, node* add, int pos){
   if (!v){
      v = add;
   }else if (add->prior <= v->prior){
      if (pos <= getCnt(v->l)+1){
         insert(v->l, add, pos);
      }else{
         insert(v->r, add, pos - getCnt(v->l) - 1);
      }
 
   }else{
      split(v, pos, add->l, add->r);
      v = add;
   }
 
   updateAggregate(v);
}
 
int query(node *x, int add, int &l, int &r){
   if (!x) return -INF;
 
   if ((l <= add) && (add + getCnt(x) <= r)){
      // Include this whole subtree
      return x->maxVal;
   }else{
      int ret = -INF;
      int mid = add + getCnt(x->l) + 1;
    
      // Include itself?
      if ((l <= mid) && (mid <= r)) ret = max(ret, x->val);
 
      // Include left/right subtree?
      if ((l <= add + getCnt(x->l)))    ret = max(ret, query(x->l, add, l, r));
      if ((r > add + getCnt(x->l) + 1)) ret = max(ret, query(x->r, add + getCnt(x->l) + 1, l, r));
 
      return ret;
   }
}
 
///////////////////////////
// END OF TREAP ROUTINES //
///////////////////////////
 
int N;
node* root;
 
int main(){
   root = 0;
 
   scanf("%d", &N);
   for (int i = 0; i < N; i++){
      char sc[5];
      int a,b;
      scanf("%s%d%d", sc, &a, &b);
 
      if (sc[0] == 'A'){
         insert(root, new node(a), b);
      }else{
         printf("%d\n", query(root, 0, a, b));
      }
   }
}
Diposting oleh di
Label: , , ,

2 komentar :

  1. Anonim23 Juli 2017 pukul 15.57

    Wah keren kak, dulu saya kerjakan qmax3vn dengan implicit treap juga (waktu p2)

    BalasHapus

Langganan: Posting Komentar ( Atom )