UVa12532 - Interval Product(線段樹)

題目大意

你現在在 pub 裡面，明天要程式設計競賽，朋友給你一個問題如果你沒有回答出來，就會要求你喝一杯酒，但你酒量不好，不可以讓自己失敗，幸好朋友給妳時間寫程式，朋友給你的題目如下：

會給你一個數列，之後會給你兩個命令

• C 改變數列中的某個數子
• P 請你查詢某個區間的所有數字相乘是正或負或零。

題目連結

重點觀念

• 線段樹的學習與應用
  如果需要學習演算法，請參考 大衞的筆記 - Segment Tree 線段樹
• 對於題目的仔細閱讀
• 用到線段樹的單點修改
• 題目只需要你輸出區間的結果是正或負或零

分析

一個簡單的線段樹，只要將題目完全看過一遍後，再搭配所學過的線段樹知識就可以解出此題，那這裡有一個小麻煩就是題目的數列的數字值是在 100 ~ -100 中，我們如果存數字進去會導致相乘溢位的狀態。

因此我們改成在線段樹中儲存 0, -1, 1，分別代表者 零、負數、正數的情況，正數相乘還是 1、正負數相乘就是 -1，任意數乘零都是零，剛好用這三個關鍵的數子就可以充分表達題目要我們輸出的結果是正數、負數、零。

心得

最近覺得寫演算法的時間有點多，變得其他時間不好顧呢。其實也不是寫演算法的時間變多，只是上了大二後事情變多變成每件事情都要盡快完成，有時候就會覺得這種需要花大量時間完成的事情似乎沒有甚麼 CP 值呢！內心有點迷茫，希望未來的我可以知道到底怎樣做對我最好。

題目程式碼

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

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

比較需要注意的是此題沒有區間修改的問題，因此我們就不需要寫 push_down 有關於區間修改的 function。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 100020
#define Lson(x) (x<<1)
#define Rson(x) ((x<<1)+1)
using namespace std;
int num[MAXN];
int N, K, temp, a, b;
string cmd, result;　//cmd 存題目的指令是查詢還是修改值 result 存結果
struct Node{
    int l, r;
    int v;
}node[4 * MAXN];


void build(int l, int r, int x = 1){ //線段樹的 function build
    node[x].l = l;
    node[x].r = r;
    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 modify(int p, int v, int x = 1){ //線段樹的 function modify
    if(node[x].l == p && node[x].r == p){
        node[x].v = v;
        return;
    }

    int mid = (node[x].l+node[x].r) / 2;
    if(p <= mid) modify(p, v, Lson(x));
    if(p > mid) modify(p, v, Rson(x));
    node[x].v = node[Lson(x)].v * node[Rson(x)].v;
    //因為題目要求，注意這裡是乘法
    //不要跟 大衞的筆記中的線段樹說明搞混
}

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

    int mid = (node[x].l+node[x].r) / 2, ans = 1;
    if(l <= mid) ans *= query(l, r, Lson(x));
    if(r > mid) ans *= query(l, r, Rson(x));
    return ans;
    //因為題目要求，注意這裡是乘法
    //不要跟 大衞的筆記中的線段樹說明搞混
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    while(cin >> N >> K){
        for(int i = 1; i <= N; i++){ //輸入題目數列
            cin >> temp;
            if(temp > 0) temp = 1; //將數列的值，壓縮成 正、負、零三種狀態
            else if(temp < 0) temp = -1;
            else if(temp == 0) temp = 0;
            num[i] = temp;
        }
        build(1, N);

        for(int i = 1; i <= K; i++){
            cin >> cmd >> a >> b;
            if(cmd == "C"){ //進入線段樹 modify function
                if(b > 0) b = 1;
                else if(b < 0) b = -1;
                else if(b == 0) b = 0;
                modify(a, b);
            }
            if(cmd == "P"){ //進入線段樹 query function
                int ans = query(a, b);

                if(ans > 0) result = "+";
                else if(ans < 0) result = "-";
                else if(ans == 0) result = "0";
                cout << result;
            }
        }
        cout << '\n';
    }
    return 0;
}