题解 | 研究red子序列的红

#include <stdio.h>
#include <string.h>
#include <unistd.h>

//建立结构体存放r,re,red的值
typedef struct{
    long long  r,e,d,re,ed,red;
} Node;

//定义全局变量存放树
Node tree_s[800020],tree_t[800020];
char s[200005],t[200005];

//建树
void build(Node tree[],int node,int L,int R,char *s){
    if (L==R) {
        memset(&tree[node], 0, sizeof(Node));
        if (s[L-1]=='r') {
            tree[node].r=1;
        }
        else if (s[L-1]=='e') {
            tree[node].e=1;
        }
        else if (s[L-1]=='d') {
            tree[node].d=1;
        }
        return;
    }
    int mid=(L+R)/2;
    build(tree, node*2, L, mid, s);
    build(tree, node*2+1, mid+1, R, s);
    //合并左右子树的值，r，e，d的值均为左右子树相加；
    tree[node].r=tree[node*2].r+tree[node*2+1].r;
    tree[node].e=tree[node*2].e+tree[node*2+1].e;
    tree[node].d=tree[node*2].d+tree[node*2+1].d;
    //re的值为左右子树re的值相加再加上左子树r的数量*右子树e的数量，ed同理
    tree[node].re=tree[node*2].re+tree[node*2+1].re+tree[node*2].r*tree[node*2+1].e;
    tree[node].ed=tree[node*2].ed+tree[node*2+1].ed+tree[node*2].e*tree[node*2+1].d;
    //red的值为左右子树red的值相加，再加上左子树r的数量*右子树ed的数量，再加上左子树re的数量*右子树d的数量
    tree[node].red=tree[node*2].red+tree[node*2+1].red+
                    tree[node*2].r*tree[node*2+1].ed+tree[node*2].re*tree[node*2+1].d;
    

}

//单点修改
void updata(Node tree[],int node,int L,int R,int p,char c){
    if (L==R) {
        memset(&tree[node], 0, sizeof(Node));
        if (c=='r') {
            tree[node].r=1;
        }
        else if (c=='e') {
            tree[node].e=1;
        }
        else if (c=='d') {
            tree[node].d=1;
        }
        return;
    }
    int mid=(L+R)/2;
    if (p<=mid) {
        updata(tree, node*2, L, mid, p, c);
    }
    else {
        updata(tree, node*2+1, mid+1, R, p, c);
    }
    //合并左右子树的值，r，e，d的值均为左右子树相加；
    tree[node].r=tree[node*2].r+tree[node*2+1].r;
    tree[node].e=tree[node*2].e+tree[node*2+1].e;
    tree[node].d=tree[node*2].d+tree[node*2+1].d;
    //re的值为左右子树re的值相加再加上左子树r的数量*右子树e的数量，ed同理
    tree[node].re=tree[node*2].re+tree[node*2+1].re+tree[node*2].r*tree[node*2+1].e;
    tree[node].ed=tree[node*2].ed+tree[node*2+1].ed+tree[node*2].e*tree[node*2+1].d;
    //red的值为左右子树red的值相加，再加上左子树r的数量*右子树ed的数量，再加上左子树re的数量*右子树d的数量
    tree[node].red=tree[node*2].red+tree[node*2+1].red+
                    tree[node*2].r*tree[node*2+1].ed+tree[node*2].re*tree[node*2+1].d;
}

int main() {
    int n,q,a;
    scanf("%d%d",&n,&q);
    scanf("%s",s);
    scanf("%s",t);

    //建树
    build(tree_s,1,1,n,s);
    build(tree_t,1,1,n,t);

    //多次交换
    while (scanf("%d", &a) != EOF) { // 注意 while 处理多个 case
        //将字符串更新为交换后的值
        char b;
        b=s[a-1];
        s[a-1]=t[a-1];
        t[a-1]=b;
		//单点修改并重新统计red的值
        updata(tree_s,1,1,n,a,s[a-1]);
        updata(tree_t, 1, 1, n, a, t[a-1]);
		//直接输出s的red的值-t的red的值
        printf("%lld\n",tree_s[1].red-tree_t[1].red);
    }
    return 0;
}