C++ 解法, 执行用时: 228ms, 内存消耗: 15220K, 提交时间: 2021-08-23 17:29:19

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
const ll INF=1ll<<61;
char s[N];
int pos[N];
struct node
{
	int l,r;
	ll m[2][2];
	
	node operator*(const node x)const
	{
		node ret;
		ret.l=l;
		ret.r=x.r;
		for(int i=0;i<2;i++)
		{
			for(int j=0;j<2;j++)
			{
				ret.m[i][j]=INF;
				for(int k=0;k<2;k++)
				{
					ret.m[i][j]=min(ret.m[i][j],m[i][k]+x.m[k][j]);
				}
			}
		}
		return ret;
	}
}t[N<<2];
void pushup(int k)
{
	t[k]=t[k<<1]*t[k<<1|1];
}
void f(int k,ll v0,ll v1,ll v2,ll v3)
{
	t[k].m[0][0]=v0;
	t[k].m[0][1]=v1;
	t[k].m[1][0]=v2;
	t[k].m[1][1]=v3;
}
ll v0[N],v1[N],v2[N];
void build(int k,int l,int r)
{
	t[k].l=l;t[k].r=r;
	if(l==r)
	{
		pos[l]=k;
		if(s[l]=='/')f(k,v0[l],v2[l],INF,v1[l]);
		else f(k,v0[l],INF,v2[l],v1[l]);
		return ;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	pushup(k);
}
void update(int k)
{
	int root=pos[k];
	if(s[k]=='/')f(root,v0[k],v2[k],INF,v1[k]);
	else f(root,v0[k],INF,v2[k],v1[k]);
	while(root>>=1)pushup(root);
}
node query(int k,int l,int r)
{
	if(l<=t[k].l&&t[k].r<=r)
	{
		return t[k];
	}
	int mid=(t[k].l+t[k].r)>>1;
	if(r<=mid)return query(k<<1,l,r);
	else if(l>mid)return query(k<<1|1,l,r);
	else return query(k<<1,l,r)*query(k<<1|1,l,r);
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	scanf("%s",s+1);
	for(int i=1;i<n;i++)
	{
		scanf("%lld%lld%lld",&v0[i],&v1[i],&v2[i]);
	}
	build(1,1,n);
	int hs,ht,ps,pt,op,x;
	char c[5];
	while(m--)
	{
		scanf("%d",&op);
		if(op==2)
		{
			scanf("%d%d%d%d",&hs,&ht,&ps,&pt);
			ll ans=query(1,hs,ht-1).m[ps][pt];
			if(ans==INF)ans=-1;
			printf("%lld\n",ans);
		}
		else 
		{
			if(op==0)
			{
				scanf("%d",&x);
				scanf("%s",c);
				s[x]=c[0];
			}
			else 
			{
				scanf("%d",&x);
				scanf("%lld%lld%lld",&v0[x],&v1[x],&v2[x]);
			}
			update(x);
		}
	}
	return 0;
}