Created
June 16, 2018 13:38
-
-
Save purplesyringa/ef79ba091ccdebc042dcf9ee4a8bfdee to your computer and use it in GitHub Desktop.
clang bug?
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// | |
// main.cpp | |
// Work in Moscow | |
// | |
// Created by Ivan Gorbunov on 21.07.17. | |
// Copyright © 2017 Ivan Gorbunov. All rights reserved. | |
// | |
#include <algorithm> | |
#include <iostream> | |
#include <cstdlib> | |
#include <unistd.h> | |
#include <fstream> | |
#include <stdio.h> | |
#include <iomanip> | |
#include <clocale> | |
#include <string> | |
#include <vector> | |
#include <cmath> | |
#include <ctime> | |
#include <stack> | |
#include <queue> | |
#include <deque> | |
#include <set> | |
#include <map> | |
using namespace std; | |
#define int long long | |
struct tree_element { | |
int value = 0; | |
int add = 0; | |
}; | |
int n; | |
tree_element t[100000000]; | |
void push(int v, int l, int r) { | |
if (v * 2 + 1 < 4 * n) { | |
t[v * 2 + 1].add += t[v].add; | |
} | |
if (v * 2 + 2 < 4 * n) { | |
t[v * 2 + 2].add += t[v].add; | |
} | |
t[v].value += t[v].add * (r - l); | |
t[v].add = 0; | |
return; | |
} | |
void build (int a[], int v, int l, int r) { | |
if (l == r - 1) { | |
t[v].value = a[l]; | |
} else { | |
int m = (l + r) / 2; | |
build (a, v * 2 + 1, l, m); | |
build (a, v * 2 + 2, m, r); | |
t[v].value = t[v * 2 + 1].value + t[v * 2 + 2].value; | |
} | |
} | |
void update (int v, int l, int r, int pos, int new_val) { | |
if (l == r - 1) | |
t[v].value = new_val; | |
else { | |
int m = (l + r) / 2; | |
if (pos <= m) { | |
update (v * 2 + 1, l, m, pos, new_val); | |
} else { | |
update (v * 2 + 2, m, r, pos, new_val); | |
} | |
t[v].value = t[v * 2 + 1].value + t[v * 2 + 2].value; | |
} | |
} | |
int all_sum (int v, int l, int r, int vl, int vr) { | |
if (l >= r) { | |
return 0; | |
} | |
push(v, vl, vr); | |
if (l == vl && r == vr) { | |
return t[v].value; | |
} | |
int vm = (vl + vr) / 2; | |
int sum1 = all_sum(v * 2 + 1, l, min(r, vm), vl, vm); | |
int sum2 = all_sum(v * 2 + 2, max(l, vm), r, vm, vr); | |
return sum1 + sum2; | |
} | |
void mas_add(int v, int l, int r, int vl, int vr, int add_value) { | |
if (l >= r) { | |
return; | |
} | |
if (l == vl && r == vr) { | |
t[v].add += add_value; | |
return; | |
} | |
push(v, vl, vr); | |
int vm = (vl + vr) / 2; | |
mas_add(v * 2 + 1, l, min(r, vm), vl, vm, add_value); | |
mas_add(v * 2 + 2, max(l, vm), r, vm, vr, add_value); | |
pull(v, vl, vrw); | |
return; | |
} | |
signed main() { | |
int m; | |
cin >> n >> m; | |
int arr[n]; | |
for (int i = 0; i < n; i++) { | |
arr[i] = 0; | |
} | |
build(arr, 0, 0, n); | |
for (int i = 0; i < m; i++) { | |
int c; | |
cin >> c; | |
if (c == 1) { | |
int a, b, value; | |
cin >> a >> b >> value; | |
b++; | |
mas_add(0, a, b, 0, n, value); | |
} else { | |
int a, b; | |
cin >> a >> b; | |
b++; | |
cout << a << " " << b << " NOW SUM IS " << all_sum(0, a, b, 0, n) << endl; | |
} | |
for (int i = 0; i < n; i++) { | |
cout << all_sum(0, i, i + 1, 0, n) << " "; | |
} | |
cout << endl; | |
//cout << all_sum(0, 0, n, 0, n) << endl; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment