2022.07.21. (Segment Tree의 다양한 응용) 풀이

다룬 태그들

• 세그먼트 트리의 수열 직접 정의해보기 (ABCD)
• 2-Dimensional Segment Tree (EF)
• Kth Segment Tree (GH)
• Merge Sort Tree (IJ)
• Continuous Sum Segment Tree (KL)

A. [10090] Counting Inversions (Platinum V)

Inversion을 좀 더 명확히 정의하면, \( i < j \)이면서 \( A_{i} > A_{j} \)인 \( (i, j) \) 쌍을 의미합니다.

그럼 우리가 \( j \)를 기준으로 돌리면서 앞에 나온 값들 중 \( A_{j} \)보다 더 큰 값의 개수를 찾아주면 됩니다.

 

그래서 \( B_{x} := \) \( A_{j} = x \)인 \( j < i \)의 개수 (0 or 1)를 정의하면,

\( A_{i} \)보다 더 큰 값의 개수 = \( \sum_{x=A_{i}+1}^{\infty} B_{x} \)가 됩니다.

즉, Range Sum Query로 잘 해결할 수 있는 문제가 됩니다.

 

추가적으로, 위 쿼리를 수행한 뒤에는 지금 보고 있던 \( A_{j} \)가 \( A_{i} \)로 들어가야 하니

\( B_{A_{i}} \)에 1을 더해줘야 합니다.

즉, Point Add Update까지 들어가게 됩니다.

 

이제는 세그먼트 트리로 잘 풀리는 문제가 되었으니, 그대로 풀어주면 됩니다.

const int N = 1048576;
int seg[2097160];

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;
	}
}
int 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;
}

void Main(){
	int n; cin >> n;
	ll ans = 0;
	for (int i = 1; i <= n; i++){
		int x; cin >> x;
		ans += qry(x+1, N);
		upd(x, 1);
	}
	cout << ans;
}

B. [2517] 달리기 (Platinum IV)

위 문제와 비슷하면서 다르게 풀어주면 됩니다.

우선, 어차피 값의 대소 비교만 필요하니, 좌표 압축을 통해 1~N으로 강제해줍시다.

 

그 뒤, \( B_{x} := \) \( A_{j} = x \)인 \( j < i \)의 개수 (0 or 1)를 정의하면,

\( A_{i} \)보다 더 작은 값의 개수 = \( \sum_{x=1}^{A_{i}-1} B_{x} \)가 됩니다.

(최선의 등수) = (현재 등수) - (\( A_{i} \)보다 더 작은 실력을 가진 사람 수)니, 이도 간단히 계산할 수 있습니다.

 

풀이를 읽으면 알겠지만, 탐색하는 구간이 바뀐 거 빼고는, A번과 사실상 똑같게 풀어주면 됩니다.

const int N = 524288;
int seg[1048580];
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;
	}
}
int 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;
}

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

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; cs.insert(arr[i]); }
	for (int x : cs){ cvt[x] = ++cc; }
	for (int i = 1; i <= n; i++){ arr[i] = cvt[ arr[i] ]; }
	for (int i = 1; i <= n; i++){
		int x = arr[i];
		cout << i - qry(1, x-1) << endl;
		upd(x, 1);
	}
}

C. [2336] 굉장한 학생 (Platinum II)

각 학생별로, 굉장한 학생이 될 수 있는지 판별해봅시다.

 

이를 위해, 우선 시험 A를 기준으로 학생들을 정렬시켜봅시다.

그 뒤, 시험 A의 1위부터 차례대로 보면, 나중에 보는 학생들은 항상 먼저 보는 학생보다 시험 A를 못 본 학생들이 됩니다.

 

시험 B는, 세그먼트 트리의 \( i \)번째 정점에 B번 시험 \( i \)위를 한 사람이 이미 나온 적이 있는지를 저장하면 됩니다.

이러면 현재 보고 있는 학생의 B번 시험 순위 \( B_{i} \)에 대해, \( [1, B_{i}) \)번 구간 어딘가에 그런 사람이 있다는 결론이 나온다면?

그 학생은 위 조건에 의해 그 학생에 비해 시험 A를 못 본 학생이자, 시험 B를 못 본 학생이 됩니다.

 

마지막으로, 시험 C를 처리해봅시다.

이를 위해, 세그먼트 트리의 \( i \)번째 정점에 B번 시험 \( i \)위를 한 사람의 C번 시험 순위를 저장하면 됩니다.

