Senin, 07 Januari 2019

Petunjuk Coding: Segment Tree Lazy Propagation

Setelah menguasai penulisan kode segment tree yang melayani update sebuah elemen dan range query, kini waktunya beranjak ke operasi yang lebih sulit: range update.

Perkenalan tentang penanganan range update dengan lazy propagation pernah saya bahas di tulisan yang lalu. Pada tulisan ini, kita akan fokus ke implementasinya.

Konsep

Lazy propagation dapat diimplementasikan ketika:
  1. Apabila seluruh elemen yang dicakupi sebuah segmen mendapatkan update, maka update harus disangkutkan pada segmen tersebut dengan efisien & tanpa menyentuh anak-anaknya.
  2. Apabila seluruh elemen yang dicakupi suatu segmen diperlukan dalam query, maka informasi asli dari segmen itu harus bisa didapatkan dengan efisien & tanpa menyentuh anak-anaknya.
Apabila kedua syarat itu dipenuhi, maka lazy propagation dapat diterapkan. Setiap range update atau query dapat dilaksanakan dalam O(log N).

Untuk keperluan penjelasan, nilai yang disangkutkan akan saya sebut "nilai lazy".

Penjelasan tentang cara implementasi akan dijelaskan melalui studi kasus 1 pada bagian selanjutnya. Kita juga akan mengambil abstraksi kode lazy propagation dari sana, untuk diterapkan pada studi kasus seterusnya.

Studi Kasus 1: HORRIBLE (SPOJ)

Rasanya soal ini sangat sering dibahas...
Soal lengkap dapat dilihat di https://www.spoj.com/problems/HORRIBLE.

Mari kita implementasikan fungsi update, yaitu menambahkan suatu nilai kepada suatu rentang.
Selain menyimpan nilai jumlahan pada setiap segmen, kita perlu menyimpan informasi nilai yang disangkutkan. Nilai ini secara intuitif terpikir adalah nilai yang seharusnya ditambahkan pada masing-masing elemen pada segmen tersebut. Mari kita sebut nilai itu "delayedAdd".

Kini segment tree kita perlu menyimpan dua nilai, yaitu jumlahan setiap segmen dan delayedAdd. Implementasinya dapat memanfaatkan struct:
?
1
2
3
4
5
6
7
8
9
typedef long long LL;
const int MAXN = 132000;
 
struct data {
  LL sum;
  LL delayedAdd;
};
 
data sTree[2*MAXN];

Catatan: jangan lupa untuk menginisialisasi nilai sum dan delayedAdd dengan nilai 0.

Setiap kali setiap elemen yang dicakupi suatu segmen perlu mendapatkan tambahan nilai, kita tambahkan nilai lazy "delayedAdd" dengan nilai tersebut.
?
1
2
3
4
5
6
7
void update(int id, int l, int r, int xa, int xb, LL delta) {
  if ((xa <= l) && (r <= xb)) {
    sTree[id].delayedAdd += delta;
  } else {
    ...
  }
}

Nah untuk kasus update yang tidak dilakukan pada seluruh elemen pada segmen, kita perlu turun ke anak-anak segmen itu secara rekursif (seperti range query biasanya). Namun ketika segmen ini memiliki nilai lazy, kita harus melanjutkan pekerjaan yang tertunda itu. Caranya:
  1. Menurunkan nilai lazy dari segmen itu ke anak-anaknya, sehingga segmen itu sudah tidak lagi menyimpan nilai lazy. Bayangkan seperti pekerjaan di segmen tersebut yang tertunda sudah selesai dilaksanakan. Tahap ini sering disebut "propagate".
  2. Lanjut melakukan range update pada anaknya yang bersangkutan.
  3. Saat range update anak-anak selesai dilakukan, perbaharui nilai segmen dengan memanfaatkan informasi dari anak-anaknya (seperti tahap "MERGE" yang diperkenalkan tulisan sebelumnya).
