F题题解：

题目说求字符串 s 中的子序列red的数目 减去 字符串 t 中的子序列red的数目。

因为有修改，往维护方面想，考虑线段树，维护区间red6个非空子串（r、e、d、re、ed、red）的个数。

众所周知，red=re+d或r+ed，而re=r+e，ed=e+d。

区间 [l,r] 的r的个数 = [l,mid] 的r的个数 + [mid+1,r] 的r的个数。e和d 同理。

区间 [l,r] 的re的个数 = [l,mid] 的re的个数 + [mid+1,r] 的re的个数 + [l,mid] 的r的个数 * [mid+1,r] 的e的个数。ed 同理。

区间 [l,r] 的red的个数 = [l,mid] 的red的个数 + [mid+1,r] 的red的个数 + [l,mid] 的r的个数 * [mid+1,r] 的ed的个数 + [l,mid] 的re的个数 * [mid+1,r] 的d的个数。

修改直接单点修改没有技巧。

查询直接取树根的red个数就行。

代码：

#include<bits/stdc++.h>
#define ll long long
#define MXN 1000002
using namespace std;
inline void rd(ll &x){x=0;short f=1;char c=getchar();while((c<'0'||c>'9')&&c!='-') c=getchar();if(c=='-') f=-1,c=getchar();while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();x*=f;}
inline void pt(ll x){if(x<0) putchar('-'),x=-x;if(x>9) pt(x/10);putchar(x%10+'0');}
struct bzm{
    ll pl,pr,num[6];//num分别是r,e,d,re,ed,red的个数
}tr[MXN*2];
ll rt[2],trt;
ll T=1,n,m,a[2][MXN],ans;
string s,t;
void doit(ll p,ll x,ll w){//叶节点单点修改
    for(ll i=0;i<6;i++)
        tr[p].num[i]=0;
    if(w=='r') tr[p].num[0]=1;
    else if(w=='e') tr[p].num[1]=1;
    else if(w=='d') tr[p].num[2]=1;
}
void ptup(ll p){//上传操作
    bzm pl=tr[tr[p].pl],pr=tr[tr[p].pr];
    for(ll i=0;i<6;i++)
        tr[p].num[i]=pl.num[i]+pr.num[i];
    tr[p].num[3]+=pl.num[0]*pr.num[1];
    tr[p].num[4]+=pl.num[1]*pr.num[2];
    tr[p].num[5]+=pl.num[3]*pr.num[2]+pl.num[0]*pr.num[4];
}
void bd(ll t,ll &p,ll l,ll r){//初始化建树
    p=++trt;
    if(l==r){doit(p,l,a[t][l]);return;}
    ll mid=l+r>>1;
    bd(t,tr[p].pl,l,mid);
    bd(t,tr[p].pr,mid+1,r);
    ptup(p);
}
void chg(ll t,ll p,ll l,ll r,ll x){//单点修改
    if(l==r){doit(p,l,a[t][l]);return;}
    ll mid=l+r>>1;
    if(x<=mid) chg(t,tr[p].pl,l,mid,x);
    else chg(t,tr[p].pr,mid+1,r,x);
    ptup(p);
}
void solve(){
    rd(n),rd(m);
    cin>>s>>t;
    for(ll i=1;i<=n;i++)
        a[0][i]=s[i-1],a[1][i]=t[i-1];
    bd(0,rt[0],1,n),bd(1,rt[1],1,n);
    for(ll i=1,x;i<=m;i++){
        rd(x);swap(a[0][x],a[1][x]);//直接交换
        chg(0,rt[0],1,n,x),chg(1,rt[1],1,n,x);//更新线段树
        pt(tr[rt[0]].num[5]-tr[rt[1]].num[5]),puts("");//输出red个数的差值（不要取绝对值）
    }
}int main(){while(T--) solve();}