题目描述

天空中出现了许多的北极光,这些北极光组成了一个长度为$n$的正整数数列$a[i]$。

远古之魔书上记载到:$2$个位置的$graze$值为两者位置差与数值差的和:

即$graze(x,y)=|x-y|+|a[x]-a[y]|$。

要想破解天罚,就必须支持$2$种操作($k$都是正整数):

$Modify\ x\ k$:将第$x$个数的值修改为$k$。

$Query\ x\ k$:询问有几个$i$满足$graze(x,i)\leq k$。

由于从前的天罚被圣王$lmc$破解了,所以$rhl$改进了她的法术。

询问不仅要考虑当前数列,还要考虑任意历史版本:

即统计任意位置上出现过的任意数值与当前的$a[x]$的$graze$值$<=k$的对数。

(某位置多次修改为同样的数值,按多次统计)

输入格式

第$1$行两个整数$n,m$。分别表示数列长度和操作数。

第$2$行$n$个正整数,代表初始数列。

第$3-m+2$行每行一个操作。

输出格式

对于每次询问操作,输出一个非负整数表示答案。

样例输入

3 5
2 4 3
Query 2 2
Modify 1 3
Query 2 2
Modify 1 2
Query 1 1

样例输出

2
3
3

数据范围

$N\leq40000$

修改操作数$\leq60000$, 询问操作数$\leq10000$

$Max{a[i]}$(含修改)$\leq80000$

菜鸡的咆哮

前置知识:

①曼哈顿距离:两点横纵坐标差的绝对值之和。

即$dis=|x1−x2|+|y1−y2|$。

②切比雪夫距离:

即$dis=max(|x1−x2|,|y1−y2|)$。

将一个点$(x,y)$的坐标变为$(x+y,x-y)$后,

原坐标系中的曼哈顿距离$=$新坐标系中的切比雪夫距离。

将一个点$(x,y)$的坐标变为$(\frac{x+y}{2},\frac{x-y}{2})$后,

原坐标系中的切比雪夫距离$=$新坐标系中的曼哈顿距离。


考虑将序列中的每个数抽象为一个点。

横坐标为下标,纵坐标为数值。

$graze(x,y)\leq k$等效于点$x$和点$y$的曼哈顿距离$\leq k$。

如果用曼哈顿距离进行计算,合法点存在的范围是一个菱形。

利用曼哈顿距离与切比雪夫距离的转化可以将其变为一个矩形。

具体的说,将每个点的坐标转化为$(x+y,x-y)$的形式。

对于点(x,y),关于其合法点的坐标$(x',y’)$满足:

$$ |x-x'|\leq k\ \ \ \ \ \ \ |y-y'|\leq k $$

去掉绝对值移向得:

$$ x-k\leq x'\leq x+k\ \ \ \ \ y-k\leq y'\leq y+k $$

所以合法点一定在以$(x-k,y-k)$为左下端点,$(x+k,y+k)$为右上端点的矩形中。

至此原问题转化为三维偏序,第一维操作时间,第二位$x$坐标,第三维$y$坐标。

一维$sort$,二维$CDQ$,三维树状数组离线完成。

注意存在负下标的情况,整体偏移即可。

代码

#include<bits/stdc++.h>
#define lowbit(x) ((x)&(-(x)))
#define maxn 1000005
#define fyj 100005
using namespace std;
int n,m;
int nowy[maxn];
//----------------------------------
struct data{
    int a,b,c;
    int opt,num,pos;
}f[maxn],t[maxn];
bool cmp(data x,data y){
    if(x.a!=y.a) return x.a<y.a;
    if(x.b!=y.b) return x.b<y.b;
    return x.c<y.c;
}
bool anscmp(data x,data y){
    return x.pos<y.pos;
}
//----------------------------------
int tree[maxn];
void update(int x,int dx){
    if(dx==0) return;
    while(x<=300000){
        tree[x]+=dx;
        x+=lowbit(x);
    }
}
int sum(int x){
    int ans=0;
    while(x>0){
        ans+=tree[x];
        x-=lowbit(x);
    }
    return ans;
}
//-----------------------------------
void CDQ(int l,int r){
    int mid=(l+r)>>1;
    if(l==r) return;
    CDQ(l,mid);CDQ(mid+1,r);
    int p=l,q=mid+1,tot=l;
    while(p<=mid&&q<=r){
        if(f[p].b<=f[q].b) update(f[p].c+fyj,f[p].opt),t[tot++]=f[p++];
        else f[q].num+=sum(f[q].c+fyj),t[tot++]=f[q++];
    } 
    while(p<=mid) update(f[p].c+fyj,f[p].opt),t[tot++]=f[p++];
    while(q<=r) f[q].num+=sum(f[q].c+fyj),t[tot++]=f[q++];
    for(int i=l;i<=mid;i++) update(f[i].c+fyj,-f[i].opt);
    for(int i=l;i<=r;i++) f[i]=t[i]; 
}
int cnt=0;
int ask_cnt=0;
int main(){
    //freopen("aurora.in","r",stdin);
    //freopen("aurora.out","w",stdout);
    scanf("%d%d",&n,&m);
    int xx;
    for(int i=1;i<=n;i++){
        scanf("%d",&xx);
        nowy[i]=xx;
        f[++cnt]=(data){i,i+xx,i-xx,1,0,0x3f3f3f3f};
    }
    char order[100];
    int x,y;
    for(int i=1;i<=m;i++){
        cin>>order>>x>>y;
        if(order[0]=='Q'){
            //当前点(x,nowy[x])
            //(x+nowy[x],x-nowy[x])
            //左下(x+nowy[x]-y,x-nowy[x]-y); 
            //右上(x+nowy[x]+y,x-nowy[x]+y)
            int lx=x+nowy[x]-y,ly=x-nowy[x]-y;
            int rx=x+nowy[x]+y,ry=x-nowy[x]+y;
            f[++cnt]=(data){n+i,rx,ry,0,0,++ask_cnt};
            f[++cnt]=(data){n+i,lx-1,ry,0,0,++ask_cnt};
            f[++cnt]=(data){n+i,rx,ly-1,0,0,++ask_cnt};
            f[++cnt]=(data){n+i,lx-1,ly-1,0,0,++ask_cnt};
        }
        else{
            f[++cnt]=(data){n+i,x+y,x-y,1,0,0x3f3f3f3f};
            nowy[x]=y;
        }
    }
    sort(f+1,f+1+cnt,cmp);
    CDQ(1,cnt);
    sort(f+1,f+1+cnt,anscmp);
    for(int i=1;i+3<=ask_cnt;i+=4){
        printf("%d\n",f[i].num-f[i+1].num-f[i+2].num+f[i+3].num);
    }
    return 0;
}