ZeroJudge E457: 也是 Segment Tree 練習

題目敘述

本題採EOF方式收資料，每筆資料第一行有兩個正整數N和M，第二行會有N個數字代表數列中的數。接下來會有M行，每行會有一個字元和兩個整數A和B。當字元為C時，將數列中第A個位置的資料改為B。當字元為P時，如果位置A到B的乘積為正的話輸出+，負的話輸出-，0的話則輸出0。

範例輸入 #1

4 6

-2 6 0 -1

C 1 10

P 1 4

C 3 7

P 2 2

C 4 -5

P 1 4

5 9

1 5 -2 4 3

P 1 2

P 1 5

C 4 -5

P 1 5

P 4 5

C 3 0

P 1 5

C 4 -5

C 4 -5

範例輸出 #1

0+-

+-+-0

解題思路

建立線段樹的資料結構來更改資料及確認區段的乘積。

解題程式碼如下 (僅供參考)：

#include <iostream>
#include <vector>
using namespace std;

vector<int>num;
vector<int>tree;

void build(int l, int r, int id)
{
    if (l == r)
    {
        if(num[l] > 0) tree[id] = 1;
        else if(num[l] < 0) tree[id] = -1;
        else tree[id] = 0;
        return;
    }
    int middle = (l+r)/2;
    int L = id*2+1;
    int R = id*2+2;
    build(l, middle, L);
    build(middle+1, r, R);
    if((tree[L] < 0 and tree[R] < 0) or (tree[L] > 0 and tree[R] > 0)) tree[id] = 1;
    else if((tree[L] < 0 and tree[R] > 0) or (tree[L] > 0 and tree[R] < 0)) tree[id] = -1;
    else tree[id] = 0;
}

void change(int pos, long long int val, int l, int r, int id)
{
    if (l == r)
    {
        tree[id] = val;
        if(val > 0) { tree[id] = 1; num[l] = 1; }
        else if(val < 0) {tree[id] = -1;  num[l] = -1;}
        else {tree[id] = 0; num[l] = 0;}
        return;
    }
    int m = (l+r)/2;
    if (pos <= m) change(pos, val, l, m, (id*2)+1);
    else change(pos, val, m+1, r, (id*2)+2);
    tree[id] = tree[id*2+1] * tree[id*2+2];
}

int search(int l, int r , int L , int R , int id)
{
    if (l == r) return num[l];
    if (l == L && r == R) {
        return tree[id];
    }
    int m = (L+R)/2; //中間點 --> 左半邊：L~m；右半邊：m+1~R
    if (r <= m) //l跟r都小於m (因為r有小於m的話l就一定會小於m) --> 要找的資料都在左半邊
    {
        return search(l, r, L, m , id*2+1);
    }
    else if (l > m) //l跟r都大於m (因為l有大於m的話r就一定會大於m) --> 要找的資料都在右半邊
    {
        return search(l, r, m+1, R , id*2+2);
    }
    else //兩邊都有需要找的東西
    {
        return search(l, m, L, m , id*2+1) * search(m+1, r, m+1, R , id*2+2);
    }
}


int main() {
    int N, M;
    while (cin >> N >> M)
    {
        num.clear();
        tree.clear();
        for(int i = 0; i<(2*N)-1; i++)
        {
            tree.push_back(0);
        }
        for (int i = 0; i<N; i++)
        {
            int tmp;
            cin >> tmp;
            num.push_back(tmp);
        }
        build(0, N-1, 0);
        for (int i = 0; i<M; i++)
        {
            char ch;
            cin >> ch;
            if (ch == 'C')
            {
                int pos, val;
                cin >> pos >> val;
                change(pos-1, val, 0, N-1, 0);
            }
            else
            {
                int l, r;
                cin >> l >> r;
                int tmp = search(l-1, r-1, 0, N-1 , 0);
                if (tmp > 0) cout << '+';
                else if (tmp < 0) cout << '-';
                else cout << '0';
            }
        }
        cout << "\n";
    }
}