Computers are fast nowadays, so we can solve this problem in $O(nq)$.

预处理出所有可能用到的幂次方，直接暴力做即可。因为常数小数据水，直接就能 $0.4 \text{s}$ 多一点，加个火车头 $0.26 \text{s}$，时间空间码量都吊打平衡树。

#include<bits/stdc++.h>
using namespace std;
signed n, q;
unsigned a[200005], pw[12][200005];
void ini(){
    for (int i = 1; i <= 200000; i++)
        pw[0][i] = 1;
    for (int i = 1; i <= 10; i++)
        for (int j = 1; j <= 200000; j++)
            pw[i][j] = pw[i - 1][j] * j;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    ini();
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    cin >> q;
    while (q--){
        int op;
        cin >> op;
        if (op == 1){
            int p;
            unsigned v;
            cin >> p >> v;
            ++p, ++n;
            memmove(a + p + 1, a + p, (n - p) * sizeof(unsigned));
            a[p] = v;
        }else if (op == 2){
            int p;
            cin >> p;
            ++p;
            memmove(a + p, a + p + 1, (n - p) * sizeof(unsigned));
            --n;
        }else if (op == 3){
            int p;
            unsigned v;
            cin >> p >> v;
            ++p;
            a[p] = v;
        }else{
            int l, r, k;
            cin >> l >> r >> k;
            ++l, ++r;
            unsigned ans = 0;
            for (int i = l; i <= r; i++)
                ans += a[i] * pw[k][i - l + 1];
            cout << ans << "\n";
        }
    }
    return 0;
}