2022.07.22. (중간 평가) 풀이

A. [20039] Coronavirus Trend (Platinum II)

의도한 태그: Segment Tree + DP

우선, 두 수의 차이를 계산해야 하니 길이가 \( N - 1 \) 차이 배열 \( D_{i} = A_{i+1} - A_{i} \)을 만들어볼 수 있습니다.

이를 통해 문제를 재정의하면, Difference 배열에서 값을 적절히 합쳐서 고립된 +, -가 없도록 만드는 문제가 됩니다.

(문제의 조건에 의해, 0은 고려하지 않아도 됩니다.)

 

이제, DP로 이 문제를 풀어봅시다.

\( DP_{i, s, c} := A_{[1, i]} \)에 대해, 마지막 수의 부호가 \( s \)이며, 이 부호가 현재 \( c \)회 연속으로 나오게 하기 위해 필요한 합치기의 최소 횟수

문제 특성상, \( c \ge 2 \)는 그냥 \( c = 2 \)로 모아줘도 됩니다.

 

DP니까, 점화식을 세워야겠죠?

\( s = - \)일 때는 \( s = + \)일 때랑 부호만 바꿔서 처리하면 되니, 지금부터는 \( s = + \)일 때만 고려하도록 하겠습니다.

• \( c = 1 \)인 경우, 다른 부호에서 여기로 넘어오는 경우이거나, 선택한 값이 없음 (= 0)에서 첫 부호를 선택한 경우입니다. 문제 조건에 의해서, (다른 부호, 1회 선택)은 여기서 끌고 오면 안 됩니다!
• \( c \ge 2 \)인 경우, 같은 부호의 개수를 늘리는 경우입니다.

 

이를 식으로 적어보면

\( DP_{i, +, 1} = \min_{A_{(j, i]} > 0} (DP_{j, -, 2} + i-j) \)와
\( DP_{i, +, 1} = i-1 \text{ if } A_{[1, i]} > 0, \infty \text{ otherwise} \) 중 더 작은 값
\( DP_{i, +, 2} = \min_{A_{(j, i]} > 0} ( \min(DP_{j, +, 1}, DP_{j ,+, 2}) + i-j ) \)

하지만 이대로 구현해도 \( O(N^2) \)이니, TLE를 받게 됩니다.

그래서 각 \( (s, c) \) 쌍에 대해 세그먼트 트리를 만들고, 각 리프 정점에는 \( DP_{i, s, c} \)를 저장해주면

Range Minimum Query로 문제를 빠르게 풀 수 있게 됩니다.

int arr[500020], dif[500020];
map<int, int> cvt; set<int> cs; int cc = 0;

const int INF = 1e9;
const int N = 524288; int seg[3][2][1048576];
void upd(int sgn, int cnt, int pos, int val){ cnt -= 1; pos += N-1;
	seg[sgn][cnt][pos] = val; pos >>= 1;
	while (pos){
		seg[sgn][cnt][pos] = max(seg[sgn][cnt][pos<<1], seg[sgn][cnt][pos<<1|1]);
		pos >>= 1;
	}
}
int qry(int sgn, int cnt, int st, int ed){ cnt -= 1; st += N-1; ed += N-1;
	int res = -INF;
	while (st <= ed){
		if (st & 1){ res = max(res, seg[sgn][cnt][st]); st += 1; }
		if (~ed & 1){ res = max(res, seg[sgn][cnt][ed]); ed -= 1; }
		if (st > ed){ break; }
		st >>= 1; ed >>= 1;
	}
	return res;
}

void Main(){
	int n; cin >> n;
	for (int i = 0; i < n; i++){ cin >> arr[i]; cs.insert(arr[i]); }
	for (int x : cs){ cc += 1; cvt[x] = cc; }
	for (int i = 0; i < n; i++){ arr[i] = cvt[ arr[i] ]; }
	for (int i = 1; i < n; i++){ dif[i] = arr[i] - arr[i-1]; }
	//for (int i = 1; i < n; i++){ cout << dif[i] << ' '; } cout << endl;
	for (int i : {0, 1, 2}){ for (int j : {0, 1}){ for (int k = 1; k < N+N; k++){ seg[i][j][k] = -INF; } } }
	for (int i = 1; i < n; i++){
		upd(0, 1, arr[i-1], 1);
		for (int sgn : {1, 2}){
			int st = sgn==1 ? arr[i]+1 : 1; int ed = sgn==1 ? N : arr[i]-1;
			int r1 = max({ qry(3-sgn, 2, st, ed), qry(0, 1, st, ed) });
			int r2 = max({ qry(sgn, 1, st, ed), qry(sgn, 2, st, ed) });
			upd(sgn, 1, arr[i], r1+1); upd(sgn, 2, arr[i], r2+1);
			//cout << "DP " << arr[i] << ' ' << sgn << ' ' << 1 << " = " << r1+1 << endl;
			//cout << "DP " << arr[i] << ' ' << sgn << ' ' << 2 << " = " << r2+1 << endl;
		}
		//cout << endl;
	}
	int ans = max( qry(1, 2, 1, N), qry(2, 2, 1, N) );
	cout << max(ans, 0);
}

