UVa 12532 – Interval Product
Up to N = 10^5 numbers X1 ... XN, and K queries {only two formats} CIV or PIJ
CIV means changing the value of Xi to V, while PIJ means outputting the sign {positive, negative, or 0} of the consecutive product of Xi to Xj.
For multiple sets of input data, each set should have one output line. Please refer to the example for details.
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The input should end with EOF. Each set of data starts with two positive integers, N and M, on the first line. The second line contains N numbers representing the sequence. Following that are M lines, each containing a character and two integers, A and B. | When the character is 'C,' replace the data at the Ath position in the sequence with B. When the character is 'P,' if the product of the numbers from position A to B is positive, output "+"; if negative, output "-"; if zero, output "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 |
Thought Process
Build a segment tree data structure to update data and confirm the product of a segment.
Sample Code－ZeroJudge E457: Segment Tree Practice
#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