JOISC19 Antennas

문제

oj.uz/problem/view/JOI19_antennas

문제 보기 - Two Antennas (JOI19_antennas) :: oj.uz

N개의 안테나마다 $A$, $B$, $H$의 값이 주어지는데, 이는 $i$번째 안테나가 통신할 수 있는 거리의 범위가 $A$이상 $B$이하이며, 높이가 $H$라는 것을 의미한다. 서로 다른 두 안테나 $i, j$ 사이의 거리는 $|i-j|$로 정의된다. 이 때 Q개의 $(l, r)$쿼리가 주어지는데, 이는 $[l, r]$구간에 있는 안테나들 중 서로 양방향으로 통신할 수 있는 $i$와 $j$에 대하여 $|H_i-H_j|$의 값들 중 최댓값을 출력해야 한다.

$N<=200000$

$Q<=200000$

 

풀이

먼저, 두 안테나 $i$, $j$가 서로 양방향으로 통신할 수 있는 조건은 다음과 같다.

$i<j$  ,  $i+A_i<=j<=i+B_i$  ,  $j-B_j<=i<=j-A_j$

 

절댓값 처리에 대한 조건이 까다롭기 때문에 다음과 같이 바꿔 해석할 수 있다.

Observation 1 : $ |H_i-H_j|=max(H_i-H_j, -H_i+H_j) $

$i<j$일 때 $-H_i+H_j$의 값을 최대화한 후,  $H$값들의 부호를 뒤집어서 다시 구하면 된다.

 

구간 쿼리들을 효율적으로 처리하기 위해 다음과 같이 답을 구한다.

Observation 2 : 쿼리들을 r값을 기준으로 정렬한 후, 배열의 왼쪽부터 한 칸씩 추가하며 각 값이 왼쪽 끝점일 때의 쿼리의 답을 저장하는 ans 배열을 관리할 수 있으면 문제를 해결할 수 있다.

 

이제, 배열의 오른쪽에 새로운 안테나를 추가했을 때 ans 배열이 어떻게 바뀔까?

새로운 안테나가 영향을 줄 수 있는 범위는 해당 안테나의 통신 범위인 $[i-B_i, i-A_i]$에 해당하는 구간이다.

다시 말해, $i-B_i<=j<=i-A_i$인 $j<i$에 대하여 $j+A_j<=i<=j+B_j$를 만족하는 $j$를 골라 $ans[j]=max(ans[j], -H_j+H_i)$값으로 업데이트 해주면 된다.

 

문제를 조금 더 간단히 만들어 $j+A_j<=i<=j+B_j$조건을 무시하고 $[i-B_i, i-A_i]$구간의 $j$에 대해 $ans[j]=max(ans[j], -H_j+H_i)$값으로 업데이트할 수 있으면 된다.

구간 업데이트이니, 레이지 연산을 적용할 수 있는지 확인하자.

$j$에 대해 $-H_j$는 고정이므로 추가로 더하는 $-H_j+x$의 $x$를 최대화 하면 된다.

 

레이지 연산을 적용하기 위한 조건은

1. 업데이트 연산의 결합 법칙이 성립

2. 업데이트 값과 구간의 값을 알고 있을 때 새로운 구간의 값을 빠르게 구할 수 있어야 한다.

 

$x$를 최댓값으로 씌우는 것이 레이지 연산이니, 이 연산에는 결합 법칙이 성립한다.

업데이트 한 후, 구간의 최댓값을 갱신하기 위해서는 업데이트 하기 전의 그 구간의 최댓값 뿐만 아니라 $-H_j$의 최댓값 또한 알고 있어야 한다.

이를 알면 lazy 값을 이용하여 새로운 값들로 갱신해 줄 수 있다.

 

이제 위에서 무시했던 $j+A_j<=i<=j+B_j$ 조건에 대해 생각해 보자. $j$를 고정시켜 놓고 생각하면, 그 $j$가 업데이트될 수 있는 시간은 위 $i$가 해당 범위에 들어가는 것이기 때문에, 결국 오른쪽에서 하나씩 $i$를 추가하는 입장에서 살펴보면 $j$의 활성화 / 비활성화 여부가 하나의 구간으로 나타난다고 생각할 수 있다. 따라서 처음에는 $-H_j$의 값을 -INF로 설정했다가, 활성화 될 때 그 값을 원래의 값으로 바꿔 주고, 다시 비활성화 될때 -INF로 설정해 준다고 생각하면 된다.

이는 단일 업데이트로 해결해줄 수 있다.

 

모든 과정에서 업데이트될 때 ans는 누적 최댓값이니, 단일 업데이트 과정에서 ans를 줄이지 않도록 주의하자.

 

시간 복잡도 : $O((N+Q)logN)$

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 2e5;
const ll INF = 1e17;
 
struct Query
{
	int l, r, p;
};
 
