ACM-ICPC 2018 徐州赛区网络预赛 Ryuji doesn't want to study

简单数学变换+线段树

简单数据结构签到题不解释

本来应该贴板子的，鉴于最近写代码太少了，而且由于要用两个线段树，平时板子都是一个的。以及板子在队友那。就当熟悉写代码，自己写了一下。

#include <bits/stdc++.h>

using namespace std;

#define dual(i, n) (n) + 1 - (i)

typedef long long ll;

int n, q;

const int maxn = 1e+5 + 5;

typedef ll arr[maxn];

arr a, pa;

struct seg_tree

{

    // a,nds坐标都是从1开始记

    ll *a;

    int n;

    struct nd

    {

        ll sum;

    };

    vector<nd> nds;

    seg_tree(ll *a0, int n0)

    {

        a = a0;

        n = n0;

        nds.resize(4 * n);

        build(1, 1, n);

    }

    void build(int i, int l, int r)

    {

        if (l == r)

        {

            nds[i].sum = a[l];

            return;

        }

        int m = l + (r - l) / 2;

        build(2 * i, l, m);

        build(2 * i + 1, m + 1, r);

        nds[i].sum = nds[2 * i].sum + nds[2 * i + 1].sum;

    }

    void change(int i, ll x)

    {

        ll delta = x - a[i];

        a[i] = x;

        add(i, delta);

    }

    void add(int i, ll x)

    {

        int l = 1;

        int r = n;

        int u = 1;

        int m;

        while (true)

        {

            nds[u].sum += x;

            if (l == r)

                break;

            m = l + (r - l) / 2;

            if (i <= m)

            {

                r = m;

                u = 2 * u;

            }

            else

            {

                l = m + 1;

                u = 2 * u + 1;

            }

        }

    }

    ll query(int l, int r, int u, int ul, int ur)

    {

        // ensure ul<=l<=r<=ur

        if (ul == l && r == ur)

            return nds[u].sum;

        int um = ul + (ur - ul) / 2;

        if (r <= um) // left

            return query(l, r, 2 * u, ul, um);

        else if (l >= um + 1) // right

            return query(l, r, 2 * u + 1, um + 1, ur);

        else

            return query(l, um, 2 * u, ul, um)                // left

                   + query(um + 1, r, 2 * u + 1, um + 1, ur); // right

    }

    inline ll query(int l,int r) {

        return query(l,r,1,1,n);

    }

};

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);

    cin >> n >> q;

    for (int i = n; i >= 1; --i)

    {

        cin >> a[i];

        pa[i] = a[i] * i;

    }

    seg_tree s(a, n);

    seg_tree ps(pa, n);

    int t, l, r, k;

    ll x, px;

    for (int i = 0; i < q; ++i)

    {

        cin >> t;

        if (1 == t)

        {

            // query

            cin >> r >> l;

            l = dual(l, n);

            r = dual(r, n);

            cout << ps.query(l, r) - (ll)(l - 1) * s.query(l, r) << "\n";

        }

        else

        {

            // a[k] = x

            cin >> k >> x;

            k = dual(k, n);

            px = x * k;

            s.change(k, x);

            ps.change(k, px);

        }

    }

    cout.flush();

    return 0;

}

巴特西

ACM-ICPC 2018 徐州赛区网络预赛 Ryuji doesn't want to study

最新文章

热门文章