Editorial for Bedao Mini Contest 05 - BUILDING


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Code mẫu

#include <bits/stdc++.h>

using namespace std;
const string filename = "BUILDING";

#define int long long

int n, q;
int a[100001], b[100001];

int BIT[100001];

void upd(int x, int val)
{
    for(;x <= 100000; x += x & (-x))
        BIT[x] += val;
}

int query(int x)
{
    int ans = 0;
    for(;x > 0; x -= x & (-x))
        ans += BIT[x];
    return ans;             
}

int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    freopen( (filename + ".inp").c_str(), "r", stdin);
    freopen( (filename + ".out").c_str(), "w", stdout);

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n - 1; i++)
    {
        b[i] = abs(a[i + 1] - a[i]);
        upd(i, b[i]);
    }   
    cin >> q;   
    while (q--)
    {
        int t;
        cin >> t;
        if (t == 1)
        {
            int p, x;
            cin >> p >> x;
            a[p] = x;
            if (p > 1)
            {
                upd(p - 1, -b[p - 1]);
                b[p - 1] = abs(a[p] - a[p - 1]);
                upd(p - 1, b[p - 1]);
            }
            if (p < n)
            {
                upd(p, -b[p]);
                b[p] = abs(a[p + 1] - a[p]);
                upd(p, b[p]);
            }   
        }
        else
        {
            int l, r;
            cin >> l >> r;
            cout << query(r - 1) - query(l - 1) << ' ';
        }
    }
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.