【题解】「Ynoi2019」魔法少女网站 序列分块+操作分块 — Qiuly

首先不难想到对题目进行一个转化：对于询问操作，其实就是以 $>x$ 的位置为断点，然后问剩下的区间贡献和（形如 $\sum\frac{len(len-1)}{2}$ 的贡献式）。

$>x$ 的这个断点限制很不好办，可不可以将所有的询问按照 $x$ 从小到大排序后依次处理呢？

那么现在的任务就是维护一个 01 序列，最开始每个位置都是 0 。需要短时间内支持将 0 换成 1 ，然后支持区间询问。但是修改操作的话每一次都需要考虑，复杂度显然错误。

考虑对操作分块：每 $\sqrt{n}$ 次重建原序列，然后暂时储存的 $\sqrt{n}$ 次操作一起做。

然后接下来就是维护这个 01 序列的事情了，不过直接做的话也不好做：如果仅仅是将 0 换成 1 的话，则对于每个极长的 1 区间，在其端点记录信息后，可以直接合并，然后每一个块记录一下贡献和即可。但是如果是将 1 换成 0 的话，就需要拆开区间，但这显然没法 $O(1)$ 完成。

容易发现将 1 换成 0 的操作只会在这 $\sqrt{n}$ 个操作中出现。考虑先将有修改的位置空出来。然后每一次询问时再将这些位置插入进去，记录一下改变的答案量和指针个数（显然最多两个），询问完了原地撤回即可。这样子的话这些操作全部变成了将 0 换成 0 或 1，就可以维护了。

关于实现：

• 本体代码量较大，很卡常，调试难度中等偏低。
• 注意多用点 const ：比如 modify 的时候要多次访问 $pos-1$ 和 $pos+1$ ，接个 const 会快不少。
• 注意多调调块长：因为常数，其实对操作分块时块大小远大于 $\sqrt{m}$（经过多次尝试我采用的是 $\sqrt{\frac{27}{4}m}$ 的块大小），对于序列分块的话也要注意常数，这里主要其实是询问时的常数（这里采用的 $\sqrt{\frac{4}{5}n}$ 的块大小）。

（感觉这系列题目序列分块的块大小都最好小于 $\sqrt{n}$ ，就前几题而言，块大小在 $[\sqrt{0.7n},\sqrt{0.8n}]$ 之间跑的很快。

const int N=3e5+5;
const int S=2e3+5;

ll calc[N];
int n,m,c1,c2,a[N];
struct Modify {int tim,pos,val;} q1[S];
struct Query {int tim,l,r,lim,id;} q2[S];

// {{{ Data_Struct_Block

bool seq[N];
int L[S],R[S],id[N],p[N],sum[S];

inline void clear() {CLEAR(seq),CLEAR(p),CLEAR(sum);}
inline void init() {
    int sqrtn=sqrt(n*4/5+1);
    for(int i=1,c=1,j;i<=n;i=j+1,++c) {
        L[c]=i,R[c]=j=min(n,i+sqrtn);
        lep(t,L[c],R[c]) id[t]=c;
    }
}

// {{{ modify

int top;
struct Node {
    int id,ans,t1[2],t2[2]; bool typ;
    inline void clear() {t1[0]=t2[0]=t1[1]=t2[1]=typ=0;}
} sta[S];

Node tmp_node;
inline void modify(const int &pos,bool typ) {
    p[pos]=pos,seq[pos]=1;
    tmp_node.id=pos;
    const int las=pos-1,nxt=pos+1,tmp_p=p[las];
    const bool able1=(seq[las]&&L[id[pos]]!=pos),able2=(seq[nxt]&&R[id[pos]]!=pos);

    if(!able1&&!able2) tmp_node.clear(),tmp_node.ans=1;
    else {
        tmp_node.typ=1;
        if(able1&&able2) {
            tmp_node.ans=(nxt-p[las])*(p[nxt]-las);
            tmp_node.t1[0]=p[las],tmp_node.t1[1]=p[p[las]],p[p[las]]=p[nxt],
            tmp_node.t2[0]=p[nxt],tmp_node.t2[1]=p[p[nxt]],p[p[nxt]]=tmp_p;
        } else {
            if(able1) {
                tmp_node.ans=nxt-p[las];
                tmp_node.t1[0]=pos,tmp_node.t1[1]=p[pos],p[pos]=p[las],
                tmp_node.t2[0]=p[las],tmp_node.t2[1]=p[p[las]],p[p[las]]=pos;
            } else {
                tmp_node.ans=p[nxt]-las;
                tmp_node.t1[0]=pos,tmp_node.t1[1]=p[pos],p[pos]=p[nxt],
                tmp_node.t2[0]=p[nxt],tmp_node.t2[1]=p[p[nxt]],p[p[nxt]]=pos;
            }
        }
    }
    sum[id[pos]]+=tmp_node.ans;
    if(typ) sta[++top]=tmp_node;
}
inline void back() {
    while(top) {
        tmp_node=sta[top]; --top;
        sum[id[tmp_node.id]]-=tmp_node.ans,seq[tmp_node.id]=0;
        if(tmp_node.typ==1) p[tmp_node.t2[0]]=tmp_node.t2[1],p[tmp_node.t1[0]]=tmp_node.t1[1];
    }
}

