BOJ 11989 단층

문제 링크입니다.

풀이

1. 그림을 45도 기울여 생각합시다. 두 쿼리를 x/y방향으로 2배로 미는 것으로 처리해서, 나중에 밀린 양을 반으로 줄이면 됩니다.
2. 단층이 밀리는 정도는 방향 별로 계단 모양을 그립니다. 1번 쿼리로는 왼쪽으로 갈수록 밀리는 정도가 커지고, 2번 쿼리로는 오른쪽으로 갈수록 커짐을 알 수 있습니다.
3. 단층의 밀림을 역순으로 처리합니다. 그러면, 쿼리를 처리하기 전에 쿼리가 실제로 영향을 미치는 곳을 이후에 반대방향으로 밀릴 거리를 토대로 추론할 수 있습니다.
4. 2, 3번을 바탕으로 이분 탐색으로 쿼리가 영향을 미칠 구간의 경계를 찾아낼 수 있습니다. 각 방향으로 밀린 정도를 펜윅 트리로 관리하면서, 이번에 밀려지면서 생겨날 층의 두께와 이후에 반대방향으로 밀어올릴 거리를 비교합니다. Binary Lifting으로 ${\cal O} (\lg N)$에 처리할 수 있습니다.

총 시간 복잡도는 ${\cal O}((N+Q) \lg N)$입니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
const int N = 202000;
const int LG = 17;

int n, q;

struct fen{
	ll tree[202020]={};
	void upd(int i, ll v){for(;i<=N;i+=i&-i)tree[i]+=v;}
	ll qry(int i){ll ret=0; for(;i;i-=i&-i)ret+=tree[i]; return ret;}
}xfen, yfen;

void q1(ll x, ll v){ //xfen
	int idx = 0; ll sum = 0;
	for(int i = LG; i >= 0; i--){
		if(idx+(1<<i) <= n && sum+yfen.tree[idx+(1<<i)] <= x-(idx+(1<<i))){
			idx += 1<<i;
			sum += yfen.tree[idx];
		}
	}
	if(sum <= x-idx){
		xfen.upd(1, v);
		xfen.upd(idx+1, -v);
	}
}

void q2(ll x, ll v){ //yfen
	int idx = 0; ll sum = 0;
	for(int i = LG; i >= 0; i--){
		if(idx+(1<<i) <= n && sum+xfen.tree[idx+(1<<i)] >= (idx+(1<<i))-x){
			idx += 1<<i;
			sum += xfen.tree[idx];		
		}
	}
	idx++;
	if(xfen.qry(idx) < idx-x){
		yfen.upd(idx, v);
	}
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	cin >> n >> q; vector<ll> x(q+1), d(q+1), v(q+1);
	for(int i = 1; i <= q; i++) cin >> x[i] >> d[i] >> v[i];
	for(int i = q; i; i--){
		if(d[i] == 1) q1(x[i], 2*v[i]);
		else q2(x[i], 2*v[i]);
	}
	for(int i = 1; i <= n; i++) cout << (xfen.qry(i)+yfen.qry(i))/2 << '\n';
}