$RT$,怎么卡过去呀qwq

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<string>
#define ll long long

using namespace std;

bool ok=0;

char S[500005];

struct Node{
	int l,r,I,O;
	ll IO,OI,IOI;
	Node *left,*right;
	void mem()
	{
		l=r=I=O=IO=OI=IOI=0;
		left=right=NULL;
	}
}*Tree;

void update(Node *cur,Node *le,Node *rt)
{
	
	cur->I=le->I+rt->I;
	
	cur->O=le->O+rt->O;
	
	cur->IO= 1ll*le->IO + le->I * rt->O + rt->IO;
	
	cur->OI=1ll*le->OI+le->O*rt->I+rt->OI;
	
	cur->IOI=1ll*le->IOI+le->IO*rt->I+le->I*rt->OI+rt->IOI;
	
}

Node *built(int l,int r)
{
	Node *cur=new Node;
	cur->mem();
	cur->l=l;cur->r=r;
	
	if(l==r)
	{
		if(S[l]=='I')cur->I=1;
		if(S[l]=='O')cur->O=1;
		return cur;
	}
	int mid=(l+r)>>1;
	cur->left=built(l,mid),cur->right=built(mid+1,r);
	update(cur,cur->left,cur->right);
	return cur;
}

void modify(int x,char k,Node *cur)
{
	if(cur->l==cur->r)
	{
		cur->I=cur->O=0;
		if(k=='I')cur->I=1;
		if(k=='O')cur->O=1;
		return;
	}
	int mid=(cur->l+cur->r)>>1;
	if(x<=mid)modify(x,k,cur->left);
	else modify(x,k,cur->right);
	update(cur,cur->left,cur->right);
	return;
}

Node *query(int l,int r,Node *cur)
{
	if(l<=cur->l&&cur->r<=r)
		return cur;
	int mid=(cur->l+cur->r)>>1;
	if(r<=mid){return query(l,r,cur->left);} 
	if(l>mid){return query(l,r,cur->right);} 
	else 
	{
		Node *le=query(l,r,cur->left),*rt=query(l,r,cur->right);
		Node *ans=new Node;
		ans->mem();
		update(ans,le,rt);
		ok=1;
		return ans;
	}
}

signed main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	scanf("%s",S+1);
	Node *Tree=built(1,n);
	for(int i=0;i<m;i++)
	{
		int t;
		scanf("%d",&t);
		if(t==1)
		{
			int x;
			char c;
			scanf("%d",&x);cin>>c;
			modify(x,c,Tree);
		}
		else
		{
			int x,y;
			scanf("%d%d",&x,&y);
			Node *ans=query(x,y,Tree);
			printf("%lld\n",ans->IOI);
			if(ok){delete(ans);ok=0;}
		}
	}
	return 0;
}