Untuk "propagate", kita cukup menambahkan nilai lazy anak-anak suatu segmen dengan nilai lazy yang dikandung elemen tersebut. Supaya rapi saya akan mendefinisikan fungsi "PROPAGATE":
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void PROPAGATE(int id) {
  sTree[2*id+1].delayedAdd += sTree[id].delayedAdd;
  sTree[2*id+2].delayedAdd += sTree[id].delayedAdd;
 
  sTree[id].delayedAdd = 0;
}
 
void update(int id, int l, int r, int xa, int xb, LL delta) {
  if ((xa <= l) && (r <= xb)) {
    sTree[id].delayedAdd += delta;
  } else {
    int m = (l + r)/2;
 
    PROPAGATE(id);
 
    ...
  }
}
Penting untuk disadari bahwa sesudah nilai lazy diteruskan ke anak-anak, segmen tersebut sudah bersih. Tidak ada lagi nilai lazy, sehingga delayedAdd perlu dijadikan 0.

Langkah kedua, lakukan update pada anak-anak segmen seperlunya.
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void PROPAGATE(int id) {
  sTree[2*id+1].delayedAdd += sTree[id].delayedAdd;
  sTree[2*id+2].delayedAdd += sTree[id].delayedAdd;
 
  sTree[id].delayedAdd = 0;
}
 
void update(int id, int l, int r, int xa, int xb, LL delta) {
  if ((xa <= l) && (r <= xb)) {
    sTree[id].delayedAdd += delta;
  } else {
    int m = (l + r)/2;
 
    PROPAGATE(id);
 
    if (xa <= m) update(2*id+1, l, m, xa, xb, delta);
    if (xb >  m) update(2*id+2, m+1, r, xa, xb, delta);
 
    ...
  }
}

Terakhir, perbaharui nilai segmen saat ini berdasarkan informasi dari anak-anaknya. Hal ini perlu dilakukan karena segmen tersebut sudah terbebas dari nilai lazy, yang mana telah diteruskan ke anak-anaknya.

Perhatikan bahwa anak-anaknya mungkin menyimpan nilai lazy. Ketika suatu segmen menyimpan nilai lazy, nilai asli jumlahan yang dikandung segmen itu adalah: sum + delayedAdd*banyaknya_elemen. Supaya rapi, saya mendefinisikan fungsi "GET" untuk mendapatkan nilai asli suatu segmen. Berhubung banyaknya elemen dalam segmen diperlukan, saya menjadikan batasan kiri dan kanan segmen sebagai parameter dalam "GET":
?
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
void PROPAGATE(int id) {
  sTree[2*id+1].delayedAdd += sTree[id].delayedAdd;
  sTree[2*id+2].delayedAdd += sTree[id].delayedAdd;
 
  sTree[id].delayedAdd = 0;
}
 
LL GET(int id, int l, int r) {
  return sTree[id].sum + sTree[id].delayedAdd*(r-l+1);
}
 
void update(int id, int l, int r, int xa, int xb, LL delta) {
  if ((xa <= l) && (r <= xb)) {
    sTree[id].delayedAdd += delta;
  } else {
    int m = (l + r)/2;
 
    PROPAGATE(id);
 
    if (xa <= m) update(2*id+1, l, m, xa, xb, delta);
    if (xb >  m) update(2*id+2, m+1, r, xa, xb, delta);
 
    sTree[id].sum = GET(2*id+1, l, m) + GET(2*id+2, m+1, r);
  }
}

Sadari bahwa proses menempatkan nilai lazy pada base case sebenarnya memiliki konsep yang sama dengan menempatkan nilai lazy kepada anak-anak dalam fungsi "PROPAGATE". Supaya lebih rapi, kita bisa me-refactor-nya menjadi sebuah fungsi "LAZY_UPDATE":
?
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
void LAZY_UPDATE(int id, LL delta) {
  sTree[id].delayedAdd += delta;
}
 
void PROPAGATE(int id) {
  LAZY_UPDATE(2*id+1, sTree[id].delayedAdd);
  LAZY_UPDATE(2*id+2, sTree[id].delayedAdd);
 
  sTree[id].delayedAdd = 0;
}
 
LL GET(int id, int l, int r) {
  return sTree[id].sum + sTree[id].delayedAdd*(r-l+1);
}
 
