Submission #74962773

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template <typename T>
using ordered_set = tree<
    T,                                 // key type
    null_type,                         // mapped type (null for set)
    less<T>,                           // ordering
    rb_tree_tag,                       // underlying tree
    tree_order_statistics_node_update> // enable order-statistics
    ;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<string> vs;

template <typename T>
void debug(const vector<T> &x)
{
    for (const auto &elem : x)
    {
        cout << elem << ' ';
    }
    cout << endl;
}

// =================== CONSTANTS ====================
const ll MOD = 1000000007;
const ll mod9 = 998244353;
const ll INF = numeric_limits<int>::max();

// =================== MACROS ======================
#define fast_cin()                    \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define fr(i, a, b) for (ll i = (a); i < (b); ++i)
#define fo(i, n) for (ll i = (0); i < (n); ++i)
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()

// ================= QUERY FUNCTION =================
ll query(ll a, ll b)
{
    cout << "? " << a << " " << b << endl;
    cout.flush();
    ll x;
    cin >> x;
    return x;
}

struct SegmentTree
{
    vector<ll> lazy, base;
    int n;

    SegmentTree(int size)
    {
        n = size;
        lazy.assign(4 * n, 0);
        base.assign(n, 0);
    }

    SegmentTree(const vector<ll> &arr)
    {
        n = arr.size();
        lazy.assign(4 * n, 0);
        base = arr;
    }

    void update(int node, int start, int end, int l, int r, ll val)
    {
        if (r < start || end < l)
            return;

        if (l <= start && end <= r)
        {
            lazy[node] += val;
            return;
        }

        int mid = (start + end) / 2;
        update(2 * node + 1, start, mid, l, r, val);
        update(2 * node + 2, mid + 1, end, l, r, val);
    }

    ll query(int node, int start, int end, int idx)
    {
        if (start == end)
            return base[idx] + lazy[node];

        int mid = (start + end) / 2;

        if (idx <= mid)
            return lazy[node] + query(2 * node + 1, start, mid, idx);
        else
            return lazy[node] + query(2 * node + 2, mid + 1, end, idx);
    }
};

// ========================================================
ll fast_pow(ll base, ll exp, ll mod = MOD)
{
    ll res = 1;
    while (exp > 0)
    {
        if (exp % 2 == 1)
            res = (res * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}

vector<bool> is_prime;
void sieve(int n)
{
    is_prime.assign(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= n; i++)
    {
        if (is_prime[i])
        {
            for (int j = i * i; j <= n; j += i)
            {
                is_prime[j] = false;
            }
        }
    }
}

void dfs(ll i, ll par, vvll &adj, vll &vis)
{
    vis[i] = 1;
    for (auto &ne : adj[i])
    {
        if (ne != par)
        {
            dfs(ne, i, adj, vis);
        }
    }
}

void solve()
{
    ll n, q;
    cin >> n >> q;
    vll ar(n);
    fo(i, n)
    {
        cin >> ar[i];
    }
    SegmentTree seg(ar);

    while (q--)
    {
        ll typ;
        cin >> typ;
        if (typ == 1)
        {
            ll l, r, x;
            std::cin >> l >> r >> x;
            --l;
            --r;
            seg.update(0, 0, n - 1, l, r, x);
        }
        else
        {
            ll i;
            cin >> i;
            --i;
            cout << seg.query(0, 0, n - 1, i)<<'\n';
        }
    }
}

int main()
{
    fast_cin();
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

Submission Info

Judge Result