#include<bits/stdc++.h>

char buf[],*ptr=buf;

const int N=;

int _(){

    int x=;

    while(*ptr<)++ptr;

    while(*ptr>)x=x*+*ptr++-;

    return x;

}

struct itv{

    int l;

    mutable int r,x;

    bool operator<(const itv&w)const{return l<w.l;}

};

typedef std::set<itv>::iterator IT;

std::set<itv>c,cs[N*];

int n,m,v0[N],vs[N*],vp=;

int os[N][],pw[N*],pv[N];

struct P{

    int t,x,y,a;

    bool operator<(const P&w)const{return x<w.x;}

}ps[N*],qs[N*],pb[N*];

int px[N],qx[N];

int pp=,qp=,now,ans[N];

int bit[N][],tk=,c0;

void inc(int w,int a){

    if(!w)c0+=a;

    else for(;w<=n;w+=w&-w){

        bit[w][]!=tk?bit[w][]=tk,bit[w][]=:;

        bit[w][]+=a;

    }

}

int sum(int w){

    int s=c0;

    for(;w;w-=w&-w){

        s+=(bit[w][]==tk?bit[w][]:);

    }

    return s;

}

void clr(){

    ++tk,c0=;

}

void msort(P*l,P*m,P*r){

    P*bp=pb,*p1=l,*p2=m;

    while(p1!=m&&p2!=r)*bp++=*(p1->x<p2->x?p1:p2)++;

    while(p1!=m)*bp++=*p1++;

    while(p2!=r)*bp++=*p2++;

    memcpy(l,pb,(r-l)*sizeof(P));

}

void calc(int L,int R,int lp,int rp,int lq,int rq){

    if(L==R){

        std::sort(ps+lp,ps+rp);

        std::sort(qs+lq,qs+rq);

        return;

    }

    int M=(L+R)>>,mp=px[M],mq=qx[M];

    calc(L,M,lp,mp,lq,mq);

    calc(M+,R,mp,rp,mq,rq);

    if(lp<mp&&mq<rq){

        clr();

        for(int i=mq,j=lp;i<rq;++i){

            for(;j<mp&&ps[j].x<=qs[i].x;++j)inc(ps[j].y,ps[j].a);

            int z;

            ans[qs[i].t]+=z=sum(qs[i].y)*qs[i].a;

        }

    }

    msort(ps+lp,ps+mp,ps+rp);

    msort(qs+lq,qs+mq,qs+rq);

}

void setpv(int w,int v){

    if(pv[w]==v)return;

    ps[pp++]=(P){now,w,pv[w],-};

    pv[w]=v;

    ps[pp++]=(P){now,w,v,};

}

int getpv(int w,int x){

    IT it=cs[w].lower_bound((itv){x});

    if(it==cs[w].begin())return ;

    --it;

    return it->r>=x?x-:it->r;

}

void setq(int l,int r){

    qs[qp++]=(P){now,r,l-,};

    qs[qp++]=(P){now,l-,l-,-};

}

int xs[N],xp,cms[N],cp;

void modify(int l,int r,int x){

    IT it,it2,del;

    xp=cp=;

    it=c.upper_bound((itv){r});--it;

    if(it->r>r){

        cs[it->x].insert((itv){r+,it->r});

        cs[it->x].find(*it)->r=r;

        c.insert((itv){r+,it->r,it->x});

        it->r=r;

    }

    it=c.upper_bound((itv){l});--it;

    if(it->l<l){

        cs[it->x].insert((itv){l,it->r});

        cs[it->x].find(*it)->r=l-;

        c.insert((itv){l,it->r,it->x});

        it->r=l-;

    }

    for(it=c.find((itv){l});it!=c.end();it2=it,++it,c.erase(it2)){

        xs[xp++]=it->l;

        if(it->l>r)break;

        cms[cp++]=it->x;

        cs[it->x].erase(*it);

    }

    c.insert((itv){l,r,x});

    cs[x].insert((itv){l,r});

    for(int i=;i<xp;++i){

        int d=xs[i]-;

        if(xs[i]==l)d=getpv(x,xs[i]);

        else if(xs[i]>r)d=getpv(it->x,xs[i]);

        setpv(xs[i],d);

    }

    cms[cp++]=x;

    for(int i=;i<cp;++i){

        it=cs[cms[i]].upper_bound((itv){r});

        if(it!=cs[cms[i]].end()){

            setpv(it->l,getpv(cms[i],it->l));

        }

    }

}

int main(){

    fread(buf,,sizeof(buf),stdin);

    n=_();m=_();

    for(int i=;i<=n;++i)vs[vp++]=v0[i]=_();

    for(int i=;i<=m;++i){

        os[i][]=_();

        os[i][]=_();

        os[i][]=_();

        if(os[i][]==)vs[vp++]=os[i][]=_();

    }

    std::sort(vs,vs+vp);

    vp=std::unique(vs,vs+vp)-vs;

    for(int i=;i<=n;++i)v0[i]=std::lower_bound(vs,vs+vp,v0[i])-vs;

    for(int i=;i<=m;++i)os[i][]=std::lower_bound(vs,vs+vp,os[i][])-vs;

    for(int i=;i<=n;++i){

        cs[v0[i]].insert((itv){i,i});

        c.insert((itv){i,i,v0[i]});

        pv[i]=pw[v0[i]];

        ps[pp++]=(P){,i,pv[i],};

        pw[v0[i]]=i;

    }

    px[]=pp,qx[]=qp;

    for(int i=now=;i<=m;++now,++i){

        if(os[i][]==)modify(os[i][],os[i][],os[i][]);

        else setq(os[i][],os[i][]);

        px[i]=pp,qx[i]=qp;

    }

    calc(,m,,pp,,qp);

    for(int i=;i<=m;++i)if(os[i][]==)printf("%d\n",ans[i]);

    return ;

}