(아직 본 적 없는 학생의 순위는 \( \infty \)로 잡아주면 됩니다.)

 

그럼, \( [1, B_{i}) \) 구간에 있던 학생들은 아까 봤듯이 시험 A와 시험 B를 \( i \)번 학생보다 잘 친 학생들이고,

이 중 C번 시험을 잘 친 학생이 있는지는 Range Minimum Query로 C번 시험 최고성적을 골라오면 됩니다.

만약 그 학생이 C번 시험도 \( i \)번 학생보다 잘 쳤다면, 굉장한 학생이 될 수 없게 됩니다.

const int N = 524288, INF = 1e9; int seg[1048580];
void upd(int pos, int val){ pos += N-1;
	seg[pos] = val; pos >>= 1;
	while (pos){
		seg[pos] = min(seg[pos<<1], seg[pos<<1|1]); pos >>= 1;
	}
}
int qry(int st, int ed){ st += N-1; ed += N-1;
	int res = INF;
	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;
}

pi3 arr[500020];
void Main(){
	for (int i = 1; i < N+N; i++){ seg[i] = INF; }
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ int x; cin >> x; arr[x].fr = i; }
	for (int i = 1; i <= n; i++){ int x; cin >> x; arr[x].sc.fr = i; }
	for (int i = 1; i <= n; i++){ int x; cin >> x; arr[x].sc.sc = i; }
	sort(arr+1, arr+n+1);
	int ans = 0;
	for (int i = 1; i <= n; i++){
		int r1 = arr[i].fr, r2 = arr[i].sc.fr, r3 = arr[i].sc.sc;
		int mnr = qry(1, r2);
		if (mnr > r3){ ans += 1; }
		upd(r2, r3);
	}
	cout << ans;
}

D. [2472] 체인점 (Platinum I)

각 정점에서 세 아파트 단지까지의 거리를 배열 A, B, C로 나타내면,

문제는 각 \( i \)에 대해, \( A_{i} > A_{j}, B_{i} > B_{j}, C_{i} > C_{j} \)인 \( j \)가 존재하는지 판별하는 문제가 됩니다.

 

이거, 많이 익숙한 문제 아닌가요?

바로 위에서 풀이했던 '굉장한 학생' 문제와 동일합니다.

 

그래서, 다익스트라 등을 통해 배열 A, B, C를 만든 뒤,

이를 좌표 압축을 통해 1~N으로 만들어준 뒤,

'굉장한 학생' 풀듯이 풀면 됩니다.

vector<pl2> adj[100020];
ll dis[3][100020]; bool chk[3][100020];
pl4 arr[100020];
map<ll, ll> cvt; set<ll> cs; int cc = 0;
const int N = 131072;
ll seg[262150];
bool ans[100020];

void djk(int st, int idx){
	priority_queue< pl2, vector<pl2>, greater<pl2> > pq;
	pq.push({0, st}); dis[idx][st] = 0;
	while (!pq.empty()){
		ll dst = pq.top().fr; int now = pq.top().sc;
		pq.pop();
		if (chk[idx][now]){ continue; } chk[idx][now] = 1;
		for (pl2 p : adj[now]){
			int nxt = p.fr; ll d = p.sc;
			if (chk[idx][nxt]){ continue; }
			if (dis[idx][nxt] <= d+dst){ continue; }
			dis[idx][nxt] = d+dst;
			pq.push({d+dst, nxt});
		}
	}
}

void upd(int pos, ll val){ pos += N-1;
	seg[pos] = min(seg[pos], val); pos >>= 1;
	while (pos){
		seg[pos] = min(seg[pos<<1], seg[pos<<1|1]);
		pos >>= 1;
	}
}

ll qry(int st, int ed){ st += N-1; ed += N-1;
	ll res = 1e18;
	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;
}

void Main(){
	int n; cin >> n;
	int st1, st2, st3; cin >> st1 >> st2 >> st3;
	int m; cin >> m;
	while (m--){
		int a, b, c; cin >> a >> b >> c;
		adj[a].push_back({b, c});
		adj[b].push_back({a, c});
	}
	memset(dis, 0x3f, sizeof(dis));
	djk(st1, 0); djk(st2, 1); djk(st3, 2);
	for (int i = 1; i <= n; i++){
		arr[i] = { {i, dis[0][i]}, {dis[1][i], dis[2][i]} };
		cs.insert(dis[1][i]);
	}
	for (ll x : cs){ cc += 1;
		cvt[x] = cc;
	}
	sort(arr+1, arr+n+1, [](pl4 a, pl4 b){ return a.fr.sc < b.fr.sc; });
	queue<pl2> q;
	memset(seg, 0x3f, sizeof(seg));
	for (int i = 1; i <= n; i++){
		int idx = arr[i].fr.fr;
		ll a = arr[i].fr.sc, b = arr[i].sc.fr, c = arr[i].sc.sc;
		if (a != arr[i-1].fr.sc){
			while (!q.empty()){
				ll y = q.front().fr, z = q.front().sc;
				q.pop(); upd(cvt[y], z);
			}
		}
		ll res = qry(1, cvt[b]-1);
		if (res < c){ ans[idx] = 0; }
		else{ ans[idx] = 1; }
		q.push({b, c});
	}
	int t; cin >> t;
	while (t--){
		int a; cin >> a;
		cout << (ans[a] ? "YES" : "NO") << endl;
	}
}

E. [11658] 구간 합 구하기 3 (Platinum V)

2차원 세그먼트 트리에서

어떠한 점에 업데이트를 하고

특정한 구간에 쿼리를 날리는

전형적인 문제입니다.

const int N = 1024;
ll seg[2050][2050];

void upx(int ni, int nj, int ns, int ne, int qy, int qx, int qv){
	if (ne < qx || qx < ns){ return; }
	if (ns == ne){ seg[ni][nj] += qv; return; }
	int nm = ns+ne >> 1;
	upx(ni, nj<<1, ns, nm, qy, qx, qv); upx(ni, nj<<1|1, nm+1, ne, qy, qx, qv);
	seg[ni][nj] = seg[ni][nj<<1] + seg[ni][nj<<1|1];
}
inline void upx(int ni, int y, int x, int v){ return upx(ni, 1, 1, N, y, x, v); }
void upy(int ni, int ns, int ne, int qy, int qx, int qv){
	if (ne < qy || qy < ns){ return; }
	if (ns == ne){ return upx(ni, qy, qx, qv); }
	int nm = ns+ne >> 1;
	upy(ni<<1, ns, nm, qy, qx, qv); upy(ni<<1|1, nm+1, ne, qy, qx, qv);
	upx(ni, qy, qx, qv);
}
inline void upy(int y, int x, int v){ return upy(1, 1, N, y, x, v); }

int qrx(int ni, int nj, int ns, int ne, pi2 qs, pi2 qe){
	if (ne < qs.sc || qe.sc < ns){ return 0; }
	if (qs.sc <= ns && ne <= qe.sc){ return seg[ni][nj]; }
	int nm = ns+ne >> 1;
	return qrx(ni, nj<<1, ns, nm, qs, qe) + qrx(ni, nj<<1|1, nm+1, ne, qs, qe);
}
inline int qrx(int ni, pi2 st, pi2 ed){ return qrx(ni, 1, 1, N, st, ed); }
int qry(int ni, int ns, int ne, pi2 qs, pi2 qe){
	if (ne < qs.fr || qe.fr < ns){ return 0; }
	if (qs.fr <= ns && ne <= qe.fr){ return qrx(ni, qs, qe); }
	int nm = ns+ne >> 1;
	return qry(ni<<1, ns, nm, qs, qe) + qry(ni<<1|1, nm+1, ne, qs, qe);
}
inline int qry(pi2 st, pi2 ed){ return qry(1, 1, N, st, ed); }

void Main(){
	int n, q; cin >> n >> q;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){ cin >> seg[N-1+i][N-1+j]; }
	}
	for (int i = N+N-1; i >= 1; i--){
		for (int j = N+N-1; j >= 1; j--){
			if (i >= N && j >= N){ continue; }
			if (i < N){ seg[i][j] = seg[i<<1][j] + seg[i<<1|1][j]; }
			else{ seg[i][j] = seg[i][j<<1] + seg[i][j<<1|1]; }
		}
	}
	while (q--){
		int typ; cin >> typ;
		if (typ == 0){
			int x, y, v; cin >> y >> x >> v;
			v = v - seg[N-1+y][N-1+x]; upy(y, x, v);
		}
		if (typ == 1){
			int x1, y1, x2, y2; cin >> y1 >> x1 >> y2 >> x2;
			cout << qry({y1, x1}, {y2, x2}) << endl;
		}
	}
}

F. [18246] 색종이와 쿼리 (Platinum I)

2차원 레이지를 써야 할 것 같지만, 제가 배운 적이 없습니다.

그래서 레이지를 쓰지 않는 방법을 보여드리겠습니다.

 

우선, 입력받는 색종이들을 imos법을 통해 배열에 저장합니다.

이는 (y1, x1)에 +1을, (y1, x2+1)과 (y2+1, x1)에 -1을, (y2+1, x2+1)에 +1을 놓으면 됩니다.

그 뒤, x 방향으로 prefix sum을 다 계산해준 뒤,

그 결과에 y 방향으로 prefix sum을 다 계산해주면 됩니다.

 

이러면 2차원 배열을 \( O(N^2) \)만에 채울 수 있습니다.

남은 건 그 2차원 배열을 세그먼트 트리에 옮겨서 max 쿼리를 날리는 것만 해주면 됩니다.

const int N = 2048;
int seg[4100][4100];

int qrx(int ni, int nj, int ns, int ne, pi2 qs, pi2 qe){
	//cout << "QRX " << ni << ' ' << nj << ' ' << ns << ' ' << ne << endl << flush;
	if (ne < qs.sc || qe.sc < ns){ return 0; }
	if (qs.sc <= ns && ne <= qe.sc){ return seg[ni][nj]; }
	int nm = ns+ne >> 1;
	return max( qrx(ni, nj<<1, ns, nm, qs, qe), qrx(ni, nj<<1|1, nm+1, ne, qs, qe) );
}
inline int qrx(int ni, pi2 st, pi2 ed){ return qrx(ni, 1, 0, N-1, st, ed); }

int qry(int ni, int ns, int ne, pi2 qs, pi2 qe){
	//cout << "QRY " << ni << ' ' << ns << ' ' << ne << endl << flush;
	if (ne < qs.fr || qe.fr < ns){ return 0; }
	if (qs.fr <= ns && ne <= qe.fr){ return qrx(ni, qs, qe); }
	int nm = ns+ne >> 1;
	return max( qry(ni<<1, ns, nm, qs, qe), qry(ni<<1|1, nm+1, ne, qs, qe) );
}
inline int qry(pi2 st, pi2 ed){ return qry(1, 0, N-1, st, ed); }

int prf[2050][2050];

void Main(){
	int n, q; cin >> n >> q;
	for (int i = 1; i <= n; i++){
		int y1, x1, y2, x2; cin >> y1 >> x1 >> y2 >> x2;
		prf[y1][x1] += 1; prf[y1][x2] -= 1;
		prf[y2][x1] -= 1; prf[y2][x2] += 1;
	}
	for (int y = 0; y < N; y++){
		for (int x = 1; x < N; x++){ prf[y][x] += prf[y][x-1]; }
	}
	for (int x = 0; x < N; x++){
		for (int y = 1; y < N; y++){ prf[y][x] += prf[y-1][x]; }
	}
	for (int i = 0; i < N; i++){
		for (int j = 0; j < N; j++){
			seg[N+i][N+j] = prf[i][j];
		}
	}
	for (int i = N+N-1; i >= 1; i--){
		for (int j = (i < N ? N+N-1 : N-1); j >= 1; j--){
			if (j < N){ seg[i][j] = max(seg[i][j<<1], seg[i][j<<1|1]); }
			else{ seg[i][j] = max(seg[i<<1][j], seg[i<<1|1][j]); }
		}
	}
	while (q--){
		int y1, x1, y2, x2; cin >> y1 >> x1 >> y2 >> x2;
		cout << qry({y1, x1}, {y2-1, x2-1}) << endl;
	}
}

G. [1321] 군인 (Platinum IV)

쿼리부터 당당하게 K번째를 찾으라고 명령합니다.

그러니 Kth Segment Tree를 그대로 구현해주면 됩니다.

const int N = 524288;
ll seg[1048580];

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;
	}
}
int kth(ll k){ int ni = 1;
	while (ni < N){
		if (k <= seg[ni<<1]){ ni = ni<<1; }
		else{ k -= seg[ni<<1]; ni = ni<<1|1; }
	}
	return ni-N+1;
}

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> seg[N-1+i]; }
	for (int i = N-1; i >= 1; i--){ seg[i] = seg[i<<1] + seg[i<<1|1]; }
	int q; cin >> q; while (q--){
		int typ; cin >> typ;
		if (typ == 1){ int i, x; cin >> i >> x; upd(i, x); }
		if (typ == 2){ ll x; cin >> x; cout << kth(x) << endl; }
	}
}

H. [1168] 요세푸스 문제 2 (Platinum IV)

세그먼트 트리의 각 정점에, 현재까지 살아있는지 여부를 저장해봅시다.

 

그러면, 현재 제거자를 알고 있을 때 다음 제거자는 현재 제거자에서 k번째 뒤에 있는 사람이 되고, 이는

k + (현재 제거자의 위치)번째 참가자를 찾는 게 됩니다.

 

만약 참가자 수가 너무 적어서 저만큼의 사람이 없다면, modular 등을 잘 박아서 1~K 사이의 수로 잘 만들어주면 됩니다.

const int N = 131072;
int seg[262144];

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;
	}
}
int qry(int st, int ed){ st += N-1; ed += N-1;
	int 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;
}
int kth(int k){ int ni = 1;
	while (ni < N){
		if (k <= seg[ni<<1]){ ni = ni<<1; }
		else{ k -= seg[ni<<1]; ni = ni<<1|1; }
	}
	return ni-N+1;
}

void Main(){
	int n, k; cin >> n >> k;
	for (int i = 1; i <= n; i++){ seg[N-1+i] = 1; }
	for (int i = N-1; i >= 1; i--){ seg[i] = seg[i<<1] + seg[i<<1|1]; }
	int ptr = 0; cout << "<";
	for (int c = n; c >= 1; c--){
		int x = (qry(1, ptr) + k) % c; if (x == 0){ x = c; }
		ptr = kth(x); upd(ptr, -1);
		cout << ptr << (c == 1 ? ">" : ", ");
	}
}

I. [13544] 수열과 쿼리 3 (Platinum III)

Merge Sort Tree를 사용해서, 각 구간에서 정렬된 배열을 들고 있어봅시다.

그럼, 쿼리를 날린 뒤 각 정점에서 k보다 큰 원소의 개수를 이진 탐색 등으로 빠르게 찾아주면 됩니다.

const int N = 131072;
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 += seg[st].end() - upper_bound(all(seg[st]), k); st += 1; }
		if (~ed & 1){ res += seg[ed].end() - upper_bound(all(seg[ed]), k); 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++){ int x; cin >> x; seg[N-1+i].push_back(x); }
	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 ans = 0;
	int q; cin >> q; while (q--){
		int st, ed, k; cin >> st >> ed >> k;
		st ^= ans; ed ^= ans; k ^= ans;
		cout << (ans = qry(st, ed, k)) << endl;
	}
}

J. [7469] K번째 수 (Platinum II)

문제의 답인 x가 고정되면, 우리가 위 문제에서 날린 쿼리인 "[st, ed]에 존재하는 x 이상의 수의 개수"를 만들 수 있습니다.

그리고, 당연하겠지만 위 쿼리의 값은 x가 커지면 개수도 따라서 커집니다.

그러니, Merge Sort Tree를 만들고, 문제의 답인 x를 기준으로 위 쿼리를 날리면서 이진 탐색을 돌려주면 됩니다.

const int N = 131072;
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(); st += 1; }
		if (~ed & 1){ res += upper_bound(all(seg[ed]), k) - seg[ed].begin(); ed -= 1; }
		if (st > ed){ break; }
		st >>= 1; ed >>= 1;
	}
	return res;
}

void Main(){
	int n, q; cin >> n >> q;
	for (int i = 1; i <= n; i++){ int x; cin >> x; seg[N-1+i].push_back(x); }
	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() );
	}
	while (q--){
		int st, ed, k; cin >> st >> ed >> k;
		int l = -1e9, r = 1e9, ans = 1;
		while (l <= r){
			int mid = l+r >> 1;
			if (qry(st, ed, mid) >= k){ ans = mid; r = mid-1; } else{ l = mid+1; }
		}
		cout << ans << endl;
	}
}

K. [16993] 연속합과 쿼리 (Platinum II)

문제부터 연속합을 구하는 문제니,

연속합을 구해주는 Continuous Sum Segment Tree를 써주면 됩니다.

저장 방식은 pair< pair<answer, total>, pair<prefix, suffix> >입니다.

pl4 mrg(pl4 p1, pl4 p2){
	pl4 p = { {0, 0}, {0, 0} };
	p.fr.sc = p1.fr.sc + p2.fr.sc;
	p.sc.fr = max(p1.sc.fr, p1.fr.sc + p2.sc.fr);
	p.sc.sc = max(p1.sc.sc + p2.fr.sc, p2.sc.sc);
	p.fr.fr = max({ p1.fr.fr, p2.fr.fr, p1.sc.sc + p2.sc.fr });
	return p;
}

const int N = 131072;
pl4 seg[262150];
ll qry(int st, int ed){ st += N-1; ed += N-1;
	queue<pl4> l; stack<pl4> r;
	while (st <= ed){
		if (st & 1){ l.push(seg[st]); st += 1; }
		if (~ed & 1){ r.push(seg[ed]); ed -= 1; }
		if (st > ed){ break; }
		st >>= 1; ed >>= 1;
	}
	vector<pl4> v;
	while (!l.empty()){ v.push_back(l.front()); l.pop(); }
	while (!r.empty()){ v.push_back(r.top()); r.pop(); }
	int vl = v.size(); pl4 ans = v[0];
	for (int i = 1; i < vl; i++){ ans = mrg(ans, v[i]); }
	return ans.fr.fr;
}

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){
		int x; cin >> x; seg[N-1+i] = { {x, x}, {x, x} };
	}
	for (int i = N-1; i >= 1; i--){ seg[i] = mrg(seg[i<<1], seg[i<<1|1]); }
	int q; cin >> q; while (q--){
		int st, ed; cin >> st >> ed;
		cout << qry(st, ed) << endl;
	}
}

L. [10167] 금광 (Diamond V)

당연하겠지만, 사각형의 각 변은 적어도 1개의 점과 만나야 합니다.

(그렇지 않다면, 그 부분의 길이를 줄여도 답이 바뀌지 않습니다.)

 

그러니, 사각형의 두 y좌표를 고정시켜봅시다.

그러면, 그 두 좌표 사이에 있는 점들에 대해서, 답은 어떠한 연속합의 형태로 나오게 됩니다.

이렇게만 해도 두 y좌표 고정 + 연속합 계산 = \( O(N^2 \times N \log N) \)이니, 뭔가 진척이 있어 보입니다.

그래도 TLE는 TLE니, 더 고쳐봅시다.

 

y좌표의 밑 부분을 고정시키면, 윗 부분을 스위핑해볼 수 있습니다.

그러니, 새로운 y를 잡을 때마다 처음부터 다 계산하는 게 아니라, 지금까지 계산된 거에

새로운 y좌표에 해당되는 점들만 추가해주면 됩니다.

그러면 y의 밑부분 고정 + 윗 부분을 올리'면서' 연속합 계산 = \( O(N \times N \log N) \)이 되어 문제를 풀 수 있게 됩니다.

 

답을 계산할 때는 두 y 좌표 사이에 있는 "모든" 점들이 들어갈 때에만 해야 합니다!

일부 점이 빠지면 그 빠진 점들 때문에 만들어져서는 안 되는 연속합이 만들어질 수 있습니다.

pl4 mrg(pl4 p1, pl4 p2){
	pl4 p = { {0, 0}, {0, 0} };
	p.fr.sc = p1.fr.sc + p2.fr.sc;
	p.sc.fr = max(p1.sc.fr, p1.fr.sc + p2.sc.fr);
	p.sc.sc = max(p1.sc.sc + p2.fr.sc, p2.sc.sc);
	p.fr.fr = max({ p1.fr.fr, p2.fr.fr, p1.sc.sc + p2.sc.fr });
	return p;
}

const int N = 4096;
pl4 seg[8200];
void upd(int pos, ll val){ pos += N-1;
	seg[pos].fr.fr += val; seg[pos].fr.sc += val;
	seg[pos].sc.fr += val; seg[pos].sc.sc += val;
	pos >>= 1;
	while (pos){
		seg[pos] = mrg(seg[pos<<1], seg[pos<<1|1]); pos >>= 1;
	}
}

map<int, int> cvt; set<int> cs; int cc;
pl3 arr[3020];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){
		cin >> arr[i].fr.fr >> arr[i].fr.sc >> arr[i].sc;
		cs.insert(arr[i].fr.sc);
	}
	for (int x : cs){ cvt[x] = ++cc; }
	for (int i = 1; i <= n; i++){ arr[i].fr.sc = cvt[ arr[i].fr.sc ]; }
	sort(arr+1, arr+n+1);
	ll ans = 0;
	for (int i1 = 1; i1 <= n; i1++){
		if (i1 > 1 && arr[i1].fr.fr == arr[i1-1].fr.fr){ continue; }
		memset(seg, 0, sizeof(seg));
		for (int i2 = i1; i2 <= n; i2++){
			upd(arr[i2].fr.sc, arr[i2].sc);
			if (i2 == n || arr[i2].fr.fr != arr[i2+1].fr.fr){ ans = max(ans, seg[1].fr.fr); }
		}
	}
	cout << ans;
}