앳코더90 - 029 - Long Bricks（★5）

https://atcoder.jp/contests/typical90/tasks/typical90_ac

029 - Long Bricks（★5）

 

크기가 W인 가로로 이루어진 공간에 N개의 벽돌을 쌓는다.

범위 l, r이 주어질때 l~r까지 벽돌을 하나씩 놓는다. 놓는 위치에 이미 벽돌이 있다면 그 위에 쌓는데 범위 내에서 가장 높은 벽돌의 높이에서 하나 쌓은만큼 나머지 범위도 그만큼 쌓는다.

ex) 1 3 1 상태에서 범위가 1 2 면 4 4 1이 된다. 3+1 을 1,2에 둘다 적용

 

문제 형식과 범위를 보면 세그를 쓰는 문제임을 생각할 수 있고  한 곳을 갱신하는게 아니라 구간을 갱신해야되기 때문에 lazy세그를 써야함을 알 수 있다. atcoder에있는 레이지세그 구현체를 사용해보자.

 

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_set>
#include <numeric>
#include <random>
#include <iostream>
#include <unordered_map>
#include <atcoder/all>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back

using namespace std;
using namespace atcoder;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<long long> vll;

const int INF = 2000000000;
const double pi = 3.14159265358979;
const int MOD = 100000;

void yesno(bool a)
{
	if (a)
		cout << "YES\n";
	else
		cout << "NO\n";
}

ll W, N;
vi ans;

int op(int a, int b) { return max(a, b); }
int e() { return 0; }
int mapping(int f, int x) { return (f == INF ? x : f); }
int composition(int f, int g) { return (f == INF ? g : f); }
int id() { return INF; }

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> W >> N;

	lazy_segtree<int,op,e,int,mapping,composition,id> lazy(W);
	
	rep(i, N)
	{
		int a, b;
		cin >> a >> b;
		a--;
		int c = lazy.prod(a, b);
		ans.push_back(c+1);
		lazy.apply(a, b, c+1);
	}

	for (auto i : ans)
		cout << i << "\n";

	return 0;
}

 

 

AtCoder에서 제공하는 lazy_segtree 클래스는 Lazy Propagation을 지원하는 세그먼트 트리의 구현체입니다. 

---

생성자 (Constructors)

lazy_segtree는 두 가지 방식으로 생성할 수 있습니다.

1. lazy_segtree<S, op, e, F, mapping, composition, id> seg(int n);
   • 길이가 nnn인 배열을 생성합니다.
   • 배열의 모든 요소는 기본값 e()e()e()로 초기화됩니다.
2. lazy_segtree<S, op, e, F, mapping, composition, id> seg(vector<T> v);
   • 입력 벡터 vvv의 길이에 맞는 배열을 생성합니다.
   • 배열은 벡터 vvv의 값으로 초기화됩니다.

---

정의해야 할 함수 및 타입

lazy_segtree를 사용하려면, 아래의 타입과 함수들을 사용자가 정의해야 합니다.

1. Monoid의 타입 SSS

• 세그먼트 트리에서 저장할 데이터의 타입을 정의합니다. 예: int, pair<int, int>, 또는 사용자 정의 구조체.

2. Binary Operation opopop (병합 연산)

• SSS 타입의 두 값을 입력받아 병합하는 함수입니다.
• 예: 구간 합을 구하려면 덧셈 연산 op(a,b)=a+bop(a, b) = a + bop(a,b)=a+b, 최대값을 구하려면 op(a,b)=max⁡(a,b)op(a, b) = \max(a, b)op(a,b)=max(a,b) 등을 정의합니다.

3. Identity Element eee (항등원)

• 병합 연산 opopop에 대한 항등원을 반환하는 함수입니다.
• 예: 덧셈이라면 e()=0e() = 0e()=0, 최댓값 연산이라면 e()=−∞e() = -\inftye()=−∞.

4. Mapping Function mappingmappingmapping (갱신 함수)

• Lazy Propagation에서 사용되는 "맵 함수"로, 특정 Lazy 값 FFF를 현재 구간 값 SSS에 적용하는 함수입니다.
• 반환값은 "갱신된 SSS" 값입니다.
• 예: 구간의 값을 특정 값으로 설정하거나, 특정 값을 더할 때 사용합니다.

5. Composition Function compositioncompositioncomposition (Lazy 값 병합)

• 두 Lazy 값 FFF를 병합하여 새로운 Lazy 값을 반환하는 함수입니다.
• Lazy Propagation에서 Lazy 값을 구간에 전달할 때 사용하는 함수입니다.

6. Identity Lazy Value ididid (Lazy 항등원)

• Lazy 값 FFF의 항등원을 반환하는 함수입니다.
• Lazy Propagation에서 아무 갱신도 없는 상태를 나타냅니다.

사전정의하는 부분은 gpt의 답변을 참고하고 다른 사람 코드를 찾아보았다.

 

그리고 주의할점은 대부분의 레이지세그는 0-based기 때문에 범위를 a-1~b-1로 해줘야된다. b--를 하지않는이유는 prod함수의 범위가 a~b-1 이기 때문이다.