백준 14268 - 회사 문화 2(C++)

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

 

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

#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 Tree[100001 * 4];
long long left_tree[100001 * 4], right_tree[100001 * 4];
long long lazy[100001 * 4];
vector<int> connect[100001];

void make_order(int node, int &cnt){
	left_tree[node] = ++cnt;
	for(int i = 0; i < connect[node].size(); i++){
		int n_node = connect[node][i];
		make_order(n_node, cnt);
	}
	right_tree[node] = cnt;
}

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

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

long long get_node(int node, int st, int fin, int left, int right){
	update_lazy(node, st, fin);
	if(st > right || fin < left) return 0;
	if(left <= st && fin <= right) return Tree[node];
	int mid = (st + fin) / 2;
	long long left_node = get_node(node * 2, st, mid, left, right);
	long long right_node = get_node(node * 2 + 1, mid + 1 ,fin, left, right);
	return (left_node + right_node);
}

void solve(){
	int cnt = 0;
	make_order(1, cnt);
	for(int i = 1; i <= N * 4; i++) cout << left_tree[i] << " ";
	cout << "\n";   
	for(int i = 1; i <= N * 4; i++) cout << right_tree[i] << " ";
	cout << "\n";
	for(int i = 1; i <= M; i++){
		int a, x, y;
		scanf("%d", &a);
		if(a == 1){
			scanf("%d %d", &x, &y);
			update_tree(1, 0, N - 1, left_tree[x] - 1, right_tree[x] - 1, y);
		}
		else{
			scanf("%d", &x);
			cout << get_node(1, 0, N - 1, left_tree[x] - 1, left_tree[x] - 1) << "\n";
		}
	}
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for(int i = 1; i <= N; i++) {
		int x;
		scanf("%d", &x);
		if(x != -1) connect[x].push_back(i);
	}
	solve();
	return 0;
}

 

 

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