백준 10277 / C++

https://www.acmicpc.net/problem/10277

10277번: JuQueen

 

[ 풀이 ] 

문제조건이 특이하다. 값을 변경시킬때마다 증가하거나 감소시키는데 하나라도 0이나 N이 되면 변경행위를 멈춘다. 

 

예를 들어 2 3 3 7 7 7 이고 N이 9라고 하자. 4번부터 5번까지 +3만큼 변경시킨다고 하자. 

그럼 3 7 >>> 4 8 >>> 5 9 이고, 9가 된 수가 있으므로 변경을 마친다. 

 

그럼 확장해서 [a1 a2 ... ar]에서 +i만큼 변경한다면.. 이 중 최댓값을 찾고 max+i<=n일 때까지 값을 더해주면 된다. 

만약 max+i<=n이라면 i를 모두 더해주면 되고, max+i>n 이라면 n-max 만큼 더해주는것이 한계이다.

 

반대로 2 3 3 7 7 7 에서 1번부터 2번까지 -4만큼 변경한다고 하자. 

2 3 >> 1 2 >> 0 1 이고 0이 나왔으므로 변경을 마친다. 

 

그럼 확장해서 [a1 a2 ... ar]에서 -i만큼 변경한다면 이 중 최솟값을 찾고 min-i>=0일때까지 값을 더해주면 된다.

만약  min-i>=0이면 -i를 모두 더해주면 되고, min-i<0 이라면 -min만큼 더해주는게 한계이다. 

 

이제 이걸 구현해주면 된다. 구간덧셈은 레이지세그로 짜주면 된다. 구간최대와 최소도 필요하므로, 

최대, 최소를 같이 들고다니게 짜주면 된다. 

참고로 답이 틀려도 출력초과가 나올 수 있다. 구현이 좀 귀찮은 문제다. 

 

[ Code ]

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define mn first
#define mx second
const int MAX = 4588888;
int c, n, o, lazy[4 * MAX];
pii tree[4 * MAX];

// {최소, 최대} 합치는 함수 
pii merge(pii a, pii b) {
	return { min(a.mn, b.mn), max(a.mx , b.mx) };
}

struct segment_tree {
	// lazy propagation
	void propa(int node, int s, int e) {
		if (lazy[node]) {
			tree[node].mn += lazy[node];
			tree[node].mx += lazy[node];
			if (s != e) {
				lazy[2 * node] += lazy[node];
				lazy[2 * node + 1] += lazy[node];
			}
			lazy[node] = 0;
		}
	}
	// lazy update [qs,qe] +v 
	void upd(int node, int s, int e, int qs, int qe, int v) {
		propa(node, s, e);
		if (s > qe || e < qs) return;
		if (qs <= s && e <= qe) {
			lazy[node] += v;
			propa(node, s, e);
			return;
		}
		int m = (s + e) / 2;
		upd(2 * node, s, m, qs, qe, v);
		upd(2 * node + 1, m + 1, e, qs, qe, v);
		tree[node] = merge(tree[2 * node], tree[2 * node + 1]); // make
	}
	// return {min, max} in [qs, qe] 
	pii query(int node, int s, int e, int qs, int qe) {
		propa(node, s, e);
		if (s > qe || e < qs) return { 100000, -100000 }; // out case 
		if (qs <= s && e <= qe) return tree[node];
		int m = (s + e) / 2;
		pii L = query(2 * node, s, m, qs, qe);
		pii R = query(2 * node + 1, m + 1, e, qs, qe);
		return merge(L, R);
	}
}seg;

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> c >> n >> o;
	while (o--) {
		int x, s, a, b;
		string T; cin >> T;
		// change
		if (T == "change") {
			cin >> x >> s;
			int cur = seg.query(1, 0, MAX, x, x).first;
			// + 변경 
			if (s > 0) {
				cout << min(s, n - cur) << '\n';
				seg.upd(1, 0, MAX, x, x, min(s, n - cur));
			}
			// - 변경 
			else {
				cout << max(-cur, s) << '\n';
				seg.upd(1, 0, MAX, x, x, max(-cur, s));
			}
		}
		else if (T == "groupchange") {
			cin >> a >> b >> s;
			auto [m, M] = seg.query(1, 0, MAX, a, b);
			// + 변경
			if (s > 0) {
				cout << min(n - M, s) << '\n';
				seg.upd(1, 0, MAX, a, b, min(n - M, s));
			}
			// - 변경 
			else {
				cout << max(-m, s) << '\n';
				seg.upd(1, 0, MAX, a, b, max(-m, s));
			}
		}
		// 현재 값 
		else {
			cin >> x;
			cout << seg.query(1, 0, MAX, x, x).first << '\n';
		}
	}
}