잔디
시간 제한1초메모리 제한128 MB
최대 10억 개 식물에 대해 성장, 상한 고정, 좌우 깎기, 클램프 연산을 받아 효율적으로 처리하면서 높이 합을 구하는 문제입니다.
문제
Edo는 정원에 있는 잔디를 관리한다. 정원은 왼쪽에서 오른쪽으로 놓인 N개의 잔디로 표현되며, 처음 모든 높이는 0mm이다. 각 잔디의 높이는 최대 Hmm를 넘을 수 없다.
프로그램은 M개의 작업을 순서대로 처리하면서, 필요할 때 모든 잔디 높이의 합을 출력해야 한다.
작업은 다음 다섯 종류 중 하나이다.
N X: 모든 잔디가Xmm 자란다. 어떤 잔디의 높이가H를 넘게 되면H에서 멈춘다.L X: 왼쪽에서부터X개의 잔디를 완전히 깎아 높이를0으로 만든다.D X: 오른쪽에서부터X개의 잔디를 완전히 깎아 높이를0으로 만든다.S X: 잔디깎이의 높이를X로 맞추고 전체 정원을 깎는다. 높이가X보다 큰 잔디는X가 되고, 나머지는 그대로 둔다.Z: 현재 모든 잔디 높이의 합을 구한다.
입력
첫 줄에 세 양의 정수 N, H, M이 주어진다. N은 잔디의 개수, H는 잔디의 최대 높이, M은 작업의 수를 뜻한다.
1 <= N <= 10^9, 1 <= H <= 10^6, 1 <= M <= 10^6이다.
다음 M줄에는 작업이 한 줄에 하나씩 주어진다. 작업은 위에서 설명한 다섯 종류 중 하나이다. N, L, D, S 작업은 대문자 한 글자와 정수 X가 공백 하나로 구분되어 주어진다. Z 작업에는 추가 정수가 없다.
L, D 작업에서는 1 <= X <= N이고, N, S 작업에서는 1 <= X <= H이다.
출력
각 Z 작업마다 현재 모든 잔디 높이의 합을 한 줄에 하나의 정수로 출력한다. 출력 순서는 입력에서 Z 작업이 등장한 순서와 같아야 한다.
높이의 합은 2^32보다 클 수 있다.