void update(int id, int l, int r, int xa, int xb, LL delta) {
  if ((xa <= l) && (r <= xb)) {
    LAZY_UPDATE(id, delta);
  } else {
    int m = (l + r)/2;
 
    PROPAGATE(id);
 
    if (xa <= m) update(2*id+1, l, m, xa, xb, delta);
    if (xb >  m) update(2*id+2, m+1, r, xa, xb, delta);
 
    sTree[id].sum = GET(2*id+1, l, m) + GET(2*id+2, m+1, r);
  }
}

Dan selesailah fungsi update. Lanjut ke fungsi query yang konsepnya mirip.
Mulai dengan membuat kasus ketika segmen sepenuhnya dicakupi rentang yang ditanyakan. Pada kasus ini, cukup kembalikan nilai sum + delayedAdd*banyaknya_elemen. Hal ini sama dengan fungsi "GET" yang telah kita buat, jadi cukup digunakan kembali:
?
1
2
3
4
5
6
7
LL query(int id, int l, int r, int xa, int xb) {
  if ((xa <= l) && (r <= xb)) {
    return GET(id,l,r);
  }else{
    ...
  }
}

Untuk kasus anaknya perlu diperiksa, kita akan mengulang ketiga proses seperti pada update. Pertama, lakukan propagate nilai lazy ke anak-anaknya:
?
1
2
3
4
5
6
7
8
9
10
LL query(int id, int l, int r, int xa, int xb) {
  if ((xa <= l) && (r <= xb)) {
    return GET(id,l,r);
  }else{
    int m = (l + r)/2;
 
    PROPAGATE(id);
    ...
  }
}

Kedua, query anak-anaknya yang mengandung rentang yang ditanyakan:
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
LL query(int id, int l, int r, int xa, int xb) {
  if ((xa <= l) && (r <= xb)) {
    return GET(id,l,r);
  }else{
    int m = (l + r)/2;
 
    PROPAGATE(id);
 
    LL ret = 0;
    if (xa <= m) ret += query(2*id+1, l, m, xa, xb);
    if (xb >  m) ret += query(2*id+2, m+1, r, xa, xb);
 
    ...
  }
}

Terakhir, perbaharui nilai segmen ini menggunakan informasi dari anak-anaknya. Kembali diulang bahwa ini perlu dilakukan karena segmen tersebut sudah terbebas dari nilai lazy, yang mana telah diteruskan ke anak-anaknya. Selesailah fungsi query, dan jangan lupa untuk return nilai di akhir.
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
LL query(int id, int l, int r, int xa, int xb) {
  if ((xa <= l) && (r <= xb)) {
    return GET(id,l,r);
  }else{
    int m = (l + r)/2;
 
    PROPAGATE(id);
 
    LL ret = 0;
    if (xa <= m) ret += query(2*id+1, l, m, xa, xb);
    if (xb >  m) ret += query(2*id+2, m+1, r, xa, xb);
 
    sTree[id].sum = GET(2*id+1, l, m) + GET(2*id+2, m+1, r);
    return ret;
  }
}

Berhubung proses memperbaharui nilai orang tua dari anak-anaknya digunakan di update dan query, saya me-refactor-nya ke dalam fungsi "MERGE". Berikut implementasi lengkap untuk HORRIBLE:
?
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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
 
using namespace std;
 
typedef long long LL;
const int MAXN = 132000;
 
struct data {
  LL sum;
  LL delayedAdd;
};
 
data sTree[2*MAXN];
 
LL GET(int id, int l, int r) {
  return sTree[id].sum + sTree[id].delayedAdd*(r-l+1);
}
 
void LAZY_UPDATE(int id, LL delta) {
  sTree[id].delayedAdd += delta;
}
 
void PROPAGATE(int id) {
  LAZY_UPDATE(2*id+1, sTree[id].delayedAdd);
  LAZY_UPDATE(2*id+2, sTree[id].delayedAdd);
 
  sTree[id].delayedAdd = 0;
}
 
void MERGE(int id, int l, int m, int r) {
  sTree[id].sum = GET(2*id+1, l, m) + GET(2*id+2, m+1, r);
}
 