B. [18302] Counting Trees (Platinum II)

의도한 태그: Segment Tree (RMQ), Hard

현재 보고 있는 구간이 \( [st, ed] \)라고 합시다.

그럼, 그 구간 내에 있는 가장 작은 수, 즉 루트가 될 수 있는 정점의 값이 \( m \)이라고 합시다.

 

만약 \( m \)의 개수가 \( k \)개라고 한다면, \( k \)개의 정점으로 트리를 만드는 경우의 수 = \( C_{k} \)가지 경우가 가능합니다. (여기서 \( C_{x} = x \)번째 카탈란 수입니다.)

 

왜 카탈란 수로 표현이 되냐면, 초항은 당연히 \( C_{0} = 1 \)이고,

점화식을 써보면 왼쪽에 \( l \)개, 오른쪽에 \( n-l-1 \)개를 남기는 경우를 다 합하는 방식이라

\( C_{n} = C_{0}C_{n-1} + C_{1}C_{n-2} + \cdots + C_{n-1}C_{0} \)의 점화식이 나오기 때문입니다.

 

그래서 어떤 구간에 대해서 \( m \)의 개수 \( k \)를 세준 뒤, 답에 \( C_{k} \)를 곱해주고,

\( m \)을 기준으로 구간을 다 나눠서 재귀적으로 탐색해주면 됩니다.

const ll mod = 1e9 + 7;
const int M = 1000000; ll ctl[1000020];

ll fpow(ll a, ll b){
	ll res = 1, mul = a, bit = b;
	while (bit){
		if (bit & 1){ res = res*mul % mod; }
		mul = mul*mul % mod; bit >>= 1;
	}
	return res;
}
inline ll finv(ll x){ return fpow(x, mod-2); }

const int N = 1048576;
pi2 seg[2097160];
pi2 qry(int st, int ed){ st += N-1; ed += N-1;
	pi2 res = {N, N};
	while (st <= ed){
		if (st & 1){ res = min(res, seg[st]); st += 1; }
		if (~ed & 1){ res = min(res, seg[ed]); ed -= 1; }
		if (st > ed){ break; }
		st >>= 1; ed >>= 1;
	}
	return res;
}

int arr[1000020];
int ptr[1000020], val[1000020];

ll ans = 1;
void dnc(int st, int ed){
	if (st > ed){ return; }
	int cnt = 1; int p = qry(st, ed).sc;
	dnc(st, p-1);
	while (p <= ed){
		int pp = ptr[p];
		if (pp > ed){ break; }
		dnc(p+1, pp-1);
		p = pp; cnt += 1;
	}
	dnc(p+1, ed);
	ans = ans*ctl[cnt] % mod;
}

void Main(){
	ctl[0] = 1;
	for (int i = 0; i < M; i++){ ctl[i+1] = ctl[i]*2 % mod * (2*i+1) % mod * finv(i+2) % mod; }
	//for (int i = 0; i <= 10; i++){
	//	cout << "CATALAN " << i << ' ' << ctl[i] << endl;
	//}
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	for (int i = N+N-1; i >= 1; i--){
		if (i >= N){ int idx = i-N+1;
			if (i >= N+n){ seg[i] = {N, idx}; }
			else{ seg[i] = {arr[idx], idx}; }
		}
		else{
			seg[i] = min(seg[i<<1], seg[i<<1|1]);
		}
	}
	for (int i = n; i >= 1; i--){
		int x = arr[i]; ptr[i] = (val[x] ? val[x] : n+1);
		val[x] = i;
	}
	dnc(1, n); cout << ans;
}

C. [16532] Looking for the Risk Factor (Platinum III)

의도한 태그: Merge Sort Tree

"모든 소인수에 대해" 같은 건 처리하기 귀찮으니까, 대신 "가장 큰 소인수에 대해"로 문제를 바꿔봅시다.

이렇게 바꿔도 문제에서 묻는 게 달라지지 않음은 자명합니다.

 

그럼 남은 건 \( [2, N] \) 구간에서, 최대 소인수가 \( K \) 이하인 수의 개수를 구하는 문제가 됩니다.

그러니 \( 2 \)부터 \( N \)까지 최대 소인수를 에라토스테네스의 체 등으로 미리 구해둔 뒤, 이를 Merge Sort Tree에 저장해둔다면 남은 건 Merge Sort Tree 연습 문제 풀듯이 이진 탐색을 돌려주면 풀 수 있습니다.

const int N = 131072;
int prm[131080];
vector<int> seg[262150];

int qry(int st, int ed, int k){ st += N-1; ed += N-1;
	int res = 0;
	while (st <= ed){
		if (st & 1){
			res += upper_bound(all(seg[st]), k) - seg[st].begin();
			//cout << "RESS " << res << endl << flush;
			st += 1;
		}
		if (~ed & 1){
			res += upper_bound(all(seg[ed]), k) - seg[ed].begin();
			//cout << "RESE " << res << endl << flush;
			ed -= 1;
		}
		if (st > ed){ break; }
		st >>= 1; ed >>= 1;
	}
	return res;
}
inline int qry(int n, int k){ return qry(1, n, k); }

void Main(){
	for (int i = 2; i <= N; i++){
		if (prm[i] != 0){ continue; }
		for (int j = i; j <= N; j+=i){ prm[j] = i; }
	}
	for (int i = 2; i <= N; i++){
		seg[N-1+i].push_back(prm[i]);
	}
	for (int i = N-1; i >= 1; i--){
		seg[i].resize(seg[i<<1].size() + seg[i<<1|1].size());
		merge(all(seg[i<<1]), all(seg[i<<1|1]), seg[i].begin());
	}
	int q; cin >> q; while (q--){
		int n, k; cin >> n >> k;
		cout << qry(n, k) << endl; //cout << flush;
	}
}

D. [1280] 나무 심기 (Platinum IV)

의도한 태그: Segment Tree (+ Linear Equation)

어떤 지점에 업데이트를 할 때, 다른 위치에 더해지는 값은 \( \ldots 3, 2, 1, 0, 1, 2, 3, \ldots \) 형태가 됩니다.

뭔가 \( | x-a | \) 형태로 표현되는 식이니까, 세그먼트 트리에 \( ax + b \) 형태의 식을 저장해주면 됩니다.

 

우선 쿼리부터 날려서 답 (이번에 나무를 심는 비용)을 구해봅시다. 이는 \( i \)번째 자식 노드가 가지고 있는 \( ax + b \)에 \( x = i \)를 대입해주면 됩니다.

업데이트 (나무 심기)는 이번에 나무를 심는 지점을 기준으로, 왼쪽에는 \( -x + a \)를, 오른쪽에는 \( x - a \)를 더해주면 됩니다.

const ll mod = 1e9 + 7;

const int N = 262144;
pl2 seg[524290];

void upd(int idx){ int pos = idx+N;
	seg[pos].fr += 1; seg[pos].sc += idx; pos >>= 1;
	while (pos){
		seg[pos].fr = seg[pos<<1].fr + seg[pos<<1|1].fr; seg[pos].fr %= mod;
		seg[pos].sc = seg[pos<<1].sc + seg[pos<<1|1].sc; seg[pos].sc %= mod;
		pos >>= 1;
	}
}
pl2 qry(int st, int ed){ st += N; ed += N;
	pl2 res = {0, 0};
	while (st <= ed){
		if (st & 1){
			res.fr += seg[st].fr; res.fr %= mod;
			res.sc += seg[st].sc; res.sc %= mod;
			st += 1;
		}
		if (~ed & 1){
			res.fr += seg[ed].fr; res.fr %= mod;
			res.sc += seg[ed].sc; res.sc %= mod;
			ed -= 1;
		}
		if (st > ed){ break; }
		st >>= 1; ed >>= 1;
	}
	return res;
}

void Main(){
	int n; cin >> n;
	ll ans = 1;
	for (int i = 1; i <= n; i++){
		int p; cin >> p;
		if (i > 1){
			pl2 p1 = qry(0, p-1), p2 = qry(p+1, N);
			ll res = (p*p1.fr - p1.sc) % mod - (p*p2.fr - p2.sc) % mod;
			res = (res+mod) % mod;
			ans *= res; ans %= mod;
		}
		upd(p);
	}
	cout << ans;
}

E. [2192] 두 수열 (Platinum III)

의도한 태그: Without Segment Tree

(수들의 합) - (수의 개수), 즉 \( \sum_{i=st}^{ed} A_{i} - (ed-st+1) \)는 \( \sum_{i=st}^_{ed} (A_{i}-1) \)로 나타낼 수 있습니다.

그러니 두 수열을 입력받으면서 각 수에서 1을 빼서 저장하면, 그냥 두 수열의 곱으로 표현할 수 있습니다.

 

이제, 최적해가 가지는 형태를 생각해봅시다.

결론부터 말하자면, 최적해는 두 수열에서 동시에 2개 이상의 수를 뽑는 경우가 없습니다.

만약 그런 경우가 있었다고 한다면, 두 수열을 각각 \( sa_{1}, sa_{2}, sb_{1}, sb_{2} \)라는 합으로 나눠보면

원래 해는 \( (sa_{1} + sa_{2})(sb_{1} + sb_{2}) \)지만, 위와 같은 방식으로 나눠서 합을 구해보면

\( sa_{1} sb_{1} + sa_{2} sb_{2} \)가 됩니다.

전개를 해보면 아래 식의 값이 위 식의 값보다 작거나 같음을 자명히 볼 수 있습니다.

 

이제, 두 수열의 첫 \( i, j \)개의 수만을 가지고 만들 수 있는 최소 점수를 DP로 구해봅시다.

점화식은 아래 3가지 경우로 나눠볼 수 있습니다.

• 새로운 수열의 시작: \( DP_{i-1, j-1} + A_{i} B_{j} \)
• 수열 A에서 하나 더 넣기: \( DP_{i-1, j} + A_{i} B_{j} \)
• 수열 B에서 하나 더 넣기: \( DP_{i, j-1} + A_{i} B_{j} \)

최종 답은 \( DP_{N, M} \)이 됩니다.

ll arr[2020], brr[2020];
ll dp[2020][2020];

void Main(){
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; arr[i] -= 1; }
	for (int i = 1; i <= m; i++){ cin >> brr[i]; brr[i] -= 1; }
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			if (i==1 && j==1){ dp[i][j] = arr[i]*brr[j]; }
			else if (i==1){ dp[i][j] = dp[i][j-1] + arr[i]*brr[j]; }
			else if (j==1){ dp[i][j] = dp[i-1][j] + arr[i]*brr[j]; }
			else{ dp[i][j] = min({ dp[i-1][j], dp[i][j-1], dp[i-1][j-1] }) + arr[i]*brr[j]; }
		}
	}
	cout << dp[n][m];
}

F. [9345] 디지털 비디오 디스트(DVDs) (Platinum III)

의도한 태그: Minimum/Maximum Segment Tree

\( [L, R] \) 구간에 DVD가 \( L \)부터 \( R \)까지 있는지 확인하려면,

\( [L, R] \) 구간에 쿼리를 날려서 최솟값이 \( L \)이고 최댓값이 \( R \)인지 확인하면 됩니다.

swap은 그냥 어떤 위치의 수를 변경하는 쿼리를 2번 날려주면 됩니다.

const int N = 131072;
const ll INF = 1e9; pl2 seg[262150];
void upd(int pos, int val){ pos += N-1;
	seg[pos] = {val, val}; pos >>= 1;
	while (pos){
		seg[pos].fr = min(seg[pos<<1].fr, seg[pos<<1|1].fr);
		seg[pos].sc = max(seg[pos<<1].sc, seg[pos<<1|1].sc);
		pos >>= 1;
	}
}
pl2 qry(int st, int ed){ st += N-1; ed += N-1;
	pl2 res = {INF, -INF};
	while (st <= ed){
		if (st & 1){
			res.fr = min(res.fr, seg[st].fr);
			res.sc = max(res.sc, seg[st].sc);
			st += 1;
		}
		if (~ed & 1){
			res.fr = min(res.fr, seg[ed].fr);
			res.sc = max(res.sc, seg[ed].sc);
			ed -= 1;
		}
		if (st > ed){ break; }
		st >>= 1; ed >>= 1;
	}
	return res;
}

void Main(){
	int t; cin >> t;
	while (t--){
		int n, q; cin >> n >> q;
		for (int i = 1; i <= n; i++){ seg[N-1+i] = {i, i}; }
		for (int i = N-1; i >= 1; i--){
			seg[i].fr = min(seg[i<<1].fr, seg[i<<1|1].fr);
			seg[i].sc = max(seg[i<<1].sc, seg[i<<1|1].sc);
		}
		while (q--){
			int typ; cin >> typ;
			if (typ == 0){
				int i1, i2; cin >> i1 >> i2; i1++; i2++;
				int v1 = seg[N-1+i1].fr, v2 = seg[N-1+i2].sc;
				upd(i1, v2); upd(i2, v1);
			}
			if (typ == 1){
				int st, ed; cin >> st >> ed; st++; ed++;
				pl2 p = qry(st, ed);
				cout << (p.fr==st && p.sc==ed ? "YES" : "NO") << endl;
			}
		}
	}
}

G. [23024] 보트 정박 (Platinum IV)

의도한 태그: Kth Segment Tree (세그먼트 트리의 루트에서부터 이진 탐색하기)

세그먼트 트리의 각 정점에, 부두의 길이를 저장해봅시다. (배가 정박했으면 0)

그리고, 각 구간에는 정박할 수 있는 가장 긴 부두의 길이 (즉 max)를 저장해봅시다.

 

그럼 어떤 구간에서 보트가 정박할 수 있다는 건, 그 구간에 보트보다 더 긴 부두가 존재한다는 것이니

max(부두의 길이) ≥ 보트의 길이 라면 그 구간 내에 정박이 가능한 부두가 존재한다는 의미가 됩니다.

 

이러면, 루트에서부터 출발해서

\( [L, R] \) 구간에 정박이 가능하다고 하면, \( [L, M] \) 구간에 정박이 가능한지 판별한 뒤

\( [L, M] \) 구간에 정박할 수 있으면 그 쪽으로, 그렇지 않다면 \( (M, R] \) 구간으로 탐색을 이어나가면 됩니다.

 

주의할 점은, \( [1, N] \) 구간에서 정박이 불가능하다면 위와 같은 탐색을 하지 말고 그냥 넘겨야 합니다.

const int N = 262144; ll seg[524290];
int res[200020];

void upd(int pos){ pos += N-1;
	seg[pos] = 0; pos >>= 1;
	while (pos){ seg[pos] = max(seg[pos<<1], seg[pos<<1|1]); pos >>= 1; }
}
int qry(ll x){ int ni = 1;
	while (ni < N){
		if (seg[ni<<1] >= x){ ni = ni<<1; }
		else{ ni = ni<<1 | 1; }
	}
	return ni-N+1;
}

void Main(){
	int t; cin >> t; while (t--){
		int n, q; cin >> n >> q;
		for (int i = 1; i <= n; i++){ cin >> seg[N-1+i]; res[i] = 0; }
		for (int i = n+1; i <= N; i++){ seg[N-1+i] = 0; }
		for (int i = N-1; i >= 1; i--){ seg[i] = max(seg[i<<1], seg[i<<1|1]); }
		for (int qi = 1; qi <= q; qi++){
			ll x; cin >> x; if (x > seg[1]){ continue; }
			int idx = qry(x); res[idx] = qi; upd(idx);
			//cout << "RES " << idx << ' ' << qi << endl;
		}
		ll ans = 0;
		for (int i = 1; i <= n; i++){ ans += (ll)res[i]*i; }
		cout << ans << endl;
	}
}

H. [2995] 생일 (Platinum IV)

의도한 태그: Segment Tree + DP (수열 정의하기)

구간을 \( st \)를 기준으로, \( st \)가 동일하다면 \( ed \) 역순을 기준으로 정렬해봅시다.

이렇게 정렬하면, 어떤 구간을 포함하는 구간들은 항상 그 구간보다 앞에 오게 됩니다.

 

그럼 각 구간에 대해서, 아래와 같은 DP를 생각해볼 수 있습니다.

\( DP_{i} = i \)번째 구간을 끝으로 하는 가장 긴 수열

그럼 DP 점화식은, \( i \)번 구간을 포함하는 \( j \)번 구간들에 대해 \( \max DP{j} + 1 \)이 됩니다.

 

\( st \)를 기준으로 정렬했기 때문에, 나보다 앞에 있는 구간이 나를 포함하려면

\( ed \)가 나보다 늦게 나오는 경우밖에 나오지 않습니다.

그래서, 세그먼트 트리의 \( ed \)번째 정점에 어떤 값을 넣어둔다면,

\( ed \le e \)인 \( e \)에 대해 쿼리를 날리면 나를 포함하는 구간에 대한 쿼리를 처리할 수 있게 됩니다.

 

이 경우는 \( j \)번째 구간이 \( [s, e] \)일 때, 세그먼트 트리의 \( e \)번 정점에 \( DP_{j} \)를 넣어주면 됩니다.

이러고 max 쿼리를 날리면, \( \max DP{j} \)의 값을 구하게 됩니다.

실제 DP는 거기에 1만 더해주면 됐으니, 그대로 해주면 됩니다.

 

구간을 하나씩 스위핑하면서 보는 것이니, 쿼리를 날리고 업데이트도 해줘야 합니다!

pi2 arr[100020]; int pre[100020];

const int N = 1048576; pi2 seg[2097160];
void upd(int pos, pi2 val){ pos += N-1;
	seg[pos] = max(seg[pos], val); pos >>= 1;
	while (pos){
		seg[pos] = max(seg[pos<<1], seg[pos<<1|1]); pos >>= 1;
	}
}
pi2 qry(int st, int ed){ st += N-1; ed += N-1;
	pi2 res = {0, 0};
	while (st <= ed){
		if (st & 1){ res = max(res, seg[st]); st += 1; }
		if (~ed & 1){ res = max(res, seg[ed]); ed -= 1; }
		if (st > ed){ break; }
		st >>= 1; ed >>= 1;
	}
	return res;
}

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i].fr >> arr[i].sc; }
	sort(arr+1, arr+n+1, [](pi2 a, pi2 b){
		if (a.fr != b.fr){ return a.fr < b.fr; }
		return a.sc > b.sc;
	});
	int ans = 0, ptr = 0;
	for (int i = 1; i <= n; i++){
		int val = arr[i].sc;
		pi2 p = qry(val, N);
		int res = p.fr + 1, idx = p.sc;
		if (ans < res){ ans = res; ptr = i; } pre[i] = idx;
		upd(val, {res, i});
	}
	cout << ans << endl;
	stack<pi2> stk;
	while (ans--){ stk.push(arr[ptr]); ptr = pre[ptr]; }
	while (!stk.empty()){
		pi2 p = stk.top(); stk.pop();
		cout << p.fr << ' ' << p.sc << endl;
	}
}

I. [13925] 수열과 쿼리 13 (Platinum I)

의도한 태그: Segment Tree with Lazy Propagation

세그먼트 트리의 각 정점의 Lazy에 \( ax + b \)를 저장해봅시다. 이번에는 저번 문제와 다르게 \( x = A_{i} \)입니다.

세그먼트 트리의 각 정점 자체에는 \( ax + b \)가 아니라 그냥 \( A_{i} \)를 저장해야 함에 주의하세요!

 

그럼 각 쿼리를 아래와 같이 나타낼 수 있습니다.

• 1번 쿼리 (덧셈): \( ax + b + k \rightarrow (a, b+k) \)
• 2번 쿼리 (곱셈): \( k(ax + b) = akx + bk \rightarrow (ak, bk) \)
• 3번 쿼리 (설정): \( k = 0x + k \rightarrow (0, k) \)

위와 같은 방식으로 Lazy Propagation을 해주면서 \( A_{[l, r]} \)의 합을 업데이트해주면 됩니다.

Range Sum Query는 하던대로 진행해주면 됩니다.

const ll mod = 1e9 + 7;
const int N = 131072; pl3 seg[262150];

void pro(int ni, int ns, int ne){ int cnt = ne-ns+1;
	seg[ni].fr = (seg[ni].fr*seg[ni].sc.fr % mod + seg[ni].sc.sc*cnt%mod) % mod;
	if (ns != ne){
		ll a1 = seg[ni].sc.fr, b1 = seg[ni].sc.sc;
		ll a2 = seg[ni<<1].sc.fr, b2 = seg[ni<<1].sc.sc;
		seg[ni<<1].sc = { a1*a2 % mod, (a1*b2%mod + b1) % mod };
		a2 = seg[ni<<1|1].sc.fr; b2 = seg[ni<<1|1].sc.sc;
		seg[ni<<1|1].sc = { a1*a2 % mod, (a1*b2%mod + b1) % mod };
	}
	seg[ni].sc = {1, 0};
}
void upd(int ni, int ns, int ne, int st, int ed, pl2 val){
	pro(ni, ns, ne);
	if (ed < ns || ne < st){ return; }
	if (st <= ns && ne <= ed){ seg[ni].sc = val; return pro(ni, ns, ne); }
	int nm = ns+ne >> 1;
	upd(ni<<1, ns, nm, st, ed, val); upd(ni<<1|1, nm+1, ne, st, ed, val);
	seg[ni].fr = (seg[ni<<1].fr + seg[ni<<1|1].fr) % mod;
}
void upd(int st, int ed, pl2 val){ return upd(1, 1, N, st, ed, val); }
ll qry(int ni, int ns, int ne, int st, int ed){
	pro(ni, ns, ne);
	if (ed < ns || ne < st){ return 0; }
	if (st <= ns && ne <= ed){ return seg[ni].fr; }
	int nm = ns+ne >> 1;
	return ( qry(ni<<1, ns, nm, st, ed) + qry(ni<<1|1, nm+1, ne, st, ed) ) % mod;
}
ll qry(int st, int ed){ return qry(1, 1, N, st, ed); }

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> seg[i+N-1].fr; }
	for (int i = N+N-1; i >= 1; i--){
		if (i < N){ seg[i].fr = (seg[i<<1].fr + seg[i<<1|1].fr) % mod; }
		seg[i].sc = {1, 0};
	}
	int q; cin >> q;
	while (q--){
		int m; cin >> m;
		if (m == 1){
			int st, ed, x; cin >> st >> ed >> x;
			upd(st, ed, {1, x});
		}
		if (m == 2){
			int st, ed, x; cin >> st >> ed >> x;
			upd(st, ed, {x, 0});
		}
		if (m == 3){
			int st, ed, x; cin >> st >> ed >> x;
			upd(st, ed, {0, x});
		}
		if (m == 4){
			int st, ed; cin >> st >> ed;
			cout << qry(st, ed) << endl;
		}
	}
}

J. [16978] 수열과 쿼리 22 (Platinum IV)

의도한 태그: Segment Tree

\( k \)번째 1번 쿼리까지 적용되었을 때는 굉장히 이상한 조건입니다.

하지만, 어차피 2번 쿼리끼리는 어떻게 순서를 바꿔도 (출력 순서를 제외하면) 영향을 끼치지 않으니 2번 쿼리의 순서를 마음대로 바꿔줄 수 있습니다.

그러니, 모든 2번 쿼리를 \( k \)번째 1번 쿼리가 적용된 직후 시점으로 이동시켜주면 됩니다.

const int N = 131072;
ll seg[262150];
void upd(int pos, int val){ pos += N-1;
	seg[pos] = val; pos >>= 1;
	while (pos){
		seg[pos] = seg[pos<<1] + seg[pos<<1|1]; pos >>= 1;
	}
}
ll qry(int st, int ed){ st += N-1; ed += N-1;
	ll res = 0;
	while (st <= ed){
		if (st & 1){ res += seg[st]; st += 1; }
		if (~ed & 1){ res += seg[ed]; ed -= 1; }
		if (st > ed){ break; } st >>= 1; ed >>= 1;
	}
	return res;
}

vector<pi3> qrv[100020]; pi2 upv[100020];
ll ans[100020];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> seg[N-1+i]; }
	for (int i = N-1; i >= 0; i--){ seg[i] = seg[i<<1] + seg[i<<1|1]; }
	int q1 = 0, q2 = 0;
	int q; cin >> q; for (int i = 1; i <= q; i++){
		int typ; cin >> typ;
		if (typ == 1){
			int pos, val; cin >> pos >> val;
			upv[++q1] = {pos, val};
		}
		if (typ == 2){
			int k, st, ed; cin >> k >> st >> ed;
			qrv[k].push_back({ {st, ed}, ++q2 });
		}
	}
	for (int i = 0; i <= q1; i++){
		if (i){ int pos = upv[i].fr, val = upv[i].sc; upd(pos, val); }
		for (pi3 p : qrv[i]){
			int st = p.fr.fr, ed = p.fr.sc; int qi = p.sc;
			ans[qi] = qry(st, ed);
		}
	}
	for (int i = 1; i <= q2; i++){ cout << ans[i] << endl; }
}

K. [17408] 수열과 쿼리 24 (Platinum IV)

의도한 태그: Segment Tree

각 세그먼트 트리의 정점에 (최댓값, 2번째 최댓값)을 저장하면 됩니다.

쿼리의 답은 자명하게 (최댓값 + 2번째 최댓값)이 될 테니까요.

pi2 mrg(pi2 p1, pi2 p2){
	pi2 res = {0, 0};
	int v1 = p1.fr, v2 = p2.fr;
	if (v1 > v2){ res.fr = v1; v1 = p1.sc; } else{ res.fr = v2; v2 = p2.sc; }
	res.sc = max(v1, v2);
	return res;
}

const int N = 131072;
pi2 seg[262150];
void upd(int pos, int val){ pos += N-1;
	seg[pos] = {val, 0}; pos >>= 1;
	while (pos){
		seg[pos] = mrg(seg[pos<<1], seg[pos<<1|1]); pos >>= 1;
	}
}
pi2 qry(int st, int ed){ st += N-1; ed += N-1;
	pi2 res = {0, 0};
	while (st <= ed){
		if (st & 1){ res = mrg(res, seg[st]); st += 1; }
		if (~ed & 1){ res = mrg(res, seg[ed]); ed -= 1; }
		if (st > ed){ break; } st >>= 1; ed >>= 1;
	}
	return res;
}

vector<pi3> qrv[100020]; pi2 upv[100020];
ll ans[100020];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> seg[N-1+i].fr; }
	for (int i = N-1; i >= 0; i--){ seg[i] = mrg(seg[i<<1], seg[i<<1|1]); }
	int q; cin >> q; while (q--){
		int typ; cin >> typ;
		if (typ == 1){
			int pos, val; cin >> pos >> val;
			upd(pos, val);
		}
		if (typ == 2){
			int st, ed; cin >> st >> ed;
			pi2 res = qry(st, ed); cout << res.fr+res.sc << endl;
		}
	}
}

L. [18865] 이제 다시 시작이다 (Platinum I)

의도한 태그: Segment Tree (다양한 값 저장해보기)

훈련소의 우측 상단 점을 (0, 0)으로 고정시켜봅시다.

그리고, 각각의 스피커를 (원점과의 거리가 달라지지 않는) x축 위의 한 점으로 옮겨봅시다.

이렇게 해도 되는 이유가, 원래 스피커가 훈련소보다 우측 상단에 있기 때문입니다.

 

이제, 우리는 성공적으로 스피커를 1차원 위의 점으로 표현시킬 수 있습니다.

그러니, \( C_{x} = x \) 위치에 있는 스피커의 개수 를 정의해봅시다.

 

그럼, 현재까지 설치된 스피커에 대해 아래 쿼리를 처리할 수 있으면 됩니다.

\( Q(k) = \sum_{x} (\max(k-x, 0))^{2} C_{x} \)

이 쿼리를 처리할 수 있다면, 실제 문제의 답은 훈련소의 높이/너비가 \( h, w \)일 때

포함-배제 하듯이 \( Q(V) - Q(V-h) - Q(V-w) + Q(V-h-w) \)를 계산해주면 됩니다.

 

그럼 저 쿼리는 어떻게 처리할까요?

이를 위해, 3가지 값을 들고 있으면 됩니다.

• SUM: \( \sum_{i=1}^{N} A_{i} \)
• TRI: \( \sum_{i=1}^{N} i \times A_{i} \)
• SQP: \( \sum_{i=1}^{N} \frac{i(i+1)}{2} \times A_{i} \)

이를 통해 실제 쿼리의 값을 계산하는 방식이나 이를 구간에 맞게 합치는 방식은 https://hibye1217-aloha.tistory.com/13?category=1071691 (ALOHA 고급반 4주차의 9번 문제)를 참고해주세요. 다시 적기에는 분량이 너무 많아서 글을 넘기겠습니다.

struct Node{ ll sum, tri, sqp; int st, ed; };
const int N = 524288; Node seg[1048580];

inline Node add(const Node& a, const Node& b){
	//cout << "ADD " << a.st << ' ' << a.ed << ' ' << b.st << ' ' << b.ed << endl << flush;
	if (a.st > b.st){ return add(b, a); }
	assert(a.ed+1 == b.st);
	int al = a.ed-a.st+1, bl = b.ed-b.st+1;
	Node res = {0, 0, 0, a.st, b.ed};
	res.sum = a.sum + b.sum;
	res.tri = a.tri + b.tri + bl*a.sum;
	res.sqp = a.sqp + b.sqp + bl*a.tri + bl*(bl+1LL)/2*a.sum;
	return res;
}

void upd(int pos, int val){ pos += N;
	seg[pos].sum += 1; seg[pos].tri += 1; seg[pos].sqp += 1;
	pos >>= 1;
	while (pos){
		int p1 = pos<<1, p2 = pos<<1|1;
		seg[pos] = add(seg[p1], seg[p2]); pos >>= 1;
	}
}
Node qry(int st, int ed){ st += N; ed += N;
	Node res = {0, 0, 0, -1, -1};
	while (st <= ed){
		if (st & 1){
			if (res.st == -1){ res = seg[st]; }
			else{ res = add(res, seg[st]); }
			st += 1;
		}
		if (~ed & 1){
			if (res.st == -1){ res = seg[ed]; }
			else{ res = add(res, seg[ed]); }
			ed -= 1;
		}
		if (st > ed){ break; }
		st >>= 1; ed >>= 1;
	}
	return res;
}
inline ll f(int x){
	if (x < 0){ return 0; }
	Node res = qry(0, x-1);
	return 2*res.sqp - res.tri;
}

void Main(){
	for (int i = N+N-1; i >= 1; i--){
		if (i >= N){ seg[i].st = seg[i].ed = i-N; }
		else{ seg[i].st = seg[i<<1].st; seg[i].ed = seg[i<<1|1].ed; }
	}
	int sy, sx, ey, ex; cin >> sy >> sx >> ey >> ex;
	int h = ey-sy, w = ex-sx;
	int q; cin >> q;
	while (q--){
		int m; cin >> m;
		if (m == 1){
			int y, x; cin >> y >> x; y -= ey; x -= ex;
			x += y; upd(x, 1);
		}
		if (m == 2){
			int x; cin >> x;
			cout << f(x) - f(x-h) - f(x-w) + f(x-h-w) << endl;
		}
	}
}

M. [15554] 전시회 (Platinum V)

의도한 태그: Without Segment Tree

미술품을 크기 순으로 정렬해봅시다. 그럼 가장 작은 미술품 \( A_{l} \)과 가장 큰 미술품 \( A_{r} \)에 대해서,

그 사이에 있는 미술품들을 전부 선택하는 것이 최적입니다.

그러니, \( l, r \)을 돌려가면서 가치의 누적 합과 \( A_{r} - A_{l} \)을 계산해주면 \( O(N^2) \)에 문제를 풀 수 있습니다.

 

하지만 이 문제는 \( O(N^2) \)이 TLE를 내버리니, 이보다는 더 빠르게 풀어야 합니다.

이를 위해, 잠시 식을 정리해봅시다.

가치의 prefix sum을 저장하고 있는 \( P_{i} = \sum_{j=1}^{i} B_{j} \)에 대해, \( l, r \)이 고정되었을 때의 답은 다음와 같이 표현할 수 있습니다. \( (P_{r} - P_{l-1}) - (A_{r} - A_{l}) \)

 

그런데, 여기서 \( l, r \)을 기준으로 항을 옮겨봅시다. \( (P_{r} - A_{r}) - (P_{l-1} - A_{l}) \)

그 뒤로 우리가 위 식에서 \( l \)만 고정시켰을 때 만들 수 있는 답의 최대를 생각해볼 수 있습니다.

이는 \( P_{r} - A_{r} \)을 최대화하는 방법밖에 없으니, 각 \( r \)별로 이 값의 suffix max를 저장해주면 답을 빠르게 구할 수 있습니다.

pl2 arr[500020]; ll prf[500020], suf[500020];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i].fr >> arr[i].sc; } sort(arr+1, arr+n+1);
	for (int i = 1; i <= n; i++){ prf[i] = prf[i-1] + arr[i].sc; }
	suf[n] = prf[i] - arr[i].fr;
	for (int i = n-1; i >= 1; i--){ suf[i] = max(suf[i+1], prf[i] - arr[i].fr); }
	ll ans = 0;
	for (int l = 1; l <= n; l++){
		ll res = suf[l] - (prf[l-1] - arr[l].fr);
		ans = max(ans, res);
	}
	cout << ans;
}