RT 序列分块+操作分块

已经尝试的卡常技巧：

1. freopen 快读
2. 用计数排序代替 sort
3. 调块长
4. 手写 vector

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

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];
  if(x<0)push('-'),x*=-1;
  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=520,qblk=2500;
int n,m,ai[maxn],ban[maxn],sta[maxn]; ll ans[maxn],val[maxn],beg[maxn],st[maxn],ed[maxn];
pair<int,int> sorted[maxn];
const char* endl="\n";

template<typename T>
struct fastvector{
    T values[qblk*10]; int len;
    void push_back(const T& x){ values[len++]=x; }
    T operator[](const int idx){ return values[idx]; }
    int size(){ return len; }
    T* begin(){ return values; }
    T* end(){ return values+len; }
    void clear(){ len=0; }
};
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;
    }
};
data bak[maxn/blk+10],base[maxn/blk+10];
struct arr{
    bool stat[maxn];
    int to[maxn];
    data dat[maxn/blk+10];
    fastvector<pair<int,int>> trace;
    fastvector<int> log;
        
    arr(){
        memset(stat, 0, sizeof(stat));
        memcpy(dat, base, sizeof(base));
        log.clear(); trace.clear();
    }
    bool _ised(int x)const{ return x!=st[beg[x]]&&to[x-1]; }
    bool _isst(int x)const{ return x!=ed[beg[x]]&&to[x+1]; }
    void turn(int x, bool _trace){
        //cout<<"turning up "<<x<<endl;
        if(stat[x])return;
        if(_trace)log.push_back(x);
        stat[x]=true;
        bool f1=_ised(x),f2=_isst(x);
        if(!f1&&!f2){
            dat[beg[x]].ans++;
            to[x]=x;
            //cout<<"kind-IV"<<endl;
            if(x==st[beg[x]])dat[beg[x]].pre++;
            if(x==ed[beg[x]])dat[beg[x]].suf++;
        }else if(f1&&f2){
            int k1=x-to[x-1],k2=to[x+1]-x;
            dat[beg[x]].ans=dat[beg[x]].ans-val[k1]-val[k2]+val[k1+k2+1];
            //cout<<"kind-I"<<endl;
            if(_trace){
                trace.push_back({to[x-1],to[to[x-1]]});
                trace.push_back({to[x+1],to[to[x+1]]});
                trace.push_back({x-1,to[x-1]});
                trace.push_back({x+1,to[x+1]});
            }
            if(to[x-1]==st[beg[x]])dat[beg[x]].pre=to[x+1]-to[x-1]+1;
            if(to[x+1]==ed[beg[x]])dat[beg[x]].suf=to[x+1]-to[x-1]+1;
            int a=to[x-1],b=to[x+1];
            to[x+1]=to[x-1]=0;
            to[a]=b;
            to[b]=a;
        }else if(f1){
            int k1=x-to[x-1];
            //cout<<"kind-II"<<endl;
            dat[beg[x]].ans=dat[beg[x]].ans-val[k1]+val[k1+1];
            if(to[x-1]==st[beg[x]])dat[beg[x]].pre=x-to[x-1]+1;
            if(x==ed[beg[x]])dat[beg[x]].suf=x-to[x-1]+1;
            if(_trace){
                trace.push_back({to[x-1],to[to[x-1]]});
                trace.push_back({x-1,to[x-1]});
            }
            int a=to[x-1];
            to[x]=to[x-1];
            to[x-1]=0;
            to[a]=x;
        }else if(f2){
            int k1=to[x+1]-x;
            //cout<<"kind-III"<<endl;
            dat[beg[x]].ans=dat[beg[x]].ans-val[k1]+val[k1+1];
            if(to[x+1]==ed[beg[x]])dat[beg[x]].suf=to[x+1]-x+1;
            if(x==st[beg[x]])dat[beg[x]].pre =to[x+1]-x+1;
            if(_trace){
                trace.push_back({to[x+1],to[to[x+1]]});
                trace.push_back({x+1,to[x+1]});
            }
            int a=to[x+1];
            to[x]=to[x+1];
            to[x+1]=0;
            to[a]=x;
        }
    }
    void rollback(){
        reverse(trace.begin(),trace.end());
        for(int i=0;i<trace.size();i++)to[trace[i].first]=trace[i].second;
        trace.clear();
        for(int i=0;i<log.size();i++)to[log[i]]=0,stat[log[i]]=false;
        log.clear();
    }
    ll query(int l, int r)const{
        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;

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;

std::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,key++;
}
void solve(){
    cur=arr();
    for(int i=1;i<=n;i++)sorted[i]={ai[i], i},ban[i]=false;
    qsort(sorted+1,sorted+n+1);
    for(int i=1;i<=mcnt;i++)ban[modifies[i].x]=true;
    sort(queries+1,queries+qcnt+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, false);
            ptr++;
        }
        memcpy(bak,cur.dat,sizeof(cur.dat));
        for(int j=1;j<=mcnt;j++)sta[modifies[j].x]=0;
        for(int j=mcnt;j>=1;j--){
            if(modifies[j].tim<queries[i].tim){
                if(sta[modifies[j].x])continue;
                if(modifies[j].y<=queries[i].x)cur.turn(modifies[j].x, true);
                sta[modifies[j].x]=1;
            }
        }
        for(int j=1;j<=mcnt;j++)if(!sta[modifies[j].x]&&ai[modifies[j].x]<=queries[i].x&&!cur.stat[modifies[j].x]){
            cur.turn(modifies[j].x, true);
            sta[modifies[j].x]=true;
        }
        ans[queries[i].tar]=cur.query(queries[i].l,queries[i].r);
        memcpy(cur.dat,bak,sizeof(bak));
        cur.rollback();
    }
    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;
    for(int i=1;i<=n;i++){
        beg[i]=(i-1)/blk+1;
        base[beg[i]].len++;
        if(!st[beg[i]])st[beg[i]]=i;
        ed[beg[i]]=i;
    }
    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();
    //for(int i=1;i<=3;i++)cout<<cur.dat[i].ans<<' '<<cur.dat[i].pre<<' '<<cur.dat[i].suf<<' '<<cur.dat[i].len<<endl;
    //for(int i=1;i<=n;i++)cout<<cur.stat[i];
}