LightOJ 1112 Solution

Curious Robin Hood Solution

#include<bits/stdc++.h>

#define mx 100010

#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

vector<int>a(mx), tree(mx*3);

void initialize(int node, int s, int e)

{

    if(s == e)

    {

        tree[node] = a[s];

        return;

    }

    int left = node*2;

    int right = node*2+1;

    int mid = (s+e)/2;

    initialize(left, s, mid);

    initialize(right, mid+1, e);

    tree[node] = tree[left] + tree[right];

}

int query(int node, int s, int e, int i, int j)

{

    if(i>e || j<s)

        return 0;

    if(s>=i && e<=j)

        return tree[node];

    int left = node*2;

    int right = node*2+1;

    int mid = (s+e)/2;

    int r1 = query(left, s, mid, i, j);

    int r2 = query(right, mid+1, e, i, j);

    return (r1+r2);

}

void update(int node, int s, int e, int i, int x)

{

    if(i>e || i<s)

        return;

    if(s>=i && e<=i)

    {

        tree[node] = x;

        return;

    }

    int left = node*2;

    int right = node*2+1;

    int mid = (s+e)/2;

    update(left, s, mid, i, x);

    update(right, mid+1, e, i, x);

    tree[node] = tree[left] + tree[right];

}

int main()

{

    fast

    int t, x = 1;

    cin >> t;

    while(t--)

    {

        int n, q;

        cin >> n >> q;

        for(int i=1; i<=n; i++)

            cin >> a[i];

        initialize(1, 1, n);

        cout << "Case " << x++ << ":\n";

        int i, j, k;

        while(q--)

        {

            cin >> i;

            if(i == 1)

            {

                cin >> j;

                j++;

                cout << a[j] << "\n";

                a[j] = 0;

                update(1, 1, n, j, 0);

            }

            else if(i == 2)

            {

                cin >> j >> k;

                j++;

                a[j] += k;

                update(1, 1, n, j, a[j]);

            }

            else

            {

                cin >> j >> k;

                j++, k++;

                cout << query(1, 1, n, j, k) << "\n";

            }

        }

        a.clear();

        tree.clear();

    }

    return 0;

}