记录编号	491091	评测结果	AAAAAAAAAA
题目名称	[HAOI 2012]高速公路	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	5.448 s
提交时间	2018-03-14 18:18:27	内存使用	10.90 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const long long maxn=500010;
int n,m;
long long ss1,ss2,ss3,s1[maxn],s2[maxn],s3[maxn],lazy[maxn];
long long Gcd(long long x,long long y){
	return y?Gcd(y,x%y):x;
}
void change(int x,long long L,long long R,long long d){
	lazy[x]+=d;
	s1[x]+=(long long)d*(R-L+1);
	s2[x]+=(long long)d*(L+R)*(R-L+1)/2;
	s3[x]+=(long long)d*(R*(R+1)*(2*R+1)-(L-1)*L*(2*L-1))/6;
}
void updata(int x){
	s1[x]=s1[x<<1]+s1[x<<1|1];
	s2[x]=s2[x<<1]+s2[x<<1|1];
	s3[x]=s3[x<<1]+s3[x<<1|1];
}
void downdata(int x,long long L,long long R){
	if(!lazy[x])return;
	long long mid=(L+R)>>1;
	change(x<<1,L,mid,lazy[x]),change(x<<1|1,mid+1,R,lazy[x]);
	lazy[x]=0;
}
void addin(int x,long long l,long long r,long long L,long long R,long long d){
	if(l==L&&R==r){change(x,L,R,d);return;}
	downdata(x,l,r);
	long long mid=(l+r)>>1;
	if(R<=mid)addin(x<<1,l,mid,L,R,d);
	else if(L>=mid+1)addin(x<<1|1,mid+1,r,L,R,d);
	else addin(x<<1,l,mid,L,mid,d),addin(x<<1|1,mid+1,r,mid+1,R,d);
	updata(x);
}
void query(int x,long long l,long long r,long long L,long long R){
	if(l==L&&R==r){
		ss1+=s1[x],ss2+=s2[x],ss3+=s3[x];
		return;
	}
	downdata(x,l,r);
	long long mid=(l+r)>>1;
	if(R<=mid)query(x<<1,l,mid,L,R);
	else if(L>=mid+1)query(x<<1|1,mid+1,r,L,R);
	else query(x<<1,l,mid,L,mid),query(x<<1|1,mid+1,r,mid+1,R);
}
int main(){
	freopen("roadxw.in","r",stdin);
	freopen("roadxw.out","w",stdout);
	scanf("%d%d",&n,&m);
	char op;long long x,y,z;
	while(m--){
		cin>>op>>x>>y;y--;
		if(op=='C'){
			scanf("%lld",&z);
			addin(1,1,n,x,y,z);
		}
		else{
			ss1=ss2=ss3=0;
			query(1,1,n,x,y);
			long long ans=ss1*(y-x-x*y+1)+ss2*(y+x)-ss3;
			if(!ans){printf("0/1\n");continue;}
			long long cnt=(1+y-x)*(y-x+2)/2;
			long long gcd=Gcd(ans,cnt);
			printf("%lld/%lld\n",ans/gcd,cnt/gcd);
		}
	}
	return 0;
}