UVa11402 - Ahoy, Pirates!(線段樹)

UVa
字數統計： 2.5k   |   閱讀時間≈ 10分鐘

題目大意

在一個海盜島上有許多的海盜，它們都有被編號(從 0 至 n)，且它們都有一個陣營，此海盜島上只有兩個陣營 Buccaneer、Barbary。

現在來了一個大魔法師，他可以將從 0 ~ n 的人變成 Buccaneer or Barbary 陣營的人或是把某區間的人陣營對調，原本是 Buccaneer 變為 Barbary，Barbary 變為 Buccaneer

神知道有這件事情後，非常生氣，他會問大魔法師一個區間內有幾個 Buccaneer 海盜，沒有就殺了他，所以請幫忙解決此問題吧！

題目連結

重點觀念

  • 線段樹的學習與應用
    如果需要學習演算法，請參考 大衞的筆記 - Segment Tree 線段樹
  • 對於題目的仔細閱讀
  • 這題需要用到線段樹的高深操作，區間修改、懶人標記
  • 題目的指令在線段樹的懶人標記時，要如何判斷誰先誰後 (非常重要，它讓我花了 12hr 思考)
  • 題目的指令優化 (非常重要，它讓我花了 12hr 思考)

分析

好題，好題…，它讓我學到了一堆知識，雖然也讓我一堆時間飛走了QQQ。

這題比較麻煩的是要判斷 segment tree 懶人標記時，要如何判斷其先後順序，如果先將 0n 的人全部變成 Buccaneer 在對調，與先對調在將 0n 的人全部變成 Buccaneer，是不一樣的結果，因此我們在 push_down 跟 mod2 都需要比較多的處理，來判斷假如現在懶人標記是怎樣的情況時，我們現在又有這個指令時會對下面的子樹造成的影響是甚麼。

  • 定義 1 為把區間的人變成 Buccaneer
  • 定義 0 為把區間的人變成 Barbary
  • 定義 2 為區間的人對調

可以找出順序

  • 如果先進行 2 再進行 0，那就不需要進行 2，只需要進行 0
  • 如果先進行 2 再進行 1，那就不需要進行 2，只需要進行 1
  • 如果先進行 2 再進行 2，那完全不需要改動下面子樹
  • 如果先進行 1 再進行 2，那就只需要進行 0
  • 如果先進行 0 再進行 2，那就只需要進行 1
  • 如果先進行 1 再進行 0，那就只需要進行 0
  • 如果先進行 0 再進行 1，那就只需要進行 1

OK，現在知道進行區間修改時如果有兩個指令卡在同個節點時，我們就可以用這些規則來告訴下面子樹要進行甚麼規則。

那這樣就能夠透過 query 找到正確答案了！動手寫程式碼八

參考連結

Segment/Interval Tree - 2 by 林品諺
【題解】UVA 11402 Ahoy, Pirates! by YUI HUANG

心得

這題真的是很棒的好題，像這樣的順序，我直接大卡關….，我花了將近 4hr 在想這些順序問題，後來真的受不了了看 YUI HUANG 的題解，發現是我自作多情，我把她想太難了！不一定要每個步驟都做，可以把它們合併再讓子樹進行一個動作就好…，原先還想要對此線段樹紀錄 queue，來記錄順序然後進行區間查詢，結果記憶體爆了…。

後面把 queue 改成 string 則是超時，非常建議大家不要亂魔改資料結構阿QQQ，設計出來不是做此用途就不要亂用QQQ，就算用成功了也不一定可以成功，可能會有超時的問題…。

不過你是大發明家就不要記住我的話拉，我是笨蛋，只能靠努力的那種。

總之希望自己的未來可以一片光明，每天在不安感度過的感覺真的好可怕，希望自己學習的演算法與資料結構未來可以幫助我在人生的路上！

不然學習了這麼多的演算法，結果都沒用上，會不會有可能太不值了呢？

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

至於 大衞的筆記 - Segment Tree 線段樹 有做說明的部分，這邊就不在進行說明。

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
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 1024200
#define Lson(x) x<<1 /
#define Rson(x) (x<<1)+1
using namespace std;
int t, n, m, a, b, Qcnt, q, kase, len;
//題目資料， qcnt 是每次測試資料的 q 的查詢次數
//len //題目的海盜數值長度，也是計算當前 num 最大的長度
int num[MAXN]; //用來記錄海盜的陣營
struct tree{
    int l, r, v, z; //其中 z 為懶人標記，z 的 0,1,2 為操作的意思，-1 表示沒有需要操作
    void print(){ //無意義，debug 用
        cout << "l = " << l << " r = " << r << " v = " << v << " z = " << z << '\n';
    }
}node[MAXN*4];

void build(int l, int r, int x = 1){ //線段樹的 function build

    //cout << "x = " << x << " l = " << l << " r = " << r << '\n';
    node[x].l = l;
    node[x].r = r;
    node[x].z = -1;
    if(l == r){
        node[x].v = num[l];
        return;
    }

    int mid = (l+r)/2;
    build(l, mid, Lson(x));
    build(mid+1, r, Rson(x));
    node[x].v = node[Lson(x)].v + node[Rson(x)].v;
}

void mod1(int x, int cmd){ //方法 1，也就是定義操作的 0 and 1，線段樹的 function update
    int lson = Lson(x), rson = Rson(x); //定義左子樹與右子樹位置
    node[lson].z = cmd; //更改懶人標記，規則上面有提到，直接更改不需要判斷先後順序
    node[rson].z = cmd;

    node[lson].v = (node[lson].r-node[lson].l+1) * cmd; //計算數值，一個小技巧，題目的 1 剛好就是要查詢的數量，
    node[rson].v = (node[rson].r-node[rson].l+1) * cmd; //因此我們直接用 * 1 or * 0，就可以算值
}

