백준 10277번 JuQueen

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

10277번: JuQueen

문제 해석에 좀 애먹은 문제이다.

일반적인 레이지 세그트리와 비슷하지만 업데이트 시에 구간에 속한 원소중 하나가 (값이 증가되는 쿼리에서) N을 넘을 수 없고 (값이 감소되는 쿼리에서) 0보다 작아질 수 없으며 이 범위를 벗어나는 입력이 주어질 때는 모든 원소가 범위를 벗어나지 않으며 똑같은 값이 바뀌게 업데이트와 얼마의 수가 바뀌었는지 출력을 하면 된다.

 

 

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;

struct segtree{
	/*
    tree : 각 코어의 값
    lazy : 해당 노드에 누적된 변화량
    l : 해당 노드 범위의 최솟값
    r : 해당 노드 범위의 최댓값
    */
	vector<int> tree, lazy, l, h;
	void init(){
		tree.resize(4587520);
		lazy.resize(16777216);
		l.resize(16777216);
		h.resize(16777216);
	}
	void update(int a, int b, int c, int d, int e, int f){
		if (a < b){
			lazy[f * 2] += lazy[f];
			lazy[f * 2 + 1] += lazy[f];
		}
		else{
			tree[a] += lazy[f];
		}
		l[f] += lazy[f];
		h[f] += lazy[f];
		lazy[f] = 0;
		if (d < a || b < c) return;
		if (c <= a && b <= d){
			if (a < b){
				lazy[f * 2] += e;
				lazy[f * 2 + 1] += e;
			}
			else{
				tree[a] += e;
			}
			l[f] += e;
			h[f] += e;
			return;
		}
		int mid = (a + b) / 2;
		update(a, mid, c, d, e, f * 2);
		update(mid + 1, b, c, d, e, f * 2 + 1);
		l[f] = min(l[f * 2], l[f * 2 + 1]);
		h[f] = max(h[f * 2], h[f * 2 + 1]);
	}
    // c 위치의 코어의 값
	int query(int a, int b, int c, int d){
		if (a < b){
			lazy[d * 2] += lazy[d];
			lazy[d * 2 + 1] += lazy[d];
		}
		else tree[a] += lazy[d];
		l[d] += lazy[d];
		h[d] += lazy[d];
		lazy[d] = 0;
		if (c < a || b < c) return 0;
		if (a == b){
			return tree[a];
		}
		int mid = (a + b) / 2;
		int ll = query(a, mid, c, d * 2), rr = query(mid + 1, b, c, d * 2 + 1);
		l[d] = min(l[d * 2], l[d * 2 + 1]);
		h[d] = max(h[d * 2], h[d * 2 + 1]);
		return ll + rr;
	}
    // cd 구간의 최솟값
	int findl(int a, int b, int c, int d, int e){
		if (a < b){
			lazy[e * 2] += lazy[e];
			lazy[e * 2 + 1] += lazy[e];
		}
		else tree[a] += lazy[e];
		l[e] += lazy[e];
		h[e] += lazy[e];
		lazy[e] = 0;
		if (d < a || b < c) return 100000;
		if (c <= a && b <= d) return l[e];
		int mid = (a + b) / 2, ll = findl(a, mid, c, d, e * 2), rr = findl(mid + 1, b, c, d, e * 2 + 1);
		l[e] = min(l[e * 2], l[e * 2 + 1]);
		h[e] = max(h[e * 2], h[e * 2 + 1]);
		return min(ll, rr);
	}
    //cd 구간의 최댓값
	int findh(int a, int b, int c, int d, int e){
		if (a < b){
			lazy[e * 2] += lazy[e];
			lazy[e * 2 + 1] += lazy[e];
		}
		else tree[a] += lazy[e];
		l[e] += lazy[e];
		h[e] += lazy[e];
		lazy[e] = 0;
		if (d < a || b < c) return 0;
		if (c <= a && b <= d) return h[e];
		int mid = (a + b) / 2, ll = findh(a, mid, c, d, e * 2), rr = findh(mid + 1, b, c, d, e * 2 + 1);
		l[e] = min(l[e * 2], l[e * 2 + 1]);
		h[e] = max(h[e * 2], h[e * 2 + 1]);
		return max(ll, rr);
	}
};

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int C, N, O, X, A, B, S;
	segtree tree;
	tree.init();
	string query;

	cin >> C >> N >> O;
	for (int i = 0; i < O; i++){
		cin >> query;
		if (query == "state"){
			cin >> X;
			cout << tree.query(0, C - 1, X, 1) << '\n';
		}
		else{
			if (query == "change"){
				cin >> A >> S;
				B = A;
			}
			else cin >> A >> B >> S;
           	// limit는 제한을 넘지 않게 변화시킬수 있는 한계값
			if (S >= 0){
				int limit = N - tree.findh(0, C - 1, A, B, 1);
				tree.update(0, C - 1, A, B, min(S, limit), 1);
				cout << min(S, limit) << '\n';
			}
			else{
				int limit = -tree.findl(0, C - 1, A, B, 1);
				tree.update(0, C - 1, A, B, max(S, limit), 1);
				cout << max(S, limit) << '\n';
			}
		}
	}

	return 0;
}