$20$ 分，求助。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

#define int long long

int n, m;
string s;

const int N = 5e5 + 5;

struct SegTree
{
	int l, r, I, IO, O, OI, IOI;
	SegTree()
	{
		l = r = I = IO = O = OI = IOI = 0;
	}
};

SegTree tree[N << 2];

inline void merge(SegTree& a, SegTree& b, SegTree& c)
{
	c.I = a.I + b.I;
	c.O = a.O + b.O;
	c.IO = a.IO + b.IO + a.I * b.O;
	c.OI = a.OI + b.OI + b.O * a.I;
	c.IOI = a.IOI + b.IOI + a.IO * b.I + a.I * b.OI;
}

inline void push_up(int u)
{
	tree[u].I = tree[u << 1].I + tree[u << 1 | 1].I;
	tree[u].O = tree[u << 1].O + tree[u << 1 | 1].O;
	tree[u].IO = tree[u << 1].I * tree[u << 1 | 1].O + tree[u << 1].IO + tree[u << 1 | 1].IO;
	tree[u].OI = tree[u << 1].O * tree[u << 1 | 1].I + tree[u << 1].OI + tree[u << 1 | 1].OI;
	tree[u].IOI = tree[u << 1].IOI + tree[u << 1 | 1].IOI + tree[u << 1].IO * tree[u << 1 | 1].I + tree[u << 1].I * tree[u << 1 | 1].OI;
}

inline void build(int u, int l, int r)
{
	tree[u].l = l, tree[u].r = r;
	if (l == r)
	{
		char c = s[r - 1];
		if (c == 'I') tree[u].I = 1;
		else if (c == 'O') tree[u].O = 1;
	}
	else
	{
		int mid = (l + r) >> 1;
		build(u << 1, l, mid);
		build(u << 1 | 1, mid + 1, r);
		push_up(u);
	}
}

inline void modify(int u, int x, char c)
{
	if (tree[u].l == x && tree[u].r == x)
	{
		if (tree[u].I) tree[u].I = 0;
		else tree[u].O = 0;
		if (c == 'I') tree[u].I = 1;
		else if (c == 'O') tree[u].O = 1;
	}
	else
	{
		int mid = (tree[u].l + tree[u].r) >> 1;
		if (x <= mid) modify(u << 1, x, c);
		else modify(u << 1 | 1, x, c);
		push_up(u);
	}
}

inline SegTree query(int u, int l, int r)
{
	if (tree[u].l >= l && tree[u].r <= r) return tree[u];
	SegTree a, b, c;
	int mid = (tree[u].l + tree[u].r) >> 1;
	if (l <= mid) a = query(u << 1, l, r);
	if (r > mid) b = query(u << 1 | 1, l, r);
	merge(a, b, c);
	return c;
}

signed main()
{
	scanf("%lld %lld", &n, &m);
	cin >> s;
	build(1, 1, n);
	while (m--)
	{
		int opt;
		scanf("%lld", &opt);
		if (opt == 1)
		{
			int r;
			char c;
			cin >> r >> c;
			modify(1, r, c);
		}
		else
		{
			int l, r;
			scanf("%lld %lld", &l, &r);
			printf("%lld\n", query(1, l, r).IOI);
		}
	}
	return 0;
}