RT，TLE 0 分

已经用的优化：freopen，预处理贡献，qsort 是一个复杂度为 $O(n+\sqrt m)$ 的排序，总体复杂度已经确认。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using std::cin;
using std::cout;
using std::pair;
using std::sort;
using std::vector;

namespace IO {
constexpr int MAXSIZE = 1 << 20;
char buf[MAXSIZE], *p1, *p2;
#define gc()                                                               \
  (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) \
       ? EOF                                                               \
       : *p1++)

void read(int& x) {
  x=0;
  char c = gc();
  while (!isdigit(c))c = gc();
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = gc();
}

char pbuf[1 << 20], *pp = pbuf;

void push(const char &c) {
  if (pp - pbuf == 1 << 20) fwrite(pbuf, 1, 1 << 20, stdout), pp = pbuf;
  *pp++ = c;
}

void write(long long x) {
  static int sta[35];
  int top = 0;
  do {
    sta[top++] = x % 10, x /= 10;
  } while (x);
  while (top) push(sta[--top] + '0');
}
void flush(){
  fwrite(pbuf, 1, pp - pbuf, stdout); pp = pbuf;
}
}  // namespace IO

#define ll long long
const int maxn=3e5+10,blk=500,qblk=500;
int n,m,ai[maxn],ban[maxn],sta[maxn]; ll ans[maxn],val[maxn];
pair<int,int> sorted[maxn];
const char* endl="\n";

struct data{
    ll ans; int pre,suf,len;
    data(){ ans=pre=suf=len=0; }
    data(bool x){ ans=pre=suf=x; len=1; }
    void operator+=(const data other){
        ans=ans+other.ans-val[other.pre]-val[suf]+val[suf+other.pre];
        pre=(pre==len?len+other.pre:pre);
        suf=(other.suf==other.len?other.len+suf:other.suf);
        len=len+other.len;
    }
};
struct arr{
    bool stat[maxn];
    int beg[maxn],ed[maxn],st[maxn];
    data dat[maxn/blk];
        
    arr(){
        memset(stat, 0, sizeof(stat)); memset(dat, 0, sizeof(dat));
        for(int i=1;i<=n;i++){
            beg[i]=(i-1)/blk+1;
            dat[beg[i]].len++;
            if(!st[beg[i]])st[beg[i]]=i;
            ed[beg[i]]=i;
        }
    }
    void rebuild(int id){
        dat[id]=data();
        for(int i=st[id];i<=ed[id];i++)dat[id]+=stat[i];
    }
    void turn(int x){
        if(stat[x])return;
        stat[x]=true;
        rebuild(beg[x]);
    }
    ll query(int l, int r){
        data res;
        if(beg[l]==beg[r]){
            for(int i=l;i<=r;i++)res+=stat[i];
            return res.ans;
        }
        for(int i=l;i<=ed[beg[l]];i++)res+=stat[i];
        for(int i=beg[l]+1;i<beg[r];i++)res+=dat[i];
        for(int i=st[beg[r]];i<=r;i++)res+=stat[i];
        return res.ans;
    }
} cur;
data bak[maxn/blk];

struct modify{ int x,y,tim; } modifies[qblk+1];
struct query{
    int l,r,x,tim,tar;
    bool operator<(const query other)const{ return x<other.x; }
} queries[qblk+1];
int mcnt,qcnt;

vector<pair<int,int>> _qsort[maxn];
void qsort(pair<int,int>* beg, pair<int,int>* end){
    for(int i=1;i<=n;i++)_qsort[i].clear();
    for(auto i=beg;i<end;i++)_qsort[i->first].push_back(*i);
    for(int i=1,key=0;i<=n;i++)for(auto j:_qsort[i])*(beg+key)=j,beg++;
}

void solve(){
    memset(ban, 0, sizeof(ban));
    cur=arr();
    int banid=0;
    for(int i=1;i<=mcnt;i++)ban[modifies[i].x]=++banid;
    sort(queries+1,queries+qcnt+1);
    for(int i=1;i<=n;i++)sorted[i]={ai[i], i};
    qsort(sorted+1,sorted+n+1);
    int ptr=1;
    for(int i=1;i<=qcnt;i++){
        while(ptr<=n&&sorted[ptr].first<=queries[i].x){
            if(!ban[sorted[ptr].second])cur.turn(sorted[ptr].second);
            ptr++;
        }
        vector<int> log;
        memcpy(bak,cur.dat,sizeof(cur.dat));
        for(int j=1;j<=mcnt;j++)sta[ban[modifies[j].x]]=0;
        for(int j=mcnt;j>=1;j--){
            if(modifies[j].tim<queries[i].tim){
                if(sta[ban[modifies[j].x]])continue;
                if(modifies[j].y<=queries[i].x)cur.turn(modifies[j].x),log.push_back(modifies[j].x);
                sta[ban[modifies[j].x]]=1;
            }
        }
        for(int j=1;j<=mcnt;j++)if(!sta[ban[modifies[j].x]]&&ai[modifies[j].x]<=queries[i].x){
            cur.turn(modifies[j].x);
            log.push_back(modifies[j].x);
            sta[ban[modifies[j].x]]=true;
        }
        ans[queries[i].tar]=cur.query(queries[i].l,queries[i].r);
        memcpy(cur.dat,bak,sizeof(bak));
        for(auto x:log)cur.stat[x]=false;
    }
    for(int i=1;i<=mcnt;i++)ai[modifies[i].x]=modifies[i].y;
    mcnt=qcnt=0;
}
int main(){
    std::ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    IO::read(n); IO::read(m);
    for(int i=1;i<=n;i++)IO::read(ai[i]),val[i]=(ll)i*(i+1)/2;
    int totquery=0;
    for(int oid=1;oid<=m;oid++){
        int op; IO::read(op);
        if(op==1)mcnt++,IO::read(modifies[mcnt].x),IO::read(modifies[mcnt].y),modifies[mcnt].tim=oid;
        else qcnt++,IO::read(queries[qcnt].l),IO::read(queries[qcnt].r),IO::read(queries[qcnt].x),queries[qcnt].tim=oid,queries[qcnt].tar=++totquery;
        if(oid%qblk==0)solve();
    }
    solve();
    for(int i=1;i<=totquery;i++)IO::write(ans[i]),IO::push('\n');
    IO::flush();
}