1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
#include <iostream>
#include <vector>
using namespace std;

#define MAXA 1000000
#define LL long long
struct Fit {
    int n;
    vector<LL> fenw;
    Fit(int n) : n(n), fenw(n+1, 0) {}
    void update(int i, LL delta) {
        for(; i <= n; i += i & -i)
            fenw[i] += delta;
    }
    LL query(int i) {
        LL s = 0;
        for(; i; i -= i & -i)
            s += fenw[i];
        return s;
    }
};

struct Node {
    int cnt;
    Node *left, *right;
    Node(int cnt, Node* left, Node* right) : cnt(cnt), left(left), right(right) {}
};

Node* build(int l, int r) {
    if(l == r)
        return new Node(0, nullptr, nullptr);
    int mid = (l + r) / 2;
    return new Node(0, build(l, mid), build(mid+1, r));
}

Node* update(Node* prev, int l, int r, int pos) {
    if(l == r)
        return new Node(prev->cnt + 1, nullptr, nullptr);
    int mid = (l + r) / 2;
    if(pos <= mid)
        return new Node(prev->cnt + 1, update(prev->left, l, mid, pos), prev->right);
    else
        return new Node(prev->cnt + 1, prev->left, update(prev->right, mid+1, r, pos));
}

int query(Node* node, int l, int r, int ql, int qr) {
    if(!node || ql > r || qr < l)
        return 0;
    if(ql <= l && r <= qr)
        return node->cnt;
    int mid = (l + r) / 2;
    return query(node->left, l, mid, ql, qr) + query(node->right, mid+1, r, ql, qr);
}

int main(){
    int n, m, z;
    cin >> n >> m >> z;
    vector<int> a(n+1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    vector<Node*> roots(n+1);
    roots[0] = build(1, MAXA);
    for (int i = 1; i <= n; i++){
        roots[i] = update(roots[i-1], 1, MAXA, a[i]);
    }

    auto H = [&](int x, int d) -> int {
        if(x <= 0) return 0;
        return query(roots[x], 1, MAXA, 1, d-1);
    };

    Fit fenw1(n), fenw2(n);

    vector<pair<int,int>> modifications;
    int totalEvents = m + z;
    for (int e = 0; e < totalEvents; e++){
        int t;
        cin >> t;
        if(t == 1){
            int p, w;
            cin >> p >> w;
            fenw1.update(p, w);
            fenw2.update(p, (LL)w * p);
            modifications.push_back({p, w});
        } else {
            int p, d;
            cin >> p >> d;
            LL total_w = fenw1.query(n);
            LL left_w = fenw1.query(p - 1);
            LL A_val = fenw2.query(p - 1);

            LL S_total = (LL)p * (total_w - left_w) + A_val;


            LL part1 = (total_w - left_w) * H(p, d);
            LL part2 = 0;
            for(auto &mod : modifications){
                if(mod.first < p)
                    part2 += (LL)mod.second * H(mod.first, d);
            }
            LL S_bad = part1 + part2;

            LL ans = S_total - S_bad;
            cout << ans << endl;
        }
    }
    return 0;
}