题解#小红的 red 计数#

记表示一个字符串中含有的子串的子序列个数，如时表示子序列的个数，表示子序列的个数，最终答案即为

对一个区间字符串的翻转，对应的变化为区间的对应翻转，即

如果我们快速得到区间对应的，将其翻转，再与区间的合并，就能获取每个询问翻转之后的总体答案

考虑合并两段相邻区间的，记为左半部分为右半部分，则有

表示左右部分各自含有的子序列个数加上左右拼起来的个数

用线段树维护即可

#include<cstring>
#include<algorithm>
using namespace std;
template<class T>inline const void read(T &in)
{
    in=0;char ch(getchar());
    while (ch<48||ch>57)ch=getchar();
    while (ch>47&&ch<58)in=(in<<3)+(in<<1)+(ch&15),ch=getchar();
}
typedef long long ll;
constexpr int N(1e5+5);
int n,m;
char s[N];
inline const int trans(const char &c)
{
    switch (c)
    {
        case 'r':return 0;
        case 'e':return 1;
        case 'd':return 2;
        default:return 4;
    }
}
struct Data
{
    ll f[3][3];
    inline Data()
    {
        memset(f,0,sizeof(f));
    }
    inline Data(const int &x)
    {
        memset(f,0,sizeof(f));
        f[x][x]=1;
    }
    inline Data(const char &c)
    {
        const int t(trans(c));
        memset(f,0,sizeof(f));
        f[t][t]=1;
    }
    inline ll *operator[](const int &x){return f[x];}
    inline ll const *operator[](const int &x)const{return f[x];}
    inline friend Data operator+(const Data &a,const Data &b)
    {
        Data c;
        for (int i(0);i<3;i++)
            for (int j(0);j<3;j++)
            {
                c[i][j]=a[i][j]+b[i][j];
                if (i<j)
                    for (int k(i);k<j;k++)
                        c[i][j]+=a[i][k]*b[k+1][j];
                else
                    for (int k(i);k>j;k--)
                        c[i][j]+=a[i][k]*b[k-1][j];
            }
        return c;
    }
    inline const void reverse()
    {
        for (int i(0);i<2;i++)
            for (int j(i+1);j<3;j++)
                swap(f[i][j],f[j][i]);
    }
};
struct Tree
{
    Data val;
    Tree *lson,*rson;
    inline void *operator new(size_t size);
    inline Tree():val(),lson(NULL),rson(NULL){}
    inline const void pushup()
    {
        val=lson->val+rson->val;
    }
    inline Data query(const int &l,const int &r,const int &L,const int &R)
    {
        if (l>=L&&r<=R)return val;
        const int mid(l+r>>1);
        if (R<=mid)return lson->query(l,mid,L,R);
        if (L>mid)return rson->query(mid+1,r,L,R);
        return lson->query(l,mid,L,mid)+rson->query(mid+1,r,mid+1,R);
    }
}*root;
char memoryPool[N*sizeof(Tree)<<1],*tail(memoryPool+sizeof(memoryPool));
inline void *Tree::operator new(size_t size){return tail-=size;}
inline const void build(Tree *&p,const int &l,const int &r)
{
    p=new Tree;
    if (l==r)return p->val=Data(s[l]),void();
    const int mid(l+r>>1);
    build(p->lson,l,mid);
    build(p->rson,mid+1,r);
    p->pushup();
}
int main()
{
    read(n);read(m);
    scanf("%s",s+1);
    build(root,1,n);
    for (int l,r;m--;)
    {
        read(l);read(r);
        if (l>1&&r<n)
        {
            Data f1(root->query(1,n,1,l-1)),f2(root->query(1,n,l,r)),f3(root->query(1,n,r+1,n));
            f2.reverse();
            f1=f1+f2+f3;
            printf("%lld\n",f1[0][2]);
            continue;
        }
        if (l>1)
        {
            Data f1(root->query(1,n,1,l-1)),f2(root->query(1,n,l,n));
            f2.reverse();
            f1=f1+f2;
            printf("%lld\n",f1[0][2]);
            continue;
        }
        if (r<n)
        {
            Data f1(root->query(1,n,1,r)),f2(root->query(1,n,r+1,n));
            f1.reverse();
            f1=f1+f2;
            printf("%lld\n",f1[0][2]);
            continue;
        }
        Data f1(root->val);
        f1.reverse();
        printf("%lld\n",f1[0][2]);
    }
    return 0;
}