直接 fhp treap 平衡树维护区间 red,r,e,d,der,de,er,re,ed 的个数，考虑乘法原理即可

#include<bits/stdc++.h>
#define int long long
#define pc(x) putchar(x)
using namespace std;
int begintime=clock();
bool __ST__;
void write(int x){ if(x<0) x=-x,pc('-');if(!x) return ;write(x/10);pc(x%10+'0');return ;}
void wr(int x){ if(!x) pc('0');else write(x);return ;}
int read(){
	int res=0;char c=getchar();bool f=0;
	while(c<'0' || c>'9') c=='-'?f=1:f=f,c=getchar();
	while(c>='0' && c<='9') res=(res<<3)+(res<<1)+c-'0',c=getchar();
	return f?-res:res;
}
const int N=1e5+10;

mt19937 rnd(time(NULL));
int T=1,n,m,root,cnt;
int a[N];
struct node{
	int L,R,v;
	int r,e,d,re,ed,red;
	int er,de,der;
	int flip;
	unsigned long long pri;
	int si;
}tree[N];

void Flip(int o){
	tree[o].flip^=1;
	swap(tree[o].re,tree[o].er);
	swap(tree[o].ed,tree[o].de);
	swap(tree[o].red,tree[o].der);
	swap(tree[o].L,tree[o].R);
	return ;
}
void push_down(int o){
	if(!tree[o].flip) return ;
	Flip(tree[o].L),Flip(tree[o].R);
	tree[o].flip=0;
	return ;
}
void push_up(int o){
	node ls=tree[tree[o].L],rs=tree[tree[o].R];
	node i=tree[o];
	i.r=ls.r+rs.r,i.e=ls.e+rs.e,i.d=ls.d+rs.d;
	if(i.v==1) i.r++;
	if(i.v==2) i.e++;
	if(i.v==3) i.d++;
	i.re=ls.re+rs.re+ls.r*rs.e;
	if(i.v==1) i.re+=rs.e;
	if(i.v==2) i.re+=ls.r;
	i.ed=ls.ed+rs.ed+ls.e*rs.d;
	if(i.v==2) i.ed+=rs.d;
	if(i.v==3) i.ed+=ls.e;
	i.er=ls.er+rs.er+ls.e*rs.r;
	if(i.v==2) i.er+=rs.r;
	if(i.v==1) i.er+=ls.e;
	i.de=ls.de+rs.de+ls.d*rs.e;
	if(i.v==3) i.de+=rs.e;
	if(i.v==2) i.de+=ls.d;
	i.red=ls.red+rs.red+ls.re*rs.d+ls.r*rs.ed;
	if(i.v==1) i.red+=rs.ed;
	if(i.v==2) i.red+=ls.r*rs.d;
	if(i.v==3) i.red+=ls.re;
	i.der=ls.der+rs.der+ls.de*rs.r+ls.d*rs.er;
	if(i.v==1) i.der+=ls.de;
	if(i.v==2) i.der+=ls.d*rs.r;
	if(i.v==3) i.der+=rs.er;
	i.si=ls.si+rs.si+1;
	tree[o]=i;
	return ;
}
int newnode(int x){ 
	tree[++cnt]=((node){0,0,0,0,0,0,0,0,0,0,0,0,0,rnd(),1});
	if(x==1) tree[cnt].r++;
	if(x==2) tree[cnt].e++;
	if(x==3) tree[cnt].d++;
	tree[cnt].v=x;
	return cnt;
}
int merge(int L,int R){
	if(!L || !R) return L+R;
	if(tree[L].pri>tree[R].pri){
		push_down(L),tree[L].R=merge(tree[L].R,R);
		push_up(L);return L;
	}
	else{
		push_down(R),tree[R].L=merge(L,tree[R].L);
		push_up(R);return R;
	}
}
void split(int u,int x,int &L,int &R){
	if(!u) return L=R=0,void();
	push_down(u);
	if(tree[tree[u].L].si+1<=x) L=u,split(tree[u].R,x-tree[tree[u].L].si-1,tree[u].R,R);
	else R=u,split(tree[u].L,x,L,tree[u].L);
	push_up(u);
	return ;
}
void out(int x){
	if(!x) return;
	out(tree[x].L);
	printf("%d ",tree[x].r);
	out(tree[x].R);
}
void solve(){

	n=read(),m=read();
	for(int i=1;i<=n;i++){
		char c;cin>>c;
		if(c=='r') a[i]=1;
		if(c=='e') a[i]=2;
		if(c=='d') a[i]=3;
		root=merge(root,newnode(a[i]));
//		printf("%d ",tree[root].r);
	}
//	out(root);
//	printf("%d\n",tree[root].red);
	while(m--){
		int l=read(),r=read();
		int a,b,c;
		split(root,r,a,c);
		split(a,l-1,a,b);
		Flip(b);
		merge(merge(a,b),c);
		printf("%lld\n",tree[root].red);
		split(root,r,a,c);
		split(a,l-1,a,b);
		Flip(b);
		merge(merge(a,b),c);
//		out(1,1,n);
	}

	return ;
}
void clr(){

	return ;
}

bool __ED__;
signed main(){
// 	double MEM=((&__ED__)-(&__ST__))/1024.0/1024.0;
// 	fprintf(stderr,"%.2lf MB %.2lf GB\n\n",MEM,MEM/1024.0);
// 	freopen("in.in","r",stdin);
// 	freopen("out.out","w",stdout);

//  T=read();
	while(T--) solve(),clr();

// 	fprintf(stderr,"\n%d ms",clock()-begintime);
	return 0;
}

/*
6 2
rreedd
*/