2022.07.20. (Segment Tree, Lazy Propagation) 풀이

다룬 태그

• Segment Tree (ABCDEFG)
• Segment Tree with Lazy Propagation (HIJKLM)

A. [2042] 구간 합 구하기 (Gold I)

세그먼트 트리의 기본형 문제입니다.

어떤 원소의 업데이트와, 구간의 합을 처리해주면 됩니다.

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

void upd(int pos, ll 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;
}

void Main(){
	int n, m, k; cin >> n >> m >> k; int q = m+k;
	for (int i = 1; i <= n; i++){ cin >> seg[i+N-1]; }
	for (int i = N-1; i >= 1; i--){ seg[i] = seg[i<<1] + seg[i<<1|1]; }
	while (q--){
		int typ; cin >> typ;
		if (typ == 1){ int pos; ll val; cin >> pos >> val; upd(pos, val); }
		if (typ == 2){ int st, ed; cin >> st >> ed; cout << qry(st, ed) << endl; }
	}
}

B. [11505] 구간 곱 구하기 (Gold I)

세그먼트 트리의 기본형 문제입니다.

구간 합 구하기와의 차이점은, 합 대신 곱을 구해야 한다는 점입니다.

곱을 구해야 하니 query 함수의 기본값이 0 대신 1임에 주의하세요!

const ll mod = 1e9 + 7;
const int N = 1048576;
ll seg[2097160];

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

void Main(){
	int n, m, k; cin >> n >> m >> k; int q = m+k;
	for (int i = 1; i <= n; i++){ cin >> seg[i+N-1]; }
	for (int i = N-1; i >= 1; i--){ seg[i] = seg[i<<1] * seg[i<<1|1] % mod; }
	while (q--){
		int typ; cin >> typ;
		if (typ == 1){ int pos; ll val; cin >> pos >> val; upd(pos, val); }
		if (typ == 2){ int st, ed; cin >> st >> ed; cout << qry(st, ed) << endl; }
	}
}

C. [5676] 음주 코딩 (Gold I)

굉장히 큰 수를 다뤄야 할 것 같지만, 양수 / 음수 / 0을 판별하는 데에는 수의 부호만으로 충분합니다.

그러니, 입력으로 들어오는 수들을 부호에 맞게 1, 0, -1로 바꿔줘도 아무런 문제가 없습니다.

남은 건 구간 곱 구하기로 나오는 값이 1, 0, -1인지에 따라 +, 0, -를 출력하는 부분입니다.

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

void upd(int pos, int val){ pos += N-1;
	if (val > 0){ seg[pos] = 1; } if (val < 0){ seg[pos] = -1; } if (val == 0){ seg[pos] = 0; }
	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 = 1;
	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, q;
	while (cin >> n >> q){
		for (int i = 1; i < 2*N; i++){ seg[i] = 1; }
		for (int i = 1; i <= n; i++){ int x; cin >> x; upd(i, x); }
		while (q--){
			char m; int a, b; cin >> m >> a >> b;
			if (m == 'C'){ upd(a, b); }
			if (m == 'P'){
				int res = qry(a, b);
				if (res > 0){ cout << '+'; } if (res < 0){ cout << '-'; } if (res == 0){ cout << '0'; }
			}
		}
		cout << endl;
	}
}

D. [2357] 최솟값과 최댓값 (Gold I)

최솟값과 최댓값을 찾는 세그먼트 트리입니다.

update는 평소 하던 대로 하면 되고 (min, max로 바꿔야 하겠지만),

query에서의 기본값도 min은 INF, max는 -INF (이 문제는 제한이 양수라서 0도 가능)으로 잡아주면 됩니다.

 

아래 구현의 경우, pair<int, int>로 구간의 min과 max를 동시에 저장하고 있지만,

원하신다면 min 세그와 max 세그를 따로 구현하셔도 됩니다.

const int INF = 2e9;
const int N = 131072;
pi2 seg[262150];

