Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <iostream>
- #include <vector>
- #include <cmath>
- #include <algorithm>
- #include <memory.h>
- #include <map>
- #include <set>
- #include <queue>
- #include <list>
- #include <sstream>
- #include <cstring>
- #include <cassert>
- #include <climits>
- #include <time.h>
- #include <stack>
- using namespace std;
- const int N = 1e6 + 1;
- const int SIZE = (1 << 17);
- const int INF = 1e9;
- int add(int a, int b) {
- return a + b;
- }
- int mul(int a, int b) {
- return a * b;
- }
- struct segment_tree {
- int t[2 * SIZE];
- int pushing[2 * SIZE];
- segment_tree() : t(), pushing() {}
- void build(int n) {
- for (int i = 0; i < n; i++)
- t[SIZE + i] = 0;
- for (int i = SIZE - 1; i > 0; i--) {
- update(i);
- }
- }
- void apply(int v, int l, int r, int val) {
- t[v] = ::add(t[v], mul(val, r - l + 1));
- pushing[v] = ::add(pushing[v], val);
- }
- void push(int v, int l, int r) {
- int m = (r + l) / 2;
- apply(2 * v, l, m, pushing[v]);
- apply(2 * v + 1, m + 1, r, pushing[v]);
- pushing[v] = 0;
- }
- void update(int v) {
- t[v] = ::add(t[2 * v], t[2 * v + 1]);
- }
- void add(int v, int l, int r, int a, int b, int val) {
- if (a > r || b < l)
- return;
- if (a <= l && r <= b) {
- apply(v, l, r, val);
- return;
- }
- int m = (r + l) / 2;
- push(v, l, r);
- add(2 * v, l, m, a, b, val);
- add(2 * v + 1, m + 1, r, a, b, val);
- update(v);
- }
- void add(int a, int b, int val) {
- add(1, 0, SIZE - 1, a, b, val);
- }
- int get_value(int v, int l, int r, int p) {
- if (l == r)
- return t[v];
- int m = (r + l) / 2;
- push(v, l, r);
- if (p <= m)
- return get_value(2 * v, l, m, p);
- return get_value(2 * v + 1, m + 1, r, p);
- }
- int get_value(int p) {
- return get_value(1, 0, SIZE - 1, p);
- }
- } tree;
- int main() {
- //freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- int n;
- scanf("%d", &n);
- tree.build(n + 1);
- for (int i = 0; i <= n; i++) {
- int a, b, c;
- scanf("%d%d%d", &a, &b, &c);
- tree.add(a, b, c);
- }
- for (int i = 1; i <= n; i++) {
- printf("%d ", tree.get_value(i));
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement