링크
https://www.acmicpc.net/problem/5676
문제
오늘은 ACM-ICPC 대회 전 날이다. 상근이는 긴장을 풀기 위해서 팀원들과 근처 술집으로 갔다.
상근이와 친구들은 다음 날 있을 대회를 연습하기 위해서 작은 게임을 하기로 했다.
먼저, 선영이는 상근이에게 총 N개의 정수로 이루어진 수열 X1, X2, ... XN을 적어준다. 게임은 총 K번 라운드로 이루어져있고, 매 라운드마다 선영이는 상근이에게 명령을 하나씩 내린다. 명령은 아래와 같이 두 가지가 있다.
- 변경: 이 명령은 친구가 수열의 한 값을 바꾸고 싶을 때 사용한다.
- 곱셈: 선영이는 상근이에게 i와 j를 말한다. 상근이는 Xi × Xi+1 × ... × Xj-1 × Xj 의 값이 양수인지, 음수인지, 0인지를 대답한다.
곱셈 명령에서 상근이가 대답을 잘못했을 때의 벌칙은 소주 한 잔이다. 상근이는 갑자기 대회가 걱정되기 시작했다. 또, 상근이는 발머의 피크 이론을 증명하고 싶지 않다.
다행히 선영이는 상근이에게 노트북 사용을 허락했다. 상근이는 자신의 수학 실력보다 코딩 실력을 더 믿는다.
상근이를 돕는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다.
각 테스트 케이스의 첫째 줄에는 수열의 크기 N과 게임의 라운드 수 K가 주어진다. (1 ≤ N, K ≤ 105)
둘째 줄에는 총 N개의 숫자 Xi가 주어진다. (-100 ≤ Xi ≤ 100)
다음 K개 줄에는 선영이가 내린 명령이 주어진다. 명령은 C 또는 P로 시작한다.
C로 시작하는 명령은 변경 명령이고, 그 다음에 i와 V가 주어진다. Xi를 V로 변경하는 명령이다. (1 ≤ i ≤ N, -100 ≤ V ≤ 100)
P로 시작하는 명령은 곱셈 명령이고, 그 다음에 i와 j가 주어진다. (1 ≤ i ≤ j ≤ N)
각 테스트 케이스에 곱셈 명령은 항상 한 번 이상있다.
출력
각 테스트 케이스마다 곱셈 명령의 결과를 한 줄에 모두 출력하면 된다. 출력하는 i번째 문자는 i번째 곱셈 명령의 결과이다. 양수인 경우에는 +, 음수인 경우에는 -, 영인 경우에는 0을 출력한다.
예제 입력 및 출력
풀이 코드(C++)
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define sz(a) int((a).size())
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using ull = unsigned long long;
using dbl = double;
using ldb = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using wector = vector<vector<int>>;
using tii = tuple<int,int,int>;
const int INF = int(1e9) + 7;
template<typename T = int64_t, size_t sz = 20, typename F = plus<T>>
struct SegTree {
vector<T> tree; T t; F f{};
SegTree(T t = T()) : tree(1 << sz + 1, t), t(t) {}
explicit SegTree(T t, const F& f) : tree(1 << sz + 1, t), t(t), f(f) {}
void Init() {
for (int i = (1 << sz) - 1; i; i--) {
tree[i] = f(tree[i << 1], tree[i << 1 | 1]);
}
}
void Update(int i, T val) {
--i |= 1 << sz; tree[i] = val;
while (i >>= 1) tree[i] = f(tree[i << 1], tree[i << 1 | 1]);
}
T Query(int l, int r) {
T ret = t; --l |= 1 << sz, --r |= 1 << sz;
while (l <= r) {
if (l & 1) ret = f(ret, tree[l++]);
if (~r & 1) ret = f(ret, tree[r--]);
l >>= 1, r >>= 1;
}
return ret;
}
};
auto Multi = [](int& a,int& b) -> int{return a * b;};
int main() {
fastio;
int n,m;
while(cin >> n >> m){
SegTree<int, 20, decltype(Multi)> ST(1, Multi);
for(int i = 1; i <= n; i++){
int t; cin >> t;
if(t > 0) ST.Update(i, 1);
else if(t < 0) ST.Update(i, -1);
else if(t == 0)ST.Update(i, 0);
}
ST.Init();
while(m--){
int a,b;
char c; cin >> c >> a >> b;
// 변경
if(c == 'C'){
if(b > 0) ST.Update(a, 1);
else if(b < 0) ST.Update(a, -1);
else if(b == 0)ST.Update(a, 0);
}
else{
int result = ST.Query(a, b);
if(result == 1) cout << '+';
else if(result == -1) cout << '-';
else cout << 0;
}
}
cout << "\n";
}
return 0;
}