pi2 qry(int st, int ed){ st += N-1; ed += N-1;
	pi2 res = {INF, 0};
	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 n, q; cin >> n >> q;
	for (int i = 1; i <= n; i++){ cin >> seg[i+N-1].fr; seg[i+N-1].sc = seg[i+N-1].fr; }
	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 st, ed; cin >> st >> ed;
		pi2 res = qry(st, ed); cout << res.fr << ' ' << res.sc << endl;
	}
}

E. [14428] 수열과 쿼리 16 (Gold I)

pair<int, int> = (value, index)로 세그먼트 트리의 리프 정점을 초기화시켜주면

그냥 min 함수로 해결이 가능합니다.

 

이는 pair 함수가 first를 비교한 뒤 second를 비교하기 때문인데,

만약 value가 다르다면 더 작은 value를 들고 오고, 두 value가 같다면 index가 더 작은 값을 들고 오게 되기 때문입니다.

const int N = 131072;
const int INF = 2e9; pi2 seg[262150];
void upd(int idx, int val){ int pos = idx + N-1;
	seg[pos] = {val, idx}; pos >>= 1;
	while (pos){
		seg[pos] = min(seg[pos<<1], seg[pos<<1|1]); pos >>= 1;
	}
}
pi2 qry(int st, int ed){ st += N-1; ed += N-1;
	pi2 res = {INF, 0};
	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;
	for (int i = 1; i <= n; i++){ cin >> seg[N-1+i].fr; seg[N-1+i].sc = i; }
	for (int i = n+1; i <= N; i++){ seg[N-1+i] = {INF, i}; }
	for (int i = N-1; i >= 1; i--){ seg[i] = min(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){ int s, e; cin >> s >> e; cout << qry(s, e).sc << endl; }
	}
}

F. [18436] 수열과 쿼리 37 (Gold I)

pair<int, int> = (evenCount, oddCount)로 정의해주면 됩니다.

구간을 합칠 때는 first끼리 더하고, second끼리 더하면 됩니다.

const int N = 131072;
pi2 seg[262150];
void upd(int pos, int val){ pos += N-1;
	seg[pos] = {~val&1, val&1}; pos >>= 1;
	while (pos){
		seg[pos].fr = seg[pos<<1].fr + seg[pos<<1|1].fr;
		seg[pos].sc = seg[pos<<1].sc + seg[pos<<1|1].sc;
		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.fr += seg[st].fr; res.sc += seg[st].sc; st += 1; }
		if (~ed & 1){ res.fr += seg[ed].fr; res.sc += seg[ed].sc; 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] = {~x&1, x&1}; }
	for (int i = N-1; i >= 1; i--){
		seg[i].fr = seg[i<<1].fr + seg[i<<1|1].fr;
		seg[i].sc = seg[i<<1].sc + seg[i<<1|1].sc;
	}
	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){ int s, e; cin >> s >> e; cout << qry(s, e).fr << endl; }
		if (typ == 3){ int s, e; cin >> s >> e; cout << qry(s, e).sc << endl; }
	}
}

G. [1306] 달려라 홍준 (Platinum V)

1 ~ 2M-1에 min 쿼리를 날린 뒤,

2 ~ 2M에 min 쿼리를 날리고,

3 ~ 2M+1에 min 쿼리를 날리고...

를 끝까지 반복해주면 됩니다.

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

int qry(int st, int ed){ st += N-1; ed += N-1;
	int res = 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, m; cin >> n >> m;
	for (int i = 1; i <= n; i++){ cin >> seg[i+N-1]; }
	for (int i = N-1; i >= 1; i--){ seg[i] = max(seg[i<<1], seg[i<<1|1]); }
	for (int i = m; i+m-1 <= n; i++){
		int st = i-m+1, ed = i+m-1;
		cout << qry(st, ed) << ' ';
	}
}

H. [10999] 구간 합 구하기 2 (Platinum IV)

구간에 더하는 업데이트와 구간의 합을 구하는, 전형적인 Lazyseg 문제입니다.

const int N = 1048576;
pl2 seg[2097160];
void pro(int ni, int ns, int ne){
	if (ns != ne){
		seg[ni<<1].sc += seg[ni].sc;
		seg[ni<<1|1].sc += seg[ni].sc;
	}
	int len = ne-ns + 1;
	seg[ni].fr += len*seg[ni].sc; seg[ni].sc = 0;
}
void upd(int ni, int ns, int ne, int qs, int qe, ll qx){
	pro(ni, ns, ne);
	if (qe < ns || ne < qs){ return; }
	if (qs <= ns && ne <= qe){ seg[ni].sc += qx; return pro(ni, ns, ne); }
	int nm = ns+ne >> 1;
	upd(ni<<1, ns, nm, qs, qe, qx); upd(ni<<1|1, nm+1, ne, qs, qe, qx);
	seg[ni].fr = seg[ni<<1].fr + seg[ni<<1|1].fr;
}
inline void upd(int st, int ed, ll val){ return upd(1, 1, N, st, ed, val); }
ll qry(int ni, int ns, int ne, int qs, int qe){
	pro(ni, ns, ne);
	if (qe < ns || ne < qs){ return 0; }
	if (qs <= ns && ne <= qe){ return seg[ni].fr; }
	int nm = ns+ne >> 1;
	return qry(ni<<1, ns, nm, qs, qe) + qry(ni<<1|1, nm+1, ne, qs, qe);
}
inline ll qry(int st, int ed){ return qry(1, 1, N, st, ed); }

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

I. [1395] 스위치 (Platinum III)

어떤 구간에 스위치 반전 쿼리를 2번 넣으면, 아무것도 넣지 않은 상태와 같아지게 됩니다.

이를 토대로, 스위치 반전 쿼리 횟수를 XOR해서 0 또는 1 상태로 저장해둘 수 있게 됩니다.

propagation을 할 때는, 스위치 반전이 있다면 그 구간에 켜진 스위치 개수를 그 구간에 꺼져있었던 스위치의 개수로 바꿔주면 됩니다.

 

나머지는 그냥 구간 합 구하듯이 구해주면 됩니다.

const int N = 131072;
pl2 seg[262150];
void pro(int ni, int ns, int ne){
	if (ns != ne){
		seg[ni<<1].sc ^= seg[ni].sc;
		seg[ni<<1|1].sc ^= seg[ni].sc;
	}
	int len = ne-ns + 1;
	if (seg[ni].sc){ seg[ni].fr = len - seg[ni].fr; } seg[ni].sc = 0;
}
void upd(int ni, int ns, int ne, int qs, int qe){
	pro(ni, ns, ne);
	if (qe < ns || ne < qs){ return; }
	if (qs <= ns && ne <= qe){ seg[ni].sc ^= 1; return pro(ni, ns, ne); }
	int nm = ns+ne >> 1;
	upd(ni<<1, ns, nm, qs, qe); upd(ni<<1|1, nm+1, ne, qs, qe);
	seg[ni].fr = seg[ni<<1].fr + seg[ni<<1|1].fr;
}
inline void upd(int st, int ed){ return upd(1, 1, N, st, ed); }
ll qry(int ni, int ns, int ne, int qs, int qe){
	pro(ni, ns, ne);
	if (qe < ns || ne < qs){ return 0; }
	if (qs <= ns && ne <= qe){ return seg[ni].fr; }
	int nm = ns+ne >> 1;
	return qry(ni<<1, ns, nm, qs, qe) + qry(ni<<1|1, nm+1, ne, qs, qe);
}
inline ll qry(int st, int ed){ return qry(1, 1, N, st, ed); }

void Main(){
	int n, q; cin >> n >> q;
	while (q--){
		int typ; cin >> typ;
		if (typ == 0){ int st, ed; cin >> st >> ed; upd(st, ed); }
		if (typ == 1){ int st, ed; cin >> st >> ed; cout << qry(st, ed) << endl; }
	}
}

J. [12844] XOR (Platinum III)

구간 XOR 업데이트와 구간 XOR 쿼리입니다.

propagate를 할 때, 구간 안에 xor이 홀수 번 되어야 = 구간의 길이가 홀수여야 xor 업데이트를 해줘야 함에 주의하세요!

const int N = 524288;
pl2 seg[1048580];
void pro(int ni, int ns, int ne){
	if (ns != ne){
		seg[ni<<1].sc ^= seg[ni].sc;
		seg[ni<<1|1].sc ^= seg[ni].sc;
	}
	int len = ne-ns + 1;
	if (len & 1){ seg[ni].fr ^= seg[ni].sc; } seg[ni].sc = 0;
}
void upd(int ni, int ns, int ne, int qs, int qe, ll qx){
	pro(ni, ns, ne);
	if (qe < ns || ne < qs){ return; }
	if (qs <= ns && ne <= qe){ seg[ni].sc ^= qx; return pro(ni, ns, ne); }
	int nm = ns+ne >> 1;
	upd(ni<<1, ns, nm, qs, qe, qx); upd(ni<<1|1, nm+1, ne, qs, qe, qx);
	seg[ni].fr = seg[ni<<1].fr ^ seg[ni<<1|1].fr;
}
inline void upd(int st, int ed, ll qx){ return upd(1, 1, N, st, ed, qx); }
ll qry(int ni, int ns, int ne, int qs, int qe){
	pro(ni, ns, ne);
	if (qe < ns || ne < qs){ return 0; }
	if (qs <= ns && ne <= qe){ return seg[ni].fr; }
	int nm = ns+ne >> 1;
	return qry(ni<<1, ns, nm, qs, qe) ^ qry(ni<<1|1, nm+1, ne, qs, qe);
}
inline 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[N-1+i].fr; }
	for (int i = N-1; i >= 1; i--){ seg[i].fr = seg[i<<1].fr ^ seg[i<<1|1].fr; }
	int q; cin >> q; while (q--){
		int typ; cin >> typ;
		if (typ == 1){ int st, ed, x; cin >> st >> ed >> x; st++; ed++; upd(st, ed, x); }
		if (typ == 2){ int st, ed; cin >> st >> ed; st++; ed++; cout << qry(st, ed) << endl; }
	}
}

K. [12895] 화려한 마을 (Platinum III)

각 구간에 있는 색깔을 bitmask로 저장해봅시다. 그럼 i번 비트는 '이 구간 안에 i번 색이 존재하는가'를 저장하게 됩니다.

세그먼트 트리니, 두 구간의 합집합은 bitmask간의 bitwise or 연산으로 처리할 수 있습니다.

 

구간에 값 변경 쿼리를 날리는데, 이 경우는 bitmask를 해야 하니

x번 색깔로 변경 → 구간 내의 모든 수를 1<<x로 변경 으로 놓으면 됩니다.

 

x와 y 사이에 있는 집이기 때문에, x > y가 주어질 수 있음에 주의하세요!

const int N = 131072; pi2 seg[262150];
void pro(int nod, int ns, int ne){
	if (seg[nod].sc == 0){ return; }
	seg[nod].fr = seg[nod].sc;
	if (ns != ne){
		seg[nod<<1].sc = seg[nod].sc;
		seg[nod<<1|1].sc = seg[nod].sc;
	}
	seg[nod].sc = 0;
}
void upd(int nod, int ns, int ne, int st, int ed, int val){
	pro(nod, ns, ne);
	if (ed < ns || ne < st){ return; }
	if (st <= ns && ne <= ed){ seg[nod].sc = val; return pro(nod, ns, ne); }
	int mid = ns+ne >> 1;
	upd(nod<<1, ns, mid, st, ed, val); upd(nod<<1|1, mid+1, ne, st, ed, val);
	int x1 = seg[nod<<1].sc==0 ? seg[nod<<1].fr : seg[nod<<1].sc;
	int x2 = seg[nod<<1|1].sc==0 ? seg[nod<<1|1].fr : seg[nod<<1|1].sc;
	seg[nod] = {x1 | x2, 0};
}
void upd(int st, int ed, int val){ return upd( 1, 1, N, st, ed, 1<<(val-1) ); }
int qry(int nod, int ns, int ne, int st, int ed){
	pro(nod, ns, ne);
	if (ed < ns || ne < st){ return 0; }
	if (st <= ns && ne <= ed){ return seg[nod].fr; }
	int mid = ns+ne >> 1;
	return qry(nod<<1, ns, mid, st, ed) | qry(nod<<1|1, mid+1, ne, st, ed);
}
int qry(int st, int ed){ return qry(1, 1, N, st, ed); }

void Main(){
	int n, m, q; cin >> n >> m >> q;
	for (int i = 1; i < N+N; i++){ seg[i] = {1, 0}; }
	while (q--){
		char m; cin >> m;
		if (m == 'C'){
			int st, ed, col; cin >> st >> ed >> col;
			if (st > ed){ swap(st, ed); }
			upd(st, ed, col);
		}
		if (m == 'Q'){
			int st, ed; cin >> st >> ed;
			if (st > ed){ swap(st, ed); }
			int res = qry(st, ed);
			int cnt = 0; while (res){ cnt += 1; res -= res&-res; }
			cout << cnt << endl;
		}
	}
}

L. [17407] 괄호 문자열과 쿼리 (Platinum III)

어떤 문자열이 괄호 문자열이 되는 필요충분조건은 아래와 같습니다.

• '('를 +1, ')'를 -1이라고 두자.
• 이 때 문자열의 전체 합은 0이어야 한다. (\( P_{N} = \sum_{i=1}^{N} = 0 \))
• 또한, 모든 prefix의 합은 0 이상이어야 한다. (\( P_{i} = \sum_{i=1}^{p} A_{i} \geq 0 \text{ forall } p \))

그러니, 각 위치의 prefix의 합을 세그먼트 트리로 관리해주면, Range Minimum Query로 문제를 풀 수 있습니다.

(prefix의 합 중 최솟값이 0 이상인가로 판별)

 

'(' → ')'는, 그 위치에 있는 수부터 끝까지의 수들에 2를 빼는 쿼리고,
')' → '('는, 그 위치에 있는 수부터 끝까지의 수들에 2를 더하는 쿼리로 볼 수 있습니다.

그러니, Range Add Update로 괄호 변경을 나타낼 수 있습니다.

 

결국 이 문제는 Range Add Update / Range Minimum Query의 Lazyseg 문제가 됩니다.

const int N = 131072, INF = 1e9; pi2 seg[262150];
void pro(int nod, int ns, int ne){
	seg[nod].fr += seg[nod].sc;
	if (ns != ne){
		seg[nod<<1].sc += seg[nod].sc;
		seg[nod<<1|1].sc += seg[nod].sc;
	}
	seg[nod].sc = 0;
}
void upd(int nod, int ns, int ne, int st, int ed, int dif){
	pro(nod, ns, ne);
	if (ed < ns || ne < st){ return; }
	if (st <= ns && ne <= ed){ seg[nod].sc += dif; return pro(nod, ns, ne); }
	int mid = ns+ne >> 1;
	upd(nod<<1, ns, mid, st, ed, dif); upd(nod<<1|1, mid+1, ne, st, ed, dif);
	int x1 = seg[nod<<1].fr + seg[nod<<1].sc;
	int x2 = seg[nod<<1|1].fr + seg[nod<<1|1].sc;
	seg[nod] = {min(x1, x2), 0};
}
void upd(int st, int ed, int dif){ return upd(1, 1, N, st, ed, dif); }
int qry(int nod, int ns, int ne, int st, int ed){
	pro(nod, ns, ne);
	if (ed < ns || ne < st){ return INF; }
	if (st <= ne && ne <= ed){ return seg[nod].fr; }
	int mid = ns+ne >> 1;
	return min( qry(nod<<1, ns, mid, st, ed), qry(nod<<1|1, mid+1, ne, st, ed) );
}
int qry(int st, int ed){ return qry(1, 1, N, st, ed); }

