Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- РУБРИКА "АНЕКИ В КОММЕНТАХ"
- "
- В дверь постучали 1024 раза.
- - Килобайт - подумал Штирлиц.
- - Не угадал, подумали 10 сороконожек и 78 осьминогов
- "
- */
- #pragma warning(disable: 4996)
- #pragma warning(disable: 6031)
- #include <iostream>
- #include <vector>
- #include <string>
- #include <algorithm>
- #include <queue>
- #include <cmath>
- #include <math.h>
- #include <set>
- #include <stack>
- #include <iomanip>
- #include <random>
- #define ll long long
- using namespace std;
- vector<int> tree, add;
- int k;
- void insert(int ind, int value) {
- int uk1 = k + ind;
- tree[uk1] = value;
- while (uk1 != 0) {
- tree[uk1 / 2] = tree[(uk1 / 2)*2] + tree[(uk1 / 2)*2 + 1];
- uk1 /= 2;
- }
- }
- int getSum(int v, int tl, int tr, int l, int r) {
- //cout << " " << tl << " " << tr << " " << l << " " << r << " v: " << v << ": " << tree[v] << '\n';
- if (r <= tl || l >= tr)
- return 0;
- if (add[v] != 0) {
- tree[v] += (tr - tl) * add[v];
- if (tr - tl > 1) {
- add[v * 2] = add[v];
- add[v * 2 + 1] = add[v];
- }
- add[v] = 0;
- }
- if (tl >= l && tr <= r)
- return tree[v];
- int mid = tl + (tr - tl) / 2;
- return getSum(v * 2, tl, mid, l, r) + getSum(v * 2+1, mid, tr, l, r);
- }
- void addRange(int v, int tl, int tr, int l, int r, int value) {
- if (r <= tl || l >= tr)
- return;
- if (tl >= l && tr <= r) {
- add[v] += value;
- return;
- }
- int mid = tl + (tr - tl) / 2;
- addRange(v * 2, tl, mid, l, r, value);
- addRange(v * 2 + 1, mid, tr, l, r, value);
- }
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(NULL);
- cout.tie(NULL);
- //cout << fixed << setprecision(5);
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- #else
- //freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- #endif // !DEBUG
- //setlocale(LC_ALL, "Russian");
- //18:42
- //19:00
- int n;
- cin >> n;
- k = 1;
- while (k < n)
- k *= 2;
- tree.resize(4*n+1, 0);
- add.resize(4 * n + 1, 0);
- vector<int> vc(n);
- for (int i = 0; i < n; i++) {
- cin >> vc[i];
- insert(i, vc[i]);
- }
- for (int i = 0; i < n * 4; i++) {
- cout << tree[i] << ' ';
- }
- cout << '\n';
- for (int i = 0; i < n; i++)
- cout << getSum(1, 0, k, i, i + 1) << ' ';
- cout << '\n';
- addRange(1, 0, k, 1, n, 2);
- addRange(1, 0, k, 1, n-1, 1);
- for (int i = 0; i < n; i++)
- cout << getSum(1, 0, k, i, i + 1) << ' ';
- cout << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement