基本思路

将坐标 $(a_i,i)$看作一个点，那么本题转化为每次资磁插入一个点，查询已插入的点中，离某个点的曼哈顿距离小于等于 $k$的点数。
曼哈顿距离转切比雪夫距离的套路，将坐标变成 $(a_i+i,a_i-i)$后，两点的距离变成 $max(|x_1-x_2|,|y_1-y_2|)$，那么查询一个矩形区域内的点数即可。如果是先一堆插入再一堆查询，那么按照 x 坐标建立主席树，每棵树内维护 y 坐标在某个区间的点有多少个即可。
问题是插入和查询是交错的，这怎么办呢？

What is 二进制分组 you may ask

对于每 $2^t$个插入的点归到一组，对每组建立 “一组” 主席树，然后查询时在所有主席树组里面查询即可。
具体方法是，假如插入了一个点，建立一个大小为 1 的组。
假如它与上一个组大小相同，将它与上一个组的主席树都暴力 ban 掉，然后重建一棵新的主席树。
譬如现在一些组大小是 16,4,2,1，我添加一个大小为 1 的组，然后不断合并：
16,4,2,1,1
16,4,2,2
16,4,4
16,8
发现每次的组数是 log 级别的，所以每一个点被合并的次数也是 log 级别的，所以复杂度就是 $O(nlog^2n)$的。

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}
const int N=160005,LIM=160000,M=1800005,Y=60000,inf=0x3f3f3f3f;
typedef pair<int,int> PR;
int n,Q,top,SZ,js;
struct node{int ls,rs,sz;}tr[M];
int a[N],rub[M],rt[20][N],vis[M];
vector<PR> OvO[20],kl;

int newnode() {
    int re;
    if(top) re=rub[top--];
    else re=++SZ;
    vis[re]=1;return re;
}
void ins(int &x,int y,int l,int r,int wz) {
    x=newnode(),tr[x]=tr[y],++tr[x].sz;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(wz<=mid) ins(tr[x].ls,tr[y].ls,l,mid,wz);
    else ins(tr[x].rs,tr[y].rs,mid+1,r,wz);
}
void del(int x) {
    if(!vis[x]) return;
    if(tr[x].ls) del(tr[x].ls);
    if(tr[x].rs) del(tr[x].rs);
    tr[x].ls=tr[x].rs=tr[x].sz=vis[x]=0,rub[++top]=x;
}
int query(int x,int y,int s,int t,int l,int r) {
    if(l<=s&&t<=r) return tr[y].sz-tr[x].sz;
    int mid=(s+t)>>1,re=0;
    if(l<=mid) re=query(tr[x].ls,tr[y].ls,s,mid,l,r);
    if(mid+1<=r) re+=query(tr[x].rs,tr[y].rs,mid+1,t,l,r);
    return re;
}

void work(int x,int y) {
    OvO[++js].push_back((PR){x,y});
    ins(rt[js][1],rt[js][0],1,LIM,y);
    while(js>1&&OvO[js].size()==OvO[js-1].size()) {
        kl.clear();int k1=0,k2=0,sz1=OvO[js].size(),sz2=OvO[js-1].size();
        for(RI i=1;i<=sz1;++i) del(rt[js][i]);
        for(RI i=1;i<=sz2;++i) del(rt[js-1][i]);
        for(RI i=1;i<=sz1+sz2;++i) {
            if(k2>=sz2||(k1<sz1&&OvO[js][k1]<OvO[js-1][k2]))
                kl.push_back(OvO[js][k1++]);
            else kl.push_back(OvO[js-1][k2++]);
            ins(rt[js-1][i],rt[js-1][i-1],1,LIM,kl[i-1].second);
        }
        OvO[js-1]=kl,OvO[js].clear(),--js;
    }
}
int getans(int x,int y,int k) {
    int re=0;
    for(RI i=1;i<=js;++i) {
        int k1=lower_bound(OvO[i].begin(),OvO[i].end(),(PR){x-k,0})-OvO[i].begin();
        int k2=lower_bound(OvO[i].begin(),OvO[i].end(),(PR){x+k,inf})-OvO[i].begin();
        re+=query(rt[i][k1],rt[i][k2],1,LIM,max(1,y-k),min(y+k,LIM));
    }
    return re;
}
int main()
{
    char ch[10];int x,y;
    n=read(),Q=read();
    for(RI i=1;i<=n;++i) a[i]=read(),work(a[i]+i,a[i]-i+Y);
    while(Q--) {
        scanf("%s",ch),x=read(),y=read();
        if(ch[0]=='M') a[x]=y,work(a[x]+x,a[x]-x+Y);
        else printf("%d\n",getans(a[x]+x,a[x]-x+Y,y));
    }
    return 0;
}