自动搬运

查看原文

来自洛谷，原作者为

	1kri 寄

搬运于2025-08-24 22:20:11，当前版本为作者最后更新于2020-04-12 06:54:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

GF官方题解

普及组线段树（¿）。

每个节点保存 I、O、IO、OI、IOI 的个数，基于乘法原理转移即可。

当前I的个数 = 左区间I的个数 + 右区间I的个数。

当前O的个数同理。

当前IO的个数 = 左区间IO的个数 + 右区间IO的个数 + 左区间I的个数 $\times$ 右区间O的个数。

当前OI的个数同理。

当前IOI的个数 = 左区间IOI的个数 + 右区间IOI的个数 + 左区间I的个数 $\times$ 右区间OI的个数 + 左区间IO的个数 $\times$ 右区间I的个数。

然后是并不很难的代码。

#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
int n,m,a[500005];
char s[500005];
struct node{
	ll i,o,oi,io,ioi;
	inline void mem(){
		i=o=oi=io=ioi=0;
	}
}tree[4000005];
inline node add(register node a,register node b){
	register node c;
	c.mem();
	c.i=a.i+b.i;
	c.o=a.o+b.o;
	c.oi=a.oi+b.oi+a.o*b.i;
	c.io=a.io+b.io+a.i*b.o;
	c.ioi=a.ioi+b.ioi+a.i*b.oi+a.io*b.i;
	return c;
}
inline void pushup(register int now){
	tree[now]=add(tree[now*2],tree[now*2+1]);
	return;
}
inline void update(register int now,register int nowl,register int nowr,register int pos,register int k){
	if (nowl==nowr){
		tree[now].mem();
		if (k==0)tree[now].i=1;
		else tree[now].o=1;
		return;
	}
	register int mid=(nowl+nowr)/2;
	if (pos<=mid)update(now*2,nowl,mid,pos,k);
	else update(now*2+1,mid+1,nowr,pos,k);
	pushup(now);
	return;
}
inline node query(register int now,register int nowl,register int nowr,register int lt,register int rt){
	if (nowl>=lt&&nowr<=rt)return tree[now];
	register int mid=(nowl+nowr)/2;
	register node s;s.mem();
	if (mid>=lt)s=add(s,query(now*2,nowl,mid,lt,rt));
	if (mid+1<=rt)s=add(s,query(now*2+1,mid+1,nowr,lt,rt));
	return s;
}
inline void build(register int now,register int nowl,register int nowr){
	tree[now].mem();
	if (nowl==nowr){
		if (a[nowl]==0)tree[now].i=1;
		else tree[now].o=1;
		return;
	}
	int mid=(nowl+nowr)/2;
	build(now*2,nowl,mid);
	build(now*2+1,mid+1,nowr);
	pushup(now);
	return;
}
int main(){
	cin>>n>>m;
	scanf("%s",s+1);
    for (int i=1;i<=n;i++){
        if (s[i]=='I')a[i]=0;
        else a[i]=1;
    }
	build(1,1,n);
	for (int i=1;i<=m;i++){
		int flag;
		scanf("%d",&flag);
		if (flag==1){
			int x,c;
			char ch[5];
			scanf("%d%s",&x,ch);
			if (ch[0]=='I')c=0;
			else c=1;
			update(1,1,n,x,c);
		}
		else{
			int l,r;
			scanf("%d%d",&l,&r);
			printf("%lld\n",query(1,1,n,l,r).ioi);
		}
	}
	return 0;
}