C++(clang++11) 解法, 执行用时: 694ms, 内存消耗: 3784K, 提交时间: 2020-12-13 00:06:16

#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5;
int n, q, p[N], rp[N];
int c[N];
void upd(int x, int v)
{
	for(int i=x; i<=n; i+=(i&-i)) c[i] += v;
}
int ask(int x)
{
	int ans = 0;
	for(int i=x; i>0; i-=(i&-i)) ans += c[i];
	return ans;
}
int rt;
int ch[N][2], sz[N], val[N], fa[N], id[N];
bool rs(int x) { return ch[fa[x]][1]==x; }
void up(int p) { if(p) sz[p] = sz[ch[p][0]] + sz[ch[p][1]] + 1; }
void bld(int l, int r, int f)
{
	if(l>r) return;
	int p = (l+r)>>1;
	sz[p] = 1;
	ch[p][0] = ch[p][1] = 0;
	if(p>=2&&p<=n+1)
	{
		val[p] = rp[p-1];
		id[rp[p-1]] = p;
	}
	fa[p] = f, ch[f][p>f] = p;
	if(l==r) return;
	bld(l, p-1, p); bld(p+1, r, p);
	up(p);
}
void rotate(int x)
{
    int y = fa[x], z = fa[y], k = rs(x), w = ch[x][k^1];
    ch[y][k] = w; fa[w] = y;
    ch[z][rs(y)] = x; fa[x] = z;
    ch[x][k^1] = y; fa[y] = x;
    up(y); up(x);
}
void splay(int x, int g=0)
{
    while(fa[x]!=g)
    {
        int y = fa[x];
        if(fa[y]!=g) (rs(x)==rs(y) ? rotate(y) : rotate(x));
        rotate(x);
    }
    if(!g) rt = x;
}
int kth(int p, int k)
{
    if(ch[p][0]&&sz[ch[p][0]]>=k) return kth(ch[p][0], k);
    else if(sz[ch[p][0]]+1==k) return p;
    else return kth(ch[p][1], k-sz[ch[p][0]]-1); 
}
int rnk(int p)
{
	splay(p);
	return sz[ch[p][0]] + 1;
}
void ins(int l, int r)
{
	int x = kth(rt, l-1), y = kth(rt, l+1);
	splay(x); splay(y, x);
	int z = ch[y][0];
	ch[y][0] = 0; fa[z] = 0;
	up(y); up(fa[y]);
	int x2 = kth(rt, r-1), y2 = kth(rt, r);
	splay(x2); splay(y2, x2);
	ch[y2][0] = z; fa[z] = y2;
	up(y2); up(fa[y2]);
}
void solve()
{
	scanf("%d", &n);
	for(int i=1; i<=n; i++) 
	{
		scanf("%d", p+i);
		rp[p[i]] = i;
	}
	scanf("%d", &q);
	int lim = n*0.6;
	for(int i=1; i<=n; i++) c[i] = 0;
	for(int i=lim+1; i<=n; i++) upd(rp[i], 1);
	bld(1, n+2, 0);
	rt = (n+3)>>1;
	while(q--)
	{
		int op, x, y; scanf("%d%d%d", &op, &x, &y);
		if(op==1)
		{
			if(y<=lim)
			{
				int rkx = rnk(id[x]) - 1;
				if(rkx>lim)
				{
					upd(x, -1);
					upd(val[kth(rt, lim+1)], 1);
				}
				ins(rkx+1, y+1);
			}
		}
		else printf("%d\n", ask(y)-ask(x-1));
	}
}
int main()
{
	int _; scanf("%d", &_);
	while(_--) solve();
	return 0;
}