BOJ)10277 JuQueen

문제: icpc.me/10277

C개의 코어가 있을 때 쿼리를 받아 3종류의 연산을 처리해주면 되는 문제이다.

단 코어의 하한선은 0이고 상한선은 N으로 입력으로 주어진다.

쿼리는 다음과 같다 

change X S    코어X를 S만큼 증가시켜라

groupchange A B S    코어 A부터 코어B까지 전부 S만큼 증가시켜라

state X  코어X의 값을 출력하라

단, 코어를 증가시키다가 상한이나 하한에 다다를시 증가를 멈춘다.

change나 groupchange 같은 경우 증가혹은 감소시킨 계수를 출력해야 하는데 우리는 코어를 증가시키다 상한이나 하한에 도달하는 경우를 판단해야한다.

따라서 우리는 구간에 대한 최댓값 최솟값을 세그먼트 트리로 관리하여 구간을 증가 시킬 시 상한혹은 하한에 도달하는지 여부를 판단하여 상한 혹은 하한까지만 증가혹은 감소 시킬 수 있다.

이때 우리는 구간에 대한 갱신연산이 있으므로 구간에 대한 증가연산은 lazy propagation 기법을 사용하여 시간을 줄여주어 TLE를 피할 수 있다.

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <iostream>
#define MAX_C 4587520
#define INF 987654321
using namespace std;
int c, n, o, minseg[4 * MAX_C], maxseg[4 * MAX_C], minlazy[4 * MAX_C], maxlazy[4 * MAX_C], x, y, z;
void u_maxlazy(int node, int x, int y) {
    if (!maxlazy[node])
        return;
    maxseg[node] += maxlazy[node];
    if (x != y) {
        maxlazy[node * 2] += maxlazy[node];
        maxlazy[node * 2 + 1] += maxlazy[node];
    }
    maxlazy[node] = 0;
}
void u_minlazy(int node, int x, int y) {
    if (!minlazy[node])
        return;
    minseg[node] += minlazy[node];
    if (x != y) {
        minlazy[node * 2] += minlazy[node];
        minlazy[node * 2 + 1] += minlazy[node];
    }
    minlazy[node] = 0;
}
void max_update(int lo, int hi, int val, int node, int x, int y) {
    u_maxlazy(node, x, y);
    if (y < lo || hi < x)
        return;
    if (lo <= x&&y <= hi) {
        maxlazy[node] += val;
        u_maxlazy(node, x, y);
        return;
    }
    int mid = (x + y) >> 1;
    max_update(lo, hi, val, node * 2, x, mid);
    max_update(lo, hi, val, node * 2 + 1, mid + 1, y);
    maxseg[node] = max(maxseg[node * 2], maxseg[node * 2 + 1]);
}
void min_update(int lo, int hi, int val, int node, int x, int y) {
    u_minlazy(node, x, y);
    if (y < lo || hi < x)
        return;
    if (lo <= x&&y <= hi) {
        minlazy[node] += val;
        u_minlazy(node, x, y);
        return;
    }
    int mid = (x + y) >> 1;
    min_update(lo, hi, val, node * 2, x, mid);
    min_update(lo, hi, val, node * 2 + 1, mid + 1, y);
    minseg[node] = min(minseg[node * 2], minseg[node * 2 + 1]);
}
int maxquery(int lo, int hi, int node, int x, int y) {
    u_maxlazy(node, x, y);
    if (y < lo || hi < x)
        return 0;
    if (lo <= x&&y <= hi)
        return maxseg[node];
    int mid = (x + y) >> 1;
    return max(maxquery(lo, hi, node * 2, x, mid), maxquery(lo, hi, node * 2 + 1, mid + 1, y));
}
int minquery(int lo, int hi, int node, int x, int y) {
    u_minlazy(node, x, y);
    if (y < lo || hi < x)
        return INF;
    if (lo <= x&&y <= hi)
        return minseg[node];
    int mid = (x + y) >> 1;
    return min(minquery(lo, hi, node * 2, x, mid), minquery(lo, hi, node * 2 + 1, mid + 1, y));
}
int main() {
    scanf("%d%d%d", &c, &n, &o);
    for (int i = 0; i < o;i++) {
        string a;
        cin >> a;
        int res;
        if (a == "state") {
            scanf("%d", &x);
            res = maxquery(x, x, 1, 0, c - 1);
        }
        else if (a == "change") {
            scanf("%d%d", &x, &y);
            int v = maxquery(x, x, 1, 0, c - 1);
            if (v + y > n) {
                max_update(x, x, n - v, 1, 0, c - 1);
                min_update(x, x, n - v, 1, 0, c - 1);
                res = n - v;
            }
            else if (v + y < 0) {
                max_update(x, x, -v, 1, 0, c - 1);
                min_update(x, x, -v, 1, 0, c - 1);
                res = -v;
            }
            else {
                max_update(x, x, y, 1, 0, c - 1);
                min_update(x, x, y, 1, 0, c - 1);
                res = y;
            }
        }
        else {
            scanf("%d%d%d", &x, &y, &z);
            if (z > 0) {
                int v = maxquery(x, y, 1, 0, c - 1);
                if (v + z > n) {
                    max_update(x, y, n - v, 1, 0, c - 1);
                    min_update(x, y, n - v, 1, 0, c - 1);
                    res = n - v;
                }
                else {
                    max_update(x, y, z, 1, 0, c - 1);
                    min_update(x, y, z, 1, 0, c - 1);
                    res = z;
                }
            }
            else {
                int v = minquery(x, y, 1, 0, c - 1);
                if (v + z < 0) {
                    max_update(x, y, -v, 1, 0, c - 1);
                    min_update(x, y, -v, 1, 0, c - 1);
                    res = -v;
                }
                else {
                    max_update(x, y, z, 1, 0, c - 1);
                    min_update(x, y, z, 1, 0, c - 1);
                    res = z;
                }
            }
        }
        printf("%d\n", res);
    }
    return 0;
}