CF610E 分块题解

· · 题解

这是一个分块题解，时间洛谷前十（不劣于线段树解法），空间是线段树解法的千分之一。好像薄纱除了 ODT 以外所有的解法。（振臂高呼：卡掉 ODT！空间开到 1M！）

1. 如何计数？

考虑如果给定的排列就是 \texttt{a}\sim\texttt{j}，那么如何单组 \Theta(n) 计算答案？

方法很简单：扫一遍 s 串，当 s_i\ge s_{i+1}(0\le i<\text{len}(s)-1) 时使答案累加，最后输出答案加一即可。

为什么能这样？我们可以把字母看成一个折线图。最后应该是每组 10 个字母一轮一轮这么过，组内一直上升，直到从 \texttt{j} 变成下一组的 \texttt{a} 时才下降回来。当 s_i\ge s_{i+1} 时，说明在这里折线图没有上升，说明他们不能被分在一组内（一组内必须单调上升）。因此这是一个断点。

故我们数出断点的个数就是上面的“答案”。显然断点加一就是段数（比如一根木棒切 x 刀变成 (x+1) 根木棒）。

2. 如何维护？

我们已经有了个 \Theta(nm) 的解法。不难发现我们可以维护所有的 v_{p,q}，表示 s_i=p\land s_{i+1}=q 的 i 的个数。这样我们可以做到任意排列了：枚举所有 (p,q)，如果 p 不在 q 前面，那么答案就加上 v_{p,q}。不难发现它的特殊情况就是上面【1】中的算法的优化。

上面的算法是个静态算法，复杂度 \Theta(mk^2)。

考虑如何支持区间修改。我们可以维护 v_{p,q} 的一个单点值 v'_{i,p,q} 表示 s_{i,i+1} 的 v_{p,q}，不难发现 \forall i,\sum_{(p,q)}v_{i,p,q}=1。修改的时候，直接修改 v'_{i,p,q}（区间推平成 0 或 1），最后就是 v_{p,q}=\sum_{0\le i<\text{len}(s)-1}v'_{i,p,q}。

发现 500M 的内存卡的好紧（线段树的空间复杂度为 \Theta(nk^2)，还有至少四倍常数），所以不敢冒险写线段树，可能会被卡。

考虑分块。定义 V_{b,p,q}=\sum_{i\in \text{block}(b)}v'_{i,p,q}。发现这样子我们区间推平就是小块暴力，然后大块直接把它的 V 全部变成 0，除了 V_{b,p,q} 变成 B=|\text{block}(b)|。

时间复杂度为 \Theta(mB+\frac{mnk^2}B)（注意到散块的暴力只用一加一减）。可以令 B=k\sqrt n，这样复杂度为 \Theta(mk\sqrt n)，实测 B=1500 最快。这个复杂度只比线段树解法慢四五倍。而且因为常数小，其实跑得还更快。

空间复杂度为 \Theta(n+\frac {nk^2}B)=\Theta(n+k\sqrt n)，几乎就是线性。交上去的空间是以 KB 为单位计算的。

3. 如何实现？

说着简单，实现真的非常困难！

首先，我们应该明确块与块之间的关系。比如 i,i+1 跨两个块时，我们答案算给谁？我的方式是算给左边的块。然后就是我们更新的时间顺序，应该是先下传推平标记，再删除散块无用答案，再处理整块，再加入散块的新答案。（大家可以想想为啥要这样）

还有一个事情是也需要更新 l-1 的答案，因为 l-1,l 也被修改了。

代码：

constexpr int B=1500;

int n,q,k,cnt[14][14],val[140][14][14],id[14];
char s[200010],tag[20010];

inline int bel(int x){return (x-1)/B+1;}
inline int L(int x){return (x-1)*B+1;}
inline int R(int x){return x*B;}

void totL(int i,char c){
  if (i!=1){
    --val[bel(i-1)][s[i-1]^96][s[i]^96];
    --cnt[s[i-1]^96][s[i]^96];
    ++val[bel(i-1)][s[i-1]^96][c^96];
    ++cnt[s[i-1]^96][c^96];
  }
}

void chgf(int i){
  if (i!=n){
    --val[bel(i)][s[i]^96][s[i+1]^96];
    --cnt[s[i]^96][s[i+1]^96];
  }
}

void chg(int i){
  // cout<<s[i]<<' '<<c<<' '<<cnt[1][2]<<'\n';
  if (i!=n){
    ++val[bel(i)][s[i]^96][s[i+1]^96];
    ++cnt[s[i]^96][s[i+1]^96];
  }
}

void down(int id){
  rep(i,L(id),R(id))s[i]=tag[id];
  tag[id]=0;
}

void chk(int id){
  if (id>0&&id<=bel(n)-1&&tag[id])down(id);
}

void chkx(int p){
  chk(bel(p-1));
  chk(bel(p));
  chk(bel(p+1));
}

void bfdel(int l,int r){
  // cout<<l<<' '<<r<<' '<<c<<'\n';
  chkx(l),chkx(r);
  // cout<<cnt[1][1]<<'\n';
  rep(i,l,r)chgf(i);
}
void bfadd(int l,int r){
  // cout<<l<<' '<<r<<' '<<c<<'\n';
  chkx(l),chkx(r);
  // cout<<cnt[1][1]<<'\n';
  rep(i,l,r)chg(i);
}

void add(int l,int r,char c){
  // cout<<cnt[2][2]<<'\n';
  if (bel(l)+1>=bel(r)){
    chkx(l);
    totL(l,c);
    bfdel(l,r);
    rep(i,l,r)s[i]=c;
    bfadd(l,r);
    return ;
  }
  // cout<<cnt[1][1]<<'\n';
  chkx(l);
  totL(l,c);
  bfdel(l,R(bel(l)));
  bfdel(L(bel(r)),r);
  rep(i,bel(l)+1,bel(r)-1){
    tag[i]=c;
    rep(c1,1,10)rep(c2,1,10){
      cnt[c1][c2]-=val[i][c1][c2];
      val[i][c1][c2]=0;
    }
    val[i][c^96][c^96]=R(i)-L(i)+1;
    cnt[c^96][c^96]+=val[i][c^96][c^96];
    // cout<<val[i][2][2]<<'\n';
    // cout<<val[i][2][2]<<'\n';
    // cout<<i<<' '<<cnt[c^96][c^96]<<'\n';
  }
  // cout<<cnt[1][1]<<'\n';
  rep(i,l,R(bel(l)))s[i]=c;
  rep(i,L(bel(r)),r)s[i]=c;
  bfadd(l,R(bel(l)));
  bfadd(L(bel(r)),r);
}

int main() {
  scanf("%d%d%d%s",&n,&q,&k,s+1);
  rep(i,1,n-1)++cnt[s[i]^96][s[i+1]^96];
  // cout<<cnt[1][2]<<'\n';
  rep(i,1,n-1)++val[bel(i)][s[i]^96][s[i+1]^96];
  while (q--){
    int o;
    scanf("%d",&o);
    if (o==1){
      int l,r;
      char u[2],c;
      scanf("%d%d%s",&l,&r,u);
      c=u[0];
      add(l,r,c);
    }else{
      char u[15];
      scanf("%s",u+1);
      int res=1;
      // rep(i,1,k)rep(j,1,k)
        // cout<<cnt[i][j]<<" \n"[j==k];
      rep(i,1,k)id[u[i]^96]=i;
      rep(i,1,k)rep(j,1,k)if (id[i]>=id[j])
        res+=cnt[i][j];
      printf("%d\n",res);
    }
  }
  return 0;
}