void update(int id, int l, int r, int xa, int xb, LL delta) {
  if ((xa <= l) && (r <= xb)) {
    LAZY_UPDATE(id, delta);
  } else {
    int m = (l + r)/2;
 
    PROPAGATE(id);
 
    if (xa <= m) update(2*id+1, l, m, xa, xb, delta);
    if (xb >  m) update(2*id+2, m+1, r, xa, xb, delta);
 
    MERGE(id, l, m, r);
  }
}
 
LL query(int id, int l, int r, int xa, int xb) {
  if ((xa <= l) && (r <= xb)) {
    return GET(id,l,r);
  }else{
    int m = (l + r)/2;
 
    PROPAGATE(id);
 
    LL ret = 0;
    if (xa <= m) ret += query(2*id+1, l, m, xa, xb);
    if (xb >  m) ret += query(2*id+2, m+1, r, xa, xb);
 
    MERGE(id, l, m, r);
    return ret;
  }
}
 
int main() {
  int nTc;
  scanf("%d", &nTc);
 
  for (int jt = 0; jt < nTc; jt++) {
    int N, Q;
    scanf("%d%d", &N, &Q);
 
    // Reset
    for (int i = 0; i < 2*MAXN; i++) {
      sTree[i].sum = 0;
      sTree[i].delayedAdd = 0;
    }
 
    for (int i = 0; i < Q; i++) {
      int a, b, delta, jq;
      scanf("%d", &jq);
 
      if (jq == 0) {
        scanf("%d%d%d", &a, &b, &delta);
        update(0, 0, N-1, a-1, b-1, delta);
      } else {
        scanf("%d%d", &a,&b);
        printf("%lld\n", query(0, 0, N-1, a-1, b-1));
      }
    }
  }
 
  return 0;
}

Demikianlah implementasi lazy propagation pada soal yang klasik. Polanya sudah terlihat dari implementasi kedua fungsi di atas, yaitu:
  1. Apabila segmen ini dicakup sepenuhnya pada rentang yang diminta, lakukan LAZY_UPDATE (untuk update) atau GET (untuk query).
  2. Apabila segmennya tidak dicakup sepenuhnya pada rentang yang diminta, telusuri anak-anaknya.
    1. Sebelum melanjutkan operasi, lakukan dulu PROPAGATE yang akan mewariskan nilai lazy segmen ke anak-anaknya menggunakan LAZY_UPDATE.
    2. Teruskan operasi ke anak-anaknya.
    3. Baik untuk update maupun query, lakukan MERGE untuk mencari nilai asli (tanpa nilai lazy-lazy-an) dari segmen tersebut menggunakan GET dari anak-anaknya.
Jadi selama Anda bisa mengimplementasikan fungsi-fungsi berikut secara efisien:
  1. LAZY_UPDATE
  2. GET
  3. PROPAGATE
  4. MERGE
berarti selesailah lazy propagation Anda. Keempat fungsi tersebutlah fungsi abstrak pada lazy propagation, yang perlu disesuaikan dengan masalah yang dihadapi.

Mari kita lihat studi kasus berikutnya untuk memperjelas pemahaman tentang implementasi keempat fungsi tersebut.

Studi Kasus 2: Circular RMQ (Codeforces)

Soal lengkap dapat dibaca di sini: https://codeforces.com/contest/52/problem/C
Intinya adalah, diberikan array bilangan a dan 2 macam operasi:
  1. inc(l, r, v): tambahkan v pada a[l], a[l+1], a[l+2], ..., a[r].
  2. rmq(l, r): cari nilai terkecil di antara a[l], a[l+1], a[l+2], ..., a[r].
Urusan sirkularnya tidak menjadi masalah, sebab operasi yang "menembus" elemen terakhir dapat dipecah menjadi 2. Contohnya operasi pada elemen ke 8 sampai ke 3 pada array zero-based dengan 10 elemen cukup dilakukan pada a[8..9] dan a[0..3] secara terpisah.

Nilai yang wajib kita simpan jelas adalah nilai elemen terkecil dari suatu segmen. Lalu apa nilai lazy-nya? Secara intuitif kita dapat menggunakan konsep yang serupa dengan soal sebelumnya, yaitu "delayedAdd".

Apakah dengan "delayedAdd" kita bisa mendapatkan nilai terkecil dari suatu segmen dengan efisien tanpa melirik anak-anaknya? Jawabannya: ya, karena nilai terkecilnya pastilah nilai terkecil yang tersimpan ditambah "delayedAdd".

Saya persilakan Anda untuk memahami implementasi berikut untuk lebih jelasnya. Fungsi update dan query nyaris sama persis dengan fungsi yang sama pada kode HORRIBLE. Yang berbeda signifikan hanya cara mengimplementasikan keempat fungsi abstraknya.
?
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 <algorithm>
#include <cstring>
#include <string>
 
using namespace std;
 
typedef long long LL;
const int MAXN = 265000;
const LL INF = 2123123123LL * 2123123123LL;
 
struct data {
  LL minValue;
  LL delayedAdd;
};
 
data sTree[2*MAXN];
char sc[100];
 
LL GET(int id) {
  return sTree[id].minValue + sTree[id].delayedAdd;
}
 
void LAZY_UPDATE(int id, int delta) {
  sTree[id].delayedAdd += delta;
}
 
void PROPAGATE(int id) {
  LAZY_UPDATE(2*id+1, sTree[id].delayedAdd);
  LAZY_UPDATE(2*id+2, sTree[id].delayedAdd);
 
  sTree[id].delayedAdd = 0;
}
 
void MERGE(int id) {
  sTree[id].minValue = min(GET(2*id+1), GET(2*id+2));
}
 
void update(int id, int l, int r, int xa, int xb, int delta) {
  if ((xa <= l) && (r <= xb)) {
    LAZY_UPDATE(id, delta);
  } else {
    int m = (l + r)/2;
 
    PROPAGATE(id);
 
    if (xa <= m) update(2*id+1, l, m, xa, xb, delta);
    if (xb >  m) update(2*id+2, m+1, r, xa, xb, delta);
 
    MERGE(id);
  }
}
 
LL query(int id, int l, int r, int xa, int xb) {
  if ((xa <= l) && (r <= xb)) {
    return GET(id);
  }else{
    int m = (l + r)/2;
 
    PROPAGATE(id);
 
    LL ret = INF;
    if (xa <= m) ret = min(ret, query(2*id+1, l, m, xa, xb));
    if (xb >  m) ret = min(ret, query(2*id+2, m+1, r, xa, xb));
 
    MERGE(id);
    return ret;
  }
}
 
int main() {
  int N, Q;
  scanf("%d", &N);
 
  // Inisialisasi
  for (int i = 0; i < 2*MAXN; i++) {
    sTree[i].minValue = 0;
    sTree[i].delayedAdd = 0;
  }
 
  // Build cara malas = update 1 per 1 (total: O(N log N))
  for (int i = 0; i < N; i++) {
    int val;
    scanf("%d", &val);
    update(0, 0, N-1, i, i, val);
  }
 
  scanf("%d", &Q);
  gets(sc); // Baca newline sesudah banyaknya query
  for (int nq = 0; nq < Q; nq++) {
    // Parse input
    gets(sc);
 
    int nSpace = 0;
    int len = strlen(sc);
    for (int i = 0; i < len; i++) {
      if (sc[i] == ' ') {
        nSpace++;
      }
    }
 
    int a, b;
    LL v;
 
    if (nSpace == 1) {
      // Query
      sscanf(sc, "%d %d", &a, &b);
 
      LL ans = INF;
      if (a <= b) {
        ans = query(0, 0, N-1, a, b);
      } else {
        ans = min(query(0, 0, N-1, 0, b), query(0, 0, N-1, a, N-1));
      }
      printf("%I64d\n", ans);
 
    } else {
      // Update
      sscanf(sc, "%d %d %I64d", &a, &b, &v);
 
      if (a <= b) {
        update(0, 0, N-1, a, b, v);
      } else {
        update(0, 0, N-1, 0, b, v);
        update(0, 0, N-1, a, N-1, v);
      }
    }
  }
 
  return 0;
}

Studi Kasus 3: Ahoy Pirates (UVa)

Soal lengkap dapat dibaca di: UVa 11402.

Kali ini kita diberikan barisan berisi nilai 0 dan 1. Angka 0 menyatakan "Barbary" dan angka 1 menyatakan "Buccaneer".

Terdapat beberapa jenis operasi yang disebut "sihir" oleh soalnya:
  • F a b: ubah elemen ke-a sampai elemen ke-b menjadi angka 1
  • E a b: ubah elemen ke-a sampai elemen ke-b menjadi angka 0
  • I a b: ubah elemen ke-a sampai elemen ke-b dari 0 menjadi 1, atau dari 1 menjadi 0 (dibalik)
  • S a b: hitung banyaknya angka 1 dari elemen ke-a sampai elemen ke-b
Melayani operasi F dan E sangat mudah, kita cukup menyimpan nilai lazy yang menyatakan apakah suatu segmen berada dalam efek F, atau E, atau tidak sama sekali. Sihir F dan E akan selalu menimpa nilai lazy apapun yang disimpan suatu segmen. Jika diketahui bahwa suatu segmen berada dalam pengaruh F atau E, banyaknya angka 1 dapat ditemukan dengan mudah.

Untuk melayani operasi I, kita bagi per kasusnya:
  1. Ketika segmen berada dalam pengaruh F, kini menjadi E
  2. Ketika segmen berada dalam pengaruh E, kini menjadi F
  3. Jika tidak dalam pengaruh sihir apa-apa, kita tandakan bahwa segmen ini berada dalam efek I.
  4. Jika ternyata segmen ini berada dalam efek I, kini menjadi tidak dalam pengaruh sihir apa-apa.
Setelah memahami bagaimana melayani operasi F, E, dan I, kita selesai mendefinisikan bagaimana fungsi LAZY_UPDATE bekerja.

Untuk operasi GET, jelas kita perlu menyimpan banyaknya elemen bernilai 1 pada suatu segmen. Mari kita sebut banyaknya elemen bernilai 1 dalam suatu segmen sebagai "nBuc". Saat teradpat nilai lazy, nilai nBuc sesungguhnya dapat dicari dengan cara berikut:
  1. Jika sedang dalam pengaruh F, kembalikan banyaknya elemen yang dicakup segmen tersebut.
  2. Jika sedang dalam pengaruh E, kembalikan 0.
  3. Jika tidak sedang dalam pengaruh sihir apa-apa, kembalikan nBuc.
  4. Jika sedang dalam pengaruh I, kembalikan banyaknya elemen 0, yang sama saja dengan banyaknya elemen segmen tersebut dikurangi nBuc.
Setelah LAZY_UPDATE dan GET didefinisikan, PROPAGATE dan MERGE tinggal mengikuti saja. Lagi-lagi fungsi update dan query nyaris sama persis dengan fungsi yang sama pada kode HORRIBLE. Perbedaan signifikan hanya dalam cara mengimplementasikan keempat fungsi abstraknya. Berikut implementasi lengkapnya:
?
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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
 
using namespace std;
 
const int MAXN = 1050000;
 
const int BUC = 1;
const int BAR = 0;
 
const int NONE = -1;
const int ALL_BUC = 0;
const int ALL_BAR = 1;
const int INVERSE = 2;
 
struct data {
  int nBuc;
  int state;
};
 
data sTree[2*MAXN];
int ar[MAXN];
char sc[55];
 
int GET(int id, int l, int r) {
  if (sTree[id].state == NONE) {
    return sTree[id].nBuc;
 
  } else if (sTree[id].state == ALL_BUC) {
    return r-l+1;
 
  } else if (sTree[id].state == ALL_BAR) {
    return 0;
 
  } else {
    // Inverse
    return r-l+1 - sTree[id].nBuc;
  }
}
 