void mod2(int x, int cmd){ //方法 2，也就是定義操作的 2，線段樹的 function update
    int lson = Lson(x), rson = Rson(x);  //定義左子樹與右子樹位置

    //更改懶人標記，規則上面有提到，直接更改不需要判斷先後順序
    if(node[lson].z == 2) node[lson].z = -1; 
    //上述有說到的規則，如果先進行 ``2`` 再進行 ``2``，那完全不需要改動下面子樹
    else if(node[lson].z != -1) node[lson].z ^= 1;
    //如果先進行 ``0`` 再進行 ``2``，那就只需要進行 ``1``
    //如果先進行 ``1`` 再進行 ``2``，那就只需要進行 ``0``
    else node[lson].z = cmd;
    //不需要合併操作，所以就直接寫

    if(node[rson].z == 2) node[rson].z = -1; //與上面相同，只是子樹換另外一邊
    else if(node[rson].z != -1) node[rson].z ^= 1;
    else node[rson].z = cmd;

    node[lson].v = (node[lson].r-node[lson].l+1) - node[lson].v;  
    //對調，於是先算出區間最大數量減掉當前數量就是對調的數值
    node[rson].v = (node[rson].r-node[rson].l+1) - node[rson].v;
}

void push_down(int x){ //線段樹的 push_down function build
    if(node[x].z == 0) mod1(x, 0); //z = 0 就去 mod1，其中 z 的值表示操作 x
    if(node[x].z == 1) mod1(x, 1);
    if(node[x].z == 2) mod2(x, 2);
    node[x].z = -1; //向下延伸完畢，現在改為 -1
}

void push_mod1(int a, int b, int cmd, int x = 1){ //線段樹的 push_down function update
//詳細請看大衛的演算法，這邊是把方法拉出來寫
    if(a <= node[x].l && b >= node[x].r){
        node[x].v = (node[x].r-node[x].l+1) * cmd;
        node[x].z = cmd;
        return;
    }
    push_down(x);

    int mid = (node[x].l+node[x].r) / 2;
    if(a <= mid) push_mod1(a, b, cmd, Lson(x));
    if(b > mid) push_mod1(a, b, cmd, Rson(x));
    node[x].v = node[Lson(x)].v + node[Rson(x)].v;
}

void push_mod2(int a, int b, int cmd, int x = 1){ //線段樹的 push_down function update
//詳細請看大衛的演算法，這邊是把方法拉出來寫
    if(a <= node[x].l && b >= node[x].r){
        node[x].v = (node[x].r-node[x].l+1) - node[x].v;

        if(node[x].z == 2) node[x].z = -1;
        else if (node[x].z != -1) node[x].z ^= 1;
        else node[x].z = cmd;

        return;
    }
    push_down(x);

    int mid = (node[x].l+node[x].r) / 2;
    if(a <= mid) push_mod2(a, b, cmd, Lson(x));
    if(b > mid) push_mod2(a, b, cmd, Rson(x));
    node[x].v = node[Lson(x)].v + node[Rson(x)].v;
}

int query(int l, int r, int x = 1){ //線段樹的 query function 
    if(node[x].l >= l && node[x].r <= r) return node[x].v;
    push_down(x);

    int mid = (node[x].l+node[x].r) / 2, ans = 0;
    if(l <= mid) ans += query(l, r, Lson(x));
    if(r > mid) ans += query(l, r, Rson(x));
    //cout << "q x = " << x << " ans = " << ans << '\n';
    return ans;
}


int main(){
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    string temp;
    cin >> t;
    while(t--){ 
        Qcnt = 1; //先定義題目的查詢數量
        cout << "Case " << ++kase << ":\n";
        cin >> n;
        len = 1; //題目的海盜數值長度
        while(n--){ //輸入題目特別的格式，字串重複 n 次，用 0,1 表示海盜的陣營
            cin >> m >> temp;
            for(int i = 0; i < m; i++){ //重複 n 次此字串
                for(int j = 0; j < temp.length(); j++) num[len++] = temp[j] - '0';
                //把字串的值給 num
            }
        }

        build(1, len);
        cin >> q; //題目資料
        for(int i = 0; i < q; i++){ //題目的指令
            cin >> temp >> a >> b; //輸入資料
            a++; b++; //index start from 1，由於題目 index 從 0 開始，我們線段樹從 1 開始
            if(temp == "F") push_mod1(a, b, 1); //F 是操作 1
            else if(temp == "E") push_mod1(a, b, 0); //E 是操作 0
            else if(temp == "I") push_mod2(a, b, 2); //I 是操作 2
            else if(temp == "S") cout << "Q" << Qcnt++ << ": " << query(a, b) << "\n"; //查詢指令

        }
    }
    return 0;
}

用紙筆去 Debug

因為只是自己在思考過程中隨手做的筆記，覺得不是對讀者這麼有幫助，因此放在文章最下面。

有時候用想或用看的可能不太能夠懂這演算法，那就用寫的吧！這是大衛我自己學習的手稿，紀錄者我的學習過程。

  • 版權聲明： 本部落格所有文章除有特別聲明外，均採用 Apache License 2.0 許可協議。轉載請註明出處！
  • © 2020-2024 John Doe
  • Powered by Hexo Theme Ayer
  • PV: UV: