백준 16975 - 수열과 쿼리 21(C++)

문제 링크입니다. https://www.acmicpc.net/problem/16975

 

느리게 갱신되는 세그먼트 트리를 이용한 문제입니다.

 

주어지는 쿼리의 수가 많기에 일반적으로 값을 바꾸는 세그먼트 트리를 사용한다면 시간초과가 생길 가능성이 높습니다.

따라서, 느리게 갱신되는 세그먼트 트리를 이용해 주시면 됩니다.

 

 

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>

using namespace std;

int N, M;
long long Index[100001];
long long Tree[100001 * 4];
long long lazy[100001 * 4];

long long segment_tree(int num, int st, int fin) {
	if (st == fin) return Tree[num] = Index[st];
	int mid = (st + fin) / 2;
	long long left = segment_tree(num * 2, st, mid);
	long long right = segment_tree(num * 2 + 1, mid + 1, fin);
	return Tree[num] = (left + right);
}

void update_lazy(int num, int left, int right) {
	if (lazy[num]) {
		Tree[num] += (lazy[num] * (right - left + 1));
		if (left != right) {
			lazy[num * 2] += lazy[num];
			lazy[num * 2 + 1] += lazy[num];
		}
		lazy[num] = 0;
	}
}

void change_Tree(int num, int left, int right, int st, int fin, long long diff) {
	update_lazy(num, st, fin);
	if (left > fin || right < st) return;
	if (left <= st && right >= fin) {
		Tree[num] += (diff * (fin - st + 1));
		if (st != fin){
			lazy[num * 2] += diff;
			lazy[num * 2 + 1] += diff;
		}
		return;
	}
	int mid = (st + fin) / 2;
	change_Tree(num * 2, left, right, st, mid, diff);
	change_Tree(num * 2 + 1, left, right, mid + 1, fin, diff);
	Tree[num] = Tree[num * 2] + Tree[num * 2 + 1];
}

long long get_sum(int num, int left, int right, int st, int fin) {
	update_lazy(num, st, fin);
	if (left > fin || right < st) return 0;
	if (left <= st && right >= fin) return Tree[num];
	int mid = (st + fin) / 2;
	long long left_sum = get_sum(num * 2, left, right, st, mid);
	long long right_sum = get_sum(num * 2 + 1, left, right, mid + 1, fin);
	return (left_sum + right_sum);
}

void solve() {
	segment_tree(1, 0, N - 1);
	cin >> M;
	for (int i = 1; i <= M; i++) {
		int a, b, c;
		long long d;
		cin >> a;
		if (a == 1) { // add d -> b to c
			scanf("%d %d %lld", &b, &c, &d);
			change_Tree(1, b - 1, c - 1, 0, N - 1, d);
		}
		else { // sum b to c
			scanf("%d", &b);
			cout << get_sum(1, b - 1, b - 1, 0, N - 1) << "\n";
		}
	}
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) scanf("%lld", &Index[i]);
	solve();
	return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요.