ZeroJudge E457: 也是 Segment Tree 練習

同題：UVa 12532 – Interval Product

最多 N = 105 個數字 X1 … XN，K 個詢問 {只有兩種格式} CIV 或 PIJ

CIV 是將 Xi 的值改為 V， PIJ 是問 Xi ~ Xj 連續乘積的符號 {正、負、或 0} 輸出 +-0

有多組測資，每組輸出一列，請參考範例

範例測資

範例輸入範例輸出
EOF 輸入，每筆資料第一行有兩個正整數 N 和 M，第二行會有 N 個數字代表數列中的數。接下來會有 M 行，每行會有一個字元和兩個整數 A 和 B。當字元為 C 時，將數列中第 A 個位置的資料改為 B。當字元為 P 時，如果位置 A 到 B 的乘積為正的話輸出「+」，負的話輸出「-」，0的話則輸出「0」。
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		0+-
+-+-0
ZeroJudge E457 範例測資

解題思路

建立線段樹的資料結構來更改資料及確認區段的乘積。(範例程式碼內有註解來解釋搜尋原理)

範例程式碼－ZeroJudge E457: 也是 Segment Tree 練習

#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";
    }
}

//ZeroJudge E457
//Dr. SeanXD
標籤

相關文章

發佈留言