Submission #70975710

---

Source Code Expand

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
using namespace std;

// #include <atcoder/all>
// using namespace atcoder;

using ll = long long;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)

const ll dy[] = {-1, 0, 0, 1};
const ll dx[] = {0, -1, 1, 0};

template <class T, class T1, class T2> bool isrange(T target, T1 low, T2 high) { return low <= target && target < high; }
template <class T, class U> T min(const T &t, const U &u) { return t < u ? t : u; }
template <class T, class U> T max(const T &t, const U &u) { return t < u ? u : t; }
template <class T, class U> bool chmin(T &t, const U &u) { if (t > u) { t = u; return true; } return false; }
template <class T, class U> bool chmax(T &t, const U &u) { if (t < u) { t = u; return true; } return false; }

// #include "titan_cpplib/others/print.cpp"

#include <iostream>
#include <vector>
#include <set>
#include <tuple>
#include <unordered_set>
#include <algorithm>
#include <map>
#include <unordered_map>
using namespace std;

// print

// -------------------------
// pair<K, V>
template<typename K, typename V> ostream& operator<<(ostream& os, const pair<K, V>& p);
// tuple<T1, T2, T3>
template<typename T1, typename T2, typename T3> ostream &operator<<(ostream &os, const tuple<T1, T2, T3> &t);
// tuple<T1, T2, T3, T4>
template<typename T1, typename T2, typename T3, typename T4> ostream &operator<<(ostream &os, const tuple<T1, T2, T3, T4> &t);
// vector<T>
template<typename T> ostream& operator<<(ostream& os, const vector<T>& a);
// vector<vector<T>>
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& a);
// array<T, 2>
template<typename T> ostream& operator<<(ostream& os, const array<T, 2>& a);
// set<T>
template<typename T> ostream& operator<<(ostream& os, const set<T>& s);
// multiset<T>
template<typename T> ostream& operator<<(ostream& os, const multiset<T>& s);
// unordered_set<T>
template<typename T> ostream& operator<<(ostream& os, const unordered_set<T>& a);
// map<K, V>
template<typename K, typename V> ostream& operator<<(ostream& os, const map<K, V>& mp);
// unordered_map<K, V>
template<typename K, typename V> ostream& operator<<(ostream& os, const unordered_map<K, V>& mp);
// -------------------------

// color
static const string PRINT_RED = "\033[91m"; // 赤字
static const string PRINT_GREEN = "\033[92m"; // 緑字
static const string PRINT_BLUE = "\033[94m";  // 青字
static const string PRINT_NONE = "\033[m"; // 色を元に戻す
static const string PRINT_BOLD = "\u001b[1m"; // 太字

string to_red(const string &s)   { return PRINT_RED + s + PRINT_NONE; }
string to_green(const string &s) { return PRINT_GREEN + s + PRINT_NONE; }
string to_blue(const string &s)  { return PRINT_BLUE + s + PRINT_NONE; }
string to_bold(const string &s)  { return PRINT_BOLD + s + PRINT_NONE; }

string spacefill(const string s, const int f) {
    int n = s.size();
    string t;
    for (int i = 0; i < f-n; ++i) t += " ";
    t += s;
    return t;
}

string zfill(const string s, const int f) {
    int n = s.size();
    string t;
    for (int i = 0; i < f-n; ++i) t += "0";
    t += s;
    return t;
}

string bin(long long s) {
    string t;
    while (s) {
        t += (s & 1) ? '1' : '0';
        s >>= 1;
    }
    reverse(t.begin(), t.end());
    return t;
}

void DEBUG_LINE() { cerr << "[Line] : " << __LINE__ << std::endl; }

// pair<K, V>
template<typename K, typename V>
ostream& operator<<(ostream& os, const pair<K, V>& p) {
    os << "(" << p.first << ", " << p.second << ")";
    return os;
}

// tuple<T1, T2, T3>
template<typename T1, typename T2, typename T3>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3> &t) {
    os << "(" << get<0>(t) << ", " << get<1>(t) << ", " << get<2>(t) << ")";
    return os;
}

// tuple<T1, T2, T3, T4>
template<typename T1, typename T2, typename T3, typename T4>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3, T4> &t) {
    os << "(" << get<0>(t) << ", " << get<1>(t) << ", " << get<2>(t) << ", " << get<3>(t) << ")";
    return os;
}

// array<T, 2>
template<typename T>
ostream& operator<<(ostream& os, const array<T, 2>& a) {
    os << "[";
    for (int i = 0; i < (int)a.size(); ++i) {
        if (i > 0) os << ", ";
        os << a[i];
    }
    os << "]";
    return os;
}

// vector<T>
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& a) {
    os << "[";
    for (int i = 0; i < (int)a.size(); ++i) {
        if (i > 0) os << ", ";
        os << a[i];
    }
    os << "]";
    return os;
}

// vector<vector<T>>
template<typename T>
ostream& operator<<(ostream& os, const vector<vector<T>>& a) {
    os << "[\n";
    int h = (int)a.size();
    for (int i = 0; i < h; ++i) {
        os << "  " << a[i] << '\n';
    }
    os << "]";
    return os;
}

// set<T>
template<typename T>
ostream& operator<<(ostream& os, const set<T>& s) {
    os << "{";
    auto it = s.begin();
    while (it != s.end()) {
        os << *it;
        ++it;
        if (it != s.end()) {
            os << ", ";
        }
    }
    os << "}";
    return os;
}

// multiset<T>
template<typename T>
ostream& operator<<(ostream& os, const multiset<T>& s) {
    os << "{";
    auto it = s.begin();
    while (it != s.end()) {
        os << *it;
        ++it;
        if (it != s.end()) {
            os << ", ";
        }
    }
    os << "}";
    return os;
}

// unordered_set<T>
template<typename T>
ostream& operator<<(ostream& os, const unordered_set<T>& a) {
    set<T> s(a.begin(), a.end());
    os << s;
    return os;
}

// map<K, V>
template<typename K, typename V>
ostream& operator<<(ostream& os, const map<K, V>& mp) {
    os << "{";
    auto it = mp.begin();
    while (it != mp.end()) {
        os << it->first << ": " << it->second;
        ++it;
        if (it != mp.end()) {
            os << ", ";
        }
    }
    os << "}";
    return os;
}

// unordered_map<K, V>
template<typename K, typename V>
ostream& operator<<(ostream& os, const unordered_map<K, V>& mp) {
    map<K, V> m(mp.begin(), mp.end());
    os << m;
    return os;
}

// #include "titan_cpplib/data_structures/segment_tree.cpp"
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;

namespace titan23 {

template <class T, T (*op)(T, T), T (*e)()>
class SegmentTree {
private:
    int n, _size, _log;
    vector<T> data;

    int bit_length(const int x) const {
        if (x == 0) return 0;
        return 32 - __builtin_clz(x);
    }

public:
    SegmentTree() {}

    SegmentTree(const int n) {
        _build(n);
    }

    SegmentTree(const vector<T> &a) {
        int n = (int)a.size();
        _build(n);
        for (int i = 0; i < n; ++i) {
            data[i+_size] = a[i];
        }
        for (int i = _size-1; i > 0; --i) {
            data[i] = op(data[i<<1], data[i<<1|1]);
        }
    }

    void _build(const int n) {
        this->n = n;
        this->_log = bit_length(n);
        this->_size = 1 << _log;
        this->data.resize(this->_size*2, e());
    }

    T get(int const k) const {
        return data[k+_size];
    }

    void set(int k, const T v) {
        assert(0 <= k && k < n);
        k += _size;
        data[k] = v;
        for (int i = 0; i < _log; ++i) {
            k >>= 1;
            data[k] = op(data[k<<1], data[k<<1|1]);
        }
    }

    T prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= n);
        l += _size;
        r += _size;
        T lres = e(), rres = e();
        while (l < r) {
            if (l & 1) lres = op(lres, data[l++]);
            if (r & 1) rres = op(data[r^1], rres);
            l >>= 1;
            r >>= 1;
        }
        return op(lres, rres);
    }

    T all_prod() const {
        return data[1];
    }

    template<typename F>  // F: function<bool (T)> f
    int max_right(int l, F &&f) const {
        assert(0 <= l && l <= _size);
        // assert(f(e()));
        if (l == n) return n;
        l += _size;
        T s = e();
        while (1) {
            while ((l & 1) == 0) {
                l >>= 1;
            }
            if (!f(op(s, data[l]))) {
                while (l < _size) {
                    l <<= 1;
                    if (f(op(s, data[l]))) {
                        s = op(s, data[l]);
                        l |= 1;
                    }
                }
                return l - _size;
            }
            s = op(s, data[l]);
            ++l;
            if ((l & (-l)) == l) break;
        }
        return n;
    }

    template<typename F>  // F: function<bool (T)> f
    int min_left(int r, F &&f) const {
        assert(0 <= r && r <= n);
        // assert(f(e()));
        if (r == 0) return 0;
        r += _size;
        T s = e();
        while (r > 0) {
            --r;
            while (r > 1 && (r & 1)) {
                r >>= 1;
            }
            if (!f(op(data[r], s))) {
                while (r < _size) {
                    r = (r << 1) | 1;
                    if (f(op(data[r], s))) {
                        s = op(data[r], s);
                        r ^= 1;
                    }
                }
                return r + 1 - _size;
            }
            s = op(data[r], s);
            if ((r & (-r)) == r) break;
        }
        return 0;
    }

    vector<T> tovector() const {
        vector<T> res(n);
        for (int i = 0; i < n; ++i) {
            res[i] = get(i);
        }
        return res;
    }

    void print() const {
        cout << '[';
        for (int i = 0; i < n-1; ++i) {
            cout << get(i) << ", ";
        }
        if (n > 0) cout << get(n-1);
        cout << ']' << endl;
    }
};
}  // namespace titan23



ll op(ll s, ll t) { return s + t; }
ll e() { return 0; }


void solve() {
    int n, q; cin >> n >> q;
    vector<ll> A(n);
    const int M = 5e5+10;
    vector<ll> init(5e5+10);
    titan23::SegmentTree<ll, op, e> seg(init), seg2(init);
    rep(i, n) {
        cin >> A[i];
        seg.set(A[i], seg.get(A[i])+A[i]);
        seg2.set(A[i], seg2.get(A[i])+1);
    }
    rep(i, q) {
        int t, x, y; cin >> t >> x >> y;
        if (t == 1) {
            x--;
            seg.set(A[x], seg.get(A[x])-A[x]);
            seg2.set(A[x], seg2.get(A[x])-1);
            A[x] = y;
            seg.set(A[x], seg.get(A[x])+A[x]);
            seg2.set(A[x], seg2.get(A[x])+1);
        } else {
            int l = x, r = y;
            if (l >= r) {
                cout << (ll)l*n << endl;
                continue;
            }
            ll ans = seg.prod(l, r);
            int lt = seg2.prod(0, l);
            int gt = seg2.prod(r, M);
            ans += (ll)l * lt;
            ans += (ll)r * gt;
            cout << ans << endl;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(15);
    cerr << fixed << setprecision(15);

    int t = 1;
    // cin >> t;
    for (int i = 0; i < t; ++i) {
        solve();
    }

    return 0;
}

Submission Info

Judge Result