void Main(){
	for (int i = 1; i < N+N; i++){ seg[i] = {INF, 0}; }
	string s; cin >> s; int n = s.size(); s = " " + s;
	int sum = 0;
	for (int i = 1; i <= n; i++){
		if (s[i] == '('){ sum += 1; } else{ sum -= 1; }
		seg[i+N-1] = {sum, 0};
	}
	for (int i = N-1; i >= 1; i--){
		seg[i] = { min(seg[i<<1].fr, seg[i<<1|1].fr), 0 };
	}
	int ans = 0;
	int q; cin >> q;
	while (q--){
		int pos; cin >> pos;
		if (s[pos] == '('){ sum -= 2; upd(pos, n, -2); }
		else{ sum += 2; upd(pos, n, 2); }
		//cout << "QRY " << sum << ' ' << qry(1, n) << endl;
		if (sum == 0 && qry(1, n) == 0){ ans += 1; }
		s[pos] ^= '('^')';
	}
	cout << ans;
}

M. [17353] 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별 (Platinum II)

각 세그먼트 트리에 ax + b 형식의 값을 저장시켜봅시다.

이는 x번 위치에 ax + b개의 별이 떨어졌음을 의미합니다.

 

이러면 별이 떨어지는 쿼리는 [st, ed] 구간에 x - (st-1)만큼의 별을 떨어뜨리는 쿼리로 볼 수 있고,

직선의 방정식을 생각해보면 구간을 합칠 때는 그냥 x의 계수끼리 / 상수항끼리 합쳐주면 됩니다.

 

어떤 위치에 별이 몇 개 떨어졌는지는, ax + b에서 a와 b를 쿼리로 구한 뒤 여기에 위치 x를 받아와서

ax + b를 출력해주면 됩니다.

const int N = 131072; pl4 seg[262150];
void pro(int nod, int ns, int ne){ int cnt = ne-ns + 1;
	seg[nod].fr.fr += seg[nod].sc.fr * cnt;
	seg[nod].fr.sc += seg[nod].sc.sc * cnt;
	if (ns != ne){
		seg[nod<<1].sc.fr += seg[nod].sc.fr;
		seg[nod<<1].sc.sc += seg[nod].sc.sc;
		seg[nod<<1|1].sc.fr += seg[nod].sc.fr;
		seg[nod<<1|1].sc.sc += seg[nod].sc.sc;
	}
	seg[nod].sc = {0, 0};
}
void upd(int nod, int ns, int ne, int st, int ed, pl2 val){
	pro(nod, ns, ne);
	if (ed < ns || ne < st){ return; }
	if (st <= ns && ne <= ed){
		seg[nod].sc.fr += val.fr; seg[nod].sc.sc += val.sc;
		return pro(nod, ns, ne);
	}
	int mid = ns+ne >> 1;
	upd(nod<<1, ns, mid, st, ed, val); upd(nod<<1|1, mid+1, ne, st, ed, val);
	seg[nod].sc.fr = seg[nod<<1].sc.fr + seg[nod<<1|1].sc.fr;
	seg[nod].sc.sc = seg[nod<<1].sc.sc + seg[nod<<1|1].sc.sc;
}
void upd(int st, int ed, pl2 val){ return upd(1, 1, N, st, ed, val); }
pl2 qry(int nod, int ns, int ne, int pos){
	pro(nod, ns, ne);
	if (pos < ns || ne < pos){ return {0, 0}; }
	if (pos <= ns && ne <= pos){ return seg[nod].fr; }
	int mid = ns+ne >> 1;
	pl2 r1 = qry(nod<<1, ns, mid, pos), r2 = qry(nod<<1|1, mid+1, ne, pos);
	return {r1.fr+r2.fr, r1.sc+r2.sc};
}
pl2 qry(int pos){ return qry(1, 1, N, pos); }

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ int x; cin >> x; upd(i, i, {0, x}); }
	int q; cin >> q;
	while (q--){
		int m; cin >> m;
		if (m == 1){ int st, ed; cin >> st >> ed; upd(st, ed, {1, -st+1}); }
		if (m == 2){
			int pos; cin >> pos;
			pl2 res = qry(pos);
			cout << res.fr*pos + res.sc << endl;
		}
	}
}