void LAZY_UPDATE(int id, int l, int r, int state) {
  // if state == NONE: no action
 
  if (state == ALL_BUC) {
    sTree[id].state = ALL_BUC;
 
  } else if (state == ALL_BAR) {
    sTree[id].state = ALL_BAR;
 
  } else if (state == INVERSE) {
    if (sTree[id].state == NONE) {
      sTree[id].state = INVERSE;
 
    } else if (sTree[id].state == ALL_BUC) {
      sTree[id].state = ALL_BAR;
 
    } else if (sTree[id].state == ALL_BAR) {
      sTree[id].state = ALL_BUC;
 
    } else if (sTree[id].state == INVERSE) {
      sTree[id].state = NONE;
    }
  }
}
 
void PROPAGATE(int id, int l, int m, int r) {
  LAZY_UPDATE(2*id+1, l, m, sTree[id].state);
  LAZY_UPDATE(2*id+2, m+1, r, sTree[id].state);
 
  sTree[id].state = NONE;
}
 
void MERGE(int id, int l, int m, int r) {
  sTree[id].nBuc = GET(2*id+1, l, m) + GET(2*id+2, m+1, r);
}
 
void build(int id, int l, int r) {
  sTree[id].state = NONE;
 
  if (l == r) {
    sTree[id].nBuc = (ar[l] == BUC) ? 1 : 0;
  } else {
    int m = (l + r)/2;
 
    build(2*id+1, l, m);
    build(2*id+2, m+1, r);
 
    MERGE(id, l, m, r);
  }
}
 
void update(int id, int l, int r, int xa, int xb, int state) {
  if ((xa <= l) && (r <= xb)) {
    LAZY_UPDATE(id, l, r, state);
  } else {
    int m = (l + r)/2;
 
    PROPAGATE(id, l, m, r);
 
    if (xa <= m) update(2*id+1, l, m, xa, xb, state);
    if (xb >  m) update(2*id+2, m+1, r, xa, xb, state);
 
    MERGE(id, l, m, r);
  }
}
 
int query(int id, int l, int r, int xa, int xb) {
  if ((xa <= l) && (r <= xb)) {
    return GET(id, l, r);
  }else{
    int m = (l + r)/2;
 
    PROPAGATE(id, l, m, r);
 
    int ret = 0;
    if (xa <= m) ret += query(2*id+1, l, m, xa, xb);
    if (xb >  m) ret += query(2*id+2, m+1, r, xa, xb);
 
    MERGE(id, l, m, r);
    return ret;
  }
}
 
int main() {
  int nTc;
  scanf("%d", &nTc);
 
  for (int jt = 0; jt < nTc; jt++) {
    int N, M, Q;
    scanf("%d", &M);
 
    N = 0;
    for (int i = 0; i < M; i++) {
      int T;
      scanf("%d", &T);
      scanf("%s", sc);
      int len = strlen(sc);
      for (int rep = 0; rep < T; rep++) {
        for (int j = 0; j < len; j++) {
          ar[N++] = sc[j] - '0';
        }
      }
    }
 
    build(0, 0, N-1);
 
    scanf("%d", &Q);
    printf("Case %d:\n", jt+1);
    int nQuery = 0;
    for (int nq = 0; nq < Q; nq++) {
      int a, b;
      scanf("%s %d %d", sc, &a, &b);
 
      if (sc[0] == 'F') {
        update(0, 0, N-1, a, b, ALL_BUC);
 
      } else if (sc[0] == 'E') {
        update(0, 0, N-1, a, b, ALL_BAR);
 
      } else if (sc[0] == 'I') {
        update(0, 0, N-1, a, b, INVERSE);
 
      } else {
        nQuery++;
        printf("Q%d: %d\n", nQuery, query(0, 0, N-1, a, b));
      }
    }
  }
 
  return 0;
}

Latihan

Tiada kata "bisa" tanpa latihan. Silakan Anda coba terapkan lazy propagation pada soal-soal berikut:
SPOJ RPAR
Rasanya butuh waktu beberapa bulan sampai saya benar-benar paham cara kerja lazy propagation. Setelah mengulas 3 contoh, saya berharap penjelasan tentang lazy propagation menjadi jelas dan Anda menangkap gambaran kasarnya tanpa perlu menghabiskan berbulan-bulan seperti saya.

Diposting oleh di
Label: , ,

Tidak ada komentar :

Posting Komentar

Langganan: Posting Komentar ( Atom )