// }}}

inline ll query(const int &l,const int &r) {
    ll ans=0;
    if(id[l]==id[r]) {
        int cnt=0;
        lep(i,l,r) {if(seq[i]) ++cnt; else ans+=calc[cnt],cnt=0;}
        return ans+calc[cnt];
    }

    int c1=0,c2=0;
    lep(i,l,R[id[l]]) {if(seq[i]) ++c1; else ans+=calc[c1],c1=0;}
    rep(i,r,L[id[r]]) {if(seq[i]) ++c2; else ans+=calc[c2],c2=0;}

    int tot=c1;
    lep(i,id[l]+1,id[r]-1) {
        if(p[L[i]]==R[i]) tot+=R[i]-L[i]+1;
        else {
            if(seq[L[i]]) tot+=p[L[i]]-L[i]+1,ans-=calc[p[L[i]]-L[i]+1];
            ans+=calc[tot]+sum[i],tot=0;
            if(seq[R[i]]) tot+=R[i]-p[R[i]]+1,ans-=calc[R[i]-p[R[i]]+1];
        }
    }
    return ans+calc[tot+c2];
}

// }}}

// {{{ solve

ll ans[S];
int head[N],cnt;
struct Edge {int nxt,to;} G[N];
inline void addedge(int u,int v) {G[++cnt]=(Edge){head[u],v},head[u]=cnt;}
bool broke[N],use[N];

inline void solve() {
    clear();
    lep(i,1,c1) broke[q1[i].pos]=true;
    lep(i,1,n) if(!broke[i]) addedge(a[i],i);
    std::sort(q2+1,q2+1+c2,[](Query x,Query y){return x.lim<y.lim;});

    int pot=1;
    lep(i,1,c2) {
        while(pot<=q2[i].lim) {for(int &e=head[pot];e;e=G[e].nxt) modify(G[e].to,0); ++pot;}

        rep(j,c1,1) if(q1[j].tim<q2[i].tim&&!use[q1[j].pos]) {
            use[q1[j].pos]=true;
            if(q1[j].val<=q2[i].lim) modify(q1[j].pos,1);
        }
        lep(j,1,c1) if(!use[q1[j].pos]) {
            use[q1[j].pos]=true;
            if(a[q1[j].pos]<=q2[i].lim) modify(q1[j].pos,1);
        }
        ans[q2[i].id]=query(q2[i].l,q2[i].r); back();
        lep(j,1,c1) use[q1[j].pos]=false;
    }
    CLEAR(head),cnt=0;
    lep(i,1,c1) broke[q1[i].pos]=false;
}

// }}}

int sqrtm,op,l,r,x,y;
int main() {
    IN(n,m),sqrtm=sqrt(m*27/4+1),init();
    lep(i,1,n) calc[i]=1ll*i*(i+1)/2;
    lep(i,1,n) IN(a[i]);

    for(int i=1,j;i<=m;i=j+1) {
        j=min(m,i+sqrtm),c1=c2=0;
        lep(t,i,j) {
            IN(op);
            if(op==1) IN(x,y),q1[++c1]=(Modify){t,x,y};
            if(op==2) IN(l,r,x),q2[++c2]=(Query){t,l,r,x,c2};
        }
        solve();
        lep(i,1,c2) printf("%lld\n",ans[i]);
        lep(i,1,c1) a[q1[i].pos]=q1[i].val;
    }
    return 0;
}