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
110
111
112
113
114
115
116
117
118
119
120
#include<bits/stdc++.h>
using namespace std;
#define int long long

void solve_1(int n, int m, int z){
    vector<int> a(n+1); // Jak daleko dochodzimy w dniu i
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    vector<int> v(n+1); // Ile zjadamy z każdego dnia w dniu i
    for(int i=0; i<m+z; i++){
        int type;
        cin >> type;
        if(type==1){
            int ile_dni, wartosc;
            cin >> ile_dni >> wartosc;
            for(int i=1; i<=ile_dni; i++){
                v[i]+=wartosc;
            }
        }
        if(type==2){
            int ile_dni, drzewo;
            cin >> ile_dni >> drzewo;
            int wynik=0;
            for(int i=1; i<=ile_dni; i++){
                if(a[i]>=drzewo) wynik+=v[i];
            }
            cout << wynik<<"\n";
        }
    }
}
struct seg_tree{
    vector<vector<int>> tab;
    int siz;
    seg_tree(vector<int> v){
        int n = v.size();
        siz = 1<<((int) ceil(log2(n)));
        tab.resize(2*siz);
        for(int i=0; i<n; i++){
            tab[siz+i].push_back(v[i]);
        }
        for(int i=siz-1; i>0; --i){
            auto it1 = tab[2*i].begin();
            auto it2 = tab[2*i+1].begin();
            while(it1!= tab[2*i].end() && it2!=tab[2*i+1].end()){
                if(*it1 < *it2){
                    tab[i].push_back(*it1);
                    it1++;
                }
                else{
                    tab[i].push_back(*it2);
                    it2++;
                }
            }
            while(it1!=tab[2*i].end()){
                tab[i].push_back(*it1);
                it1++;
            }
            while(it2!=tab[2*i+1].end()){
                tab[i].push_back(*it2);
                it2++;
            }
        }
    }

    int query(int val, int pref){ //Zwraca liczbę elementow na prefixie 0, 1, ..., pref, które są równe co najmniej val
        int wynik = 0;
        for(int l = siz, r = pref+siz+1; l<r; l/=2, r/=2){
            if(l&1){
                auto it = lower_bound(tab[l].begin(), tab[l].end(), val);
                wynik+=distance(it, tab[l].end());
                l++;
            }
            if(r&1){
                r--;
                auto it = lower_bound(tab[r].begin(), tab[r].end(), val);
                wynik+=distance(it, tab[r].end());
            }
        }
        return wynik;
    }
};
void solve_2(int n, int m, int z){
    vector<int> a(n+1);
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    seg_tree st(a);

    vector<int> ile_dni, wartosc;
    for(int i=0; i<m+z; i++){
        int type;
        cin >> type;
        if(type==1){
            int x, y;
            cin >> x >> y;
            ile_dni.push_back(x);
            wartosc.push_back(y);
        }
        if(type==2){
            int wynik=0;
            int dni_zap;
            int drzewo;
            cin >> dni_zap >> drzewo;
            for(int i=0; i<(int)ile_dni.size(); i++){
                wynik+=wartosc[i]*st.query(drzewo, min(dni_zap-1, ile_dni[i]-1));
            }
            cout << wynik<<"\n";
        }
    }
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, z;
    cin >> n >> m >> z;
    if(n*(m+z) <= 2e7) solve_1(n, m, z);
    else solve_2(n, m, z);
}