传送门

题意是说有一些方块堆积起来的积木。有两种操作。

1 x y 是把第x行从下数第y个方块往左推一个。这会导致有一些方块悬空，这些悬空的方块会受到重力的影响下落。如果可以移动输出移动的方块数量。

2 x 是输出第x列的方块数量。

根据样例分析。

1. X往左走一格，可以看作X和X+1之间插入了一个(y-1)的数。
2. L是X左边第一个小于y的数，假设L的是第rank个，那么R就是第rank+2个。L和R之间那个数删掉即可。
3. L会加上前面那个柱子里掉下来的一些方块。

具体来说，先找到排名x的点X，排名x+1的点XX，把X Splay到根，再把XX Splay到X下面，在XX的左儿子插入一个(y-1)。

找到X以前的第一个小于y的点，根据size求出它的排名rank，顺便求出排名rank+1的D，R的排名rank+2，求出点R，把L Splay到根，R Splay到L下面，删掉L的右儿子。

最后把L补上掉下来的数，也就是加D.val-y+1

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 4e5 + 233;

struct Node{
    int s[2], p, sz;
    ll v, mv, sum;
    void init(int _v, int _p)
    {
        s[0] = s[1] = 0;
        v = _v, p = _p; 
        sz = 1, mv = sum = v;
    }
}tr[N];
int root, idx;
ll w[N];
void pushup(int x)
{
    tr[x].sz = tr[tr[x].s[0]].sz + tr[tr[x].s[1]].sz + 1;
    tr[x].sum = tr[tr[x].s[0]].sum + tr[tr[x].s[1]].sum + tr[x].v;
    tr[x].mv = min(min(tr[tr[x].s[0]].mv, tr[tr[x].s[1]].mv), tr[x].v);
}
void rotate(int x)
{
    int y = tr[x].p, z = tr[y].p;
    int k = tr[y].s[1] == x;
    tr[z].s[tr[z].s[1] == y] = x; tr[x].p = z;
    tr[y].s[k] = tr[x].s[k ^ 1]; tr[tr[x].s[k ^ 1]].p = y;
    tr[x].s[k ^ 1] = y; tr[y].p = x;
    pushup(y), pushup(x);
}
void splay(int x, int k = 0)
{
    while(tr[x].p != k)
    {
        int y = tr[x].p, z = tr[y].p;
        if(z != k)
            if((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
            else rotate(y);
        rotate(x);
    }
    if(!k) root = x;
}
int get_pre(int v, int x)
{
    int u = tr[x].s[0];
    while(u)
    {
        if(tr[tr[u].s[1]].mv < v) u = tr[u].s[1];
        else if(tr[u].v < v) return u;
        else u = tr[u].s[0];
    }
    return -1;
}
int get_k(int k)
{
    int u = root, p = 0;
    while(u)
    {
        if(tr[tr[u].s[0]].sz >= k) u = tr[u].s[0];
        else if(tr[tr[u].s[0]].sz + 1 == k) return u;
        else k -= tr[tr[u].s[0]].sz + 1, u = tr[u].s[1];
    }
    return -1;
}
int build(int l, int r, int p)
{
    int mid = l + r >> 1;
    int u = ++idx;
    tr[u].init(w[mid], p);
    if(l < mid) tr[u].s[0] = build(l, mid - 1, u);
    if(r > mid) tr[u].s[1] = build(mid + 1, r, u);
    pushup(u);
    return u;
}
void output(int x)
{
    if(tr[x].s[0]) output(tr[x].s[0]);
    if(tr[x].v != 1e17) printf("%d ", tr[x].v);
    if(tr[x].s[1]) output(tr[x].s[1]);
}
int main()
{
    // time_t startt = clock();
    // freopen("G.in", "r", stdin);
    // freopen("r.txt", "w", stdout);
    int T; scanf("%d", &T);
    while(T--)
    {
        int n, q; scanf("%d%d", &n, &q);
        for(int i = 1; i <= n; i++) scanf("%d", &w[i]);
        w[0] = w[n + 1] = 1e17;
        tr[0].mv = 1e17;
        idx = 0;
        root = build(0, n + 1, 0);
        int op, x, y;
        while(q--)
        {
            scanf("%d", &op);
            if(op == 1)
            {
                scanf("%d%d", &x, &y);
                x ++;
                int X = get_k(x);
                splay(X);
                if(tr[X].v < y || tr[tr[X].s[0]].mv >= y) {printf("0\n"); continue;}
                int L = get_pre(y, X);
                splay(L, X);
                ll sum = tr[tr[L].s[1]].sum + tr[X].v, size = tr[tr[L].s[1]].sz + 1;
                printf("%lld\n", sum - (y - 1) * size);
                int XX = get_k(x + 1);
                splay(X), splay(XX, X);
                int u = ++idx;
                tr[XX].s[0] = u;
                tr[u].init(y - 1, XX);
                pushup(XX), pushup(X);
                int rank = tr[tr[L].s[0]].sz + 1;
                int D = get_k(rank + 1);
                int h = tr[D].v - y + 1;
                int R = get_k(rank + 2);
                splay(L), splay(R, L);
                tr[R].s[0] = 0;
                pushup(R), pushup(L);
                tr[L].v += h;
                pushup(R), pushup(L);
            }
            else 
            {
                scanf("%d", &x);
                x++;
                int X = get_k(x);
                splay(X);
                printf("%lld\n", tr[X].v);
            }
            // output(root); printf("\n");
        }
        // output(root); printf("\n");
        for(int i = 2; i <= n + 1; i++) 
        {
            int O = get_k(i);
            splay(O);
            printf("%lld%c", tr[O].v, " \n"[i == n + 1]);
        }
    }
    // cerr << "~ #" << " done! time : " << (double)(clock()-startt) << " ms" << endl;
    // cerr << "~ #" << " done! time : " << (double)(clock()-startt)/CLOCKS_PER_SEC << " s" << endl;
}
/*
2
8 5
2 1 1 4 4 6 2 3
1 6 4
2 5
1 1 1
1 8 2
2 2

8 4
2 1 1 4 4 6 2 3
1 6 4
2 5
1 1 1
1 8 2

*/