UVa 12532 : Interval Product

題目 : UVa Link

給一串數字，並有 2 種操作 :

1. 改變陣列鍾某的數字的值
2. 問一個 range 中所有數字乘起來是正數還是負數或是 0

測資
Input :

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

Output :

0+-
+-+-0

解法

因為會有大量的查找與改變元素的值，因此使用 Segment Tree
可以先參考一下這篇 Segment Tree 教學

其中，Tree Node 要存的值是正號、負號或是 0
當要查找一個範圍中元素乘積的正負號時，若有一個元素為 0，則結果必為 0

完整程式碼

#include <iostream>
#include <vector>
#include <string>
#include <cmath>

using namespace std;

class Solution
{
public:
	Solution() : seg_tree(2 * MAX + 1)
	{
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout.tie(nullptr);
	}

	void set(const vector<int> &data)
	{
		size = data.size() - 1;

		initial(size);

		build(data, 1, 1, size);
	}

	void update(int idx, int old_val, int new_val)
	{
		auto t1 = tell(old_val);
		auto t2 = tell(new_val);

		if (t1 == t2)
			return;

		_update(1, 1, size, idx, t2);

		return;
 	}

	char query(int l, int r) const
	{
		auto type = _query(1, 1, size, l, r);

		switch (type)
		{
		case Sign::POS:
			return '+';
		case Sign::NEG:
			return '-';
		case Sign::ZERO:
			return '0';
		}
	}

private:
	enum class Sign { NEG, ZERO, POS };

	const int MAX = 100000;

	int size;
	vector<Sign> seg_tree;

	void initial(int n)
	{
		auto hight = log2(n);
		hight = ceil(hight) + 1;
		int s = static_cast<int>(pow(2, hight));

		seg_tree.clear();
		seg_tree.resize(s, Sign::POS);
	}

	void build(const vector<int> &data, int now_idx, int start, int end)
	{
		if (start == end)
		{
			seg_tree[now_idx] = tell(data[start]);
			return;
		}

		int m = mid(start, end);

		build(data, now_idx * 2, start, m);
		build(data, now_idx * 2 + 1, m + 1, end);

		seg_tree[now_idx] = tell2(seg_tree[now_idx * 2], seg_tree[now_idx * 2 + 1]);
	}

	void _update(int seg_idx, int start, int end, int data_idx, Sign type)
	{
		if (start == end)
		{
			seg_tree[seg_idx] = type;
			return;
		}

		int m = mid(start, end);

		if (start <= data_idx && data_idx <= m)
		{
			_update(seg_idx * 2, start, m, data_idx, type);
		}
		else
		{
			_update(seg_idx * 2 + 1, m + 1, end, data_idx, type);
		}

		seg_tree[seg_idx] = tell2(seg_tree[seg_idx * 2], seg_tree[seg_idx * 2 + 1]);
	}

	Sign _query(int seg_idx, int start, int end, int l, int r) const
	{
		if (l > end || r < start)
			return Sign::POS;

		if (l <= start && r >= end)
			return seg_tree[seg_idx];

		int m = mid(start, end);

		Sign ltype = _query(seg_idx * 2, start, m, l, r);
		Sign rtype = _query(seg_idx * 2 + 1, m + 1, end, l, r);

		return tell2(ltype, rtype);
	}

	int mid(int a, int b) const
	{
		return a + (b - a) / 2;
	}

	Sign tell(int n) const
	{
		if (n == 0)
			return Sign::ZERO;
		else if (n > 0)
			return Sign::POS;
		else
			return Sign::NEG;
	}

	Sign tell2(Sign a, Sign b) const
	{
		if (a == Sign::ZERO || b == Sign::ZERO)
			return Sign::ZERO;
		
		if (a != b)
			return Sign::NEG;
		else
			return Sign::POS;
	}
};

int main(void)
{
	Solution s;

	vector<int> data(100001);
	string ans(' ', 100000);

	int n, k, t;
	char c, an;
	int a, b;

	while (cin >> n)
	{
		cin >> k;

		data.clear();
		ans.clear();

		data.push_back(0);

		while(n--)
		{
			cin >> t;
			data.push_back(t);
		}

		s.set(data);

		while (k--)
		{
			cin >> c >> a >> b;

			if (c == 'C')
			{
				s.update(a, data[a], b);
				data[a] = b;
			}
			else
			{
				an = s.query(a, b);
				ans.push_back(an);
			}
		}

		cout << ans << endl;
	}
	
	return 0;
}