[HAOI2012]高速公路

传送门

题解

由于每种选择概率是一样的，那么答案显然=每种选择费用和/选择方案数，那么我们只需要计算每种选择费用和就好了。

考虑第i段路（经过费用\(V_i\)）对答案的贡献。

假设询问区间是l,r，经过这段路的方案数\(=(i-l+1)(r-i)=(l-1+r)i-i^2-r(l-1)\)，贡献显然就是\(((l-1+r)i-i^2-r(l-1))V_i\)，答案就是\(\sum\limits_{i=l}^{r-1}(((l-1+r)i-i^2-r(l-1))V_i)=(l-1+r)\sum\limits_{i=l}^{r-1}iV_i-\sum\limits_{i=l}^{r-1}i^2-r(l-1)\sum\limits_{i=l}^{r-1}V_i\)，线段树维护即可。

/*
Author: CNYALI_LK
LANG: C++
PROG: 2221.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<ll,ll> pii;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll read(){
	ll s=0,base=1;
	char c;
	while(!isdigit(c=getchar()))if(c=='-')base=-base;
	while(isdigit(c)){s=s*10+(c^48);c=getchar();}
	return s*base;
}
ll rdc(){
	char c;
	while(!isalpha(c=getchar()));
	return c=='Q';
}
ll sum[3][102424];
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
struct smt{
	ll s[3],add,ls,rs;
	smt *l,*r;
	void push_up(){
		for(ll i=0;i<3;++i)s[i]=l->s[i]+r->s[i];
	}
	void put_tag(ll x){
		if(x){
			add+=x;
			for(ll i=0;i<3;++i)s[i]+=x*(sum[i][rs]-sum[i][ls-1]);
		}
	}
	void push_down(){
		l->put_tag(add);
		r->put_tag(add);
		add=0;
	}
	smt(ll la,ll ra){
		ls=la;rs=ra;
		add=0;
		s[0]=s[1]=s[2]=0;
		if(la==ra){l=r=0;}
		else {
			ll mid=(la+ra)>>1;
			l=new smt(la,mid);
			r=new smt(mid+1,ra);
		}
	}
	void Add(ll la,ll ra,ll w){
		if(la<=ls&&rs<=ra)put_tag(w);
		else{
			push_down();
			if(la<=l->rs)l->Add(la,ra,w);
			if(r->ls<=ra)r->Add(la,ra,w);
			push_up();
		}
	}
	ll Sum(ll w,ll la,ll ra){
		if(la<=ls&&rs<=ra)return s[w];
		else{
			push_down();
			ll ans=0;
			if(la<=l->rs)ans+=l->Sum(w,la,ra);
			if(r->ls<=ra)ans+=r->Sum(w,la,ra);
			return ans;
		}
	}
}*rt;
int main(){
#ifdef cnyali_lk
	freopen("2221.in","r",stdin);
	freopen("2221.out","w",stdout);
#endif
	ll n,m,l,r,v,s1,s2,s0,s,t,g;
	n=read();m=read();
	for(ll i=1;i<=n;++i){
		sum[0][i]=sum[0][i-1]+1;
		sum[1][i]=sum[1][i-1]+i;
		sum[2][i]=sum[2][i-1]+i*i;
	}
	rt=new smt(1,n-1);
	for(;m;--m){
		if(rdc()){
			l=read();r=read();
			s0=rt->Sum(0,l,r-1);
			s1=rt->Sum(1,l,r-1);
			s2=rt->Sum(2,l,r-1);
			--l;
			s=s1*(r+l)-l*r*s0-s2;
			t=(r-l)*(r-l-1)>>1;
			g=gcd(s,t);
			printf("%lld/%lld\n",s/g,t/g);
		}	
		else{
			l=read();r=read();
			v=read();
			rt->Add(l,r-1,v);
		}
	}
	return 0;
}