int N, Q;
int A[MAXN+10], B[MAXN+10], H[MAXN+10];
Query C[MAXN+10];
 
struct Node
{
	ll lazy, val, val2;
	Node() : lazy(-INF), val(-INF), val2(-INF) {}
};
 
Node tree[MAXN*4+10];
ll P[MAXN+10], ans[MAXN+10];
 
Node operator + (Node p, Node q)
{
	Node ret;
	ret.val=max(p.val, q.val);
	ret.val2=max(p.val2, q.val2);
	return ret;
}
 
void busy(int node, int tl, int tr)
{
	tree[node].val=max(tree[node].val, tree[node].val2+tree[node].lazy);
	if(tl!=tr) tree[node*2].lazy=max(tree[node*2].lazy, tree[node].lazy), tree[node*2+1].lazy=max(tree[node*2+1].lazy, tree[node].lazy);
	else P[tl]=max(P[tl], tree[node].lazy);
	tree[node].lazy=-INF;
}
 
void init(int node, int tl, int tr)
{
	tree[node]=Node();
	if(tl==tr)
	{
		P[tl]=-INF;
		return;
	}
	int mid=tl+tr>>1;
	init(node*2, tl, mid);
	init(node*2+1, mid+1, tr);
}
 
void update1(int node, int tl, int tr, int l, int r, ll k)
{
	busy(node, tl, tr);
	if(r<tl || tr<l) return;
	if(l<=tl && tr<=r)
	{
		tree[node].lazy=k;
		busy(node, tl, tr);
		return;
	}
	int mid=tl+tr>>1;
	update1(node*2, tl, mid, l, r, k);
	update1(node*2+1, mid+1, tr, l, r, k);
	tree[node]=tree[node*2]+tree[node*2+1];
}
 
void update2(int node, int tl, int tr, int p, ll k)
{
	busy(node, tl, tr);
	if(tr<p || p<tl) return;
	if(tl==tr)
	{
		tree[node].val2=k;
		return;
	}
	int mid=tl+tr>>1;
	update2(node*2, tl, mid, p, k);
	update2(node*2+1, mid+1, tr, p, k);
	tree[node]=tree[node*2]+tree[node*2+1];
}
 
ll query(int node, int tl, int tr, int l, int r)
{
	busy(node, tl, tr);
	if(l<=tl && tr<=r) return tree[node].val;
	if(r<tl || tr<l) return -INF;
	int mid=tl+tr>>1;
	return max(query(node*2, tl, mid, l, r), query(node*2+1, mid+1 ,tr, l, r));
}
 
int main()
{
	scanf("%d", &N);
	for(int i=1; i<=N; i++) scanf("%d%d%d", &H[i], &A[i], &B[i]);
	scanf("%d", &Q);
	for(int i=1; i<=Q; i++) scanf("%d%d", &C[i].l, &C[i].r), C[i].p=i;
 
	sort(C+1, C+Q+1, [&](const Query &p, const Query &q) { return p.r<q.r; });
	
	vector<pii> V;
	for(int i=1; i<=N; i++)
	{
		V.push_back({i+A[i], i});
		V.push_back({i+B[i]+1, -i});
	}	
	sort(V.begin(), V.end());
 
	for(int i=1; i<=Q; i++) ans[i]=-INF;
 
	init(1, 1, N);
	for(int i=1, j=0, k=1; i<=N; i++)
	{
		for(; j<V.size() && V[j].first<=i; j++)
		{
			if(V[j].second>0) 
			{
				update2(1, 1, N, V[j].second, -H[V[j].second]);
			}
			else
			{
				update2(1, 1, N, -V[j].second, -INF);
			}
		}
		int l=i-B[i], r=i-A[i];
		update1(1, 1, N, l, r, H[i]);
		for(; k<=Q && C[k].r==i; k++)
		{
			ans[C[k].p]=max(ans[C[k].p], query(1, 1, N, C[k].l, C[k].r));
		}
	}
 
	for(int i=1; i<=N; i++) H[i]=-H[i];
	init(1, 1, N);
	for(int i=1, j=0, k=1; i<=N; i++)
	{
		for(; j<V.size() && V[j].first<=i; j++)
		{
			if(V[j].second>0) 
			{
				update2(1, 1, N, V[j].second, -H[V[j].second]);
			}
			else
			{
				update2(1, 1, N, -V[j].second, -INF);
			}
		}
		int l=i-B[i], r=i-A[i];
		update1(1, 1, N, l, r, H[i]);
		for(; k<=Q && C[k].r==i; k++)
		{
			ans[C[k].p]=max(ans[C[k].p], query(1, 1, N, C[k].l, C[k].r));
		}
	}
 
	for(int i=1; i<=Q; i++)
	{
		if(ans[i]<0) ans[i]=-1;
		printf("%lld\n", ans[i]);
	}
}