高速公路[线段树]

传送门


 

#include<bits/stdc++.h>
#define N 100050
#define LL long long
#define len(x) (t[x].r-t[x].l+1)
using namespace std;
struct Node{LL l,r,tag,sum1,sum2,sum3;}t[N<<2];
LL n,m; char s[3];
LL read(){
	LL cnt=0,f=1;char ch=0;
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch))cnt=cnt*10+(ch-'0'),ch=getchar();
	return cnt*f;
}
LL gcd(LL x,LL y){return !y?x:gcd(y,x%y);}
void build(LL x,LL l,LL r){
	t[x].l=l,t[x].r=r; if(l==r) return; LL mid=(l+r)>>1; 
	build(x<<1,l,mid),build(x<<1|1,mid+1,r);
}
LL calc(LL x){return x*(x+1)*(x*2+1)/6;}
void Pushup(LL x){
	t[x].sum1 = t[x<<1].sum1 + t[x<<1|1].sum1;
	t[x].sum2 = t[x<<1].sum2 + t[x<<1|1].sum2;
	t[x].sum3 = t[x<<1].sum3 + t[x<<1|1].sum3;
}
void Pushdown(LL x){
	if(t[x].tag){
		LL val = t[x].tag;
		t[x<<1].sum1 += val*len(x<<1);
		t[x<<1|1].sum1 += val*len(x<<1|1);
		t[x<<1].sum2 += val * len(x<<1) * (t[x<<1].l+t[x<<1].r)/2;
		t[x<<1|1].sum2 += val * len(x<<1|1) * (t[x<<1|1].l+t[x<<1|1].r)/2;
		t[x<<1].sum3 += val * (calc(t[x<<1].r) - calc(t[x<<1].l-1));
		t[x<<1|1].sum3 += val * (calc(t[x<<1|1].r) - calc(t[x<<1|1].l-1));
		t[x<<1].tag += val;
		t[x<<1|1].tag += val;
		t[x].tag=0;
	}
}
void Modify(LL x,LL L,LL R,LL val){
	if(L<=t[x].l && t[x].r<=R){
		t[x].sum1 += val * len(x);
		t[x].sum2 += val * len(x) * (t[x].l+t[x].r) / 2;
		t[x].sum3 += val * (calc(t[x].r) - calc(t[x].l-1));
		t[x].tag += val;
		return;
	}
	Pushdown(x); 
	LL mid=(t[x].l+t[x].r)>>1;
	if(L<=mid) Modify(x<<1,L,R,val);
	if(R>mid) Modify(x<<1|1,L,R,val);
	Pushup(x);
}
void Ask(LL x,LL L,LL R,LL &x1,LL &x2,LL &x3){
	if(L<=t[x].l && t[x].r<=R){
		x1 += t[x].sum1 , x2 += t[x].sum2 , x3 += t[x].sum3;
		return;
	}
	Pushdown(x);
	LL mid=(t[x].l+t[x].r)>>1;
	if(L<=mid) Ask(x<<1,L,R,x1,x2,x3);
	if(R>mid) Ask(x<<1|1,L,R,x1,x2,x3);
}
LL Quary(LL L,LL R){
	LL Sum1=0 , Sum2=0 , Sum3=0;
	Ask(1,L,R,Sum1,Sum2,Sum3);
	return -(L*R+L-R-1)*Sum1 + (L+R) * Sum2 - Sum3;
}
int main(){
	n=read(),m=read(); build(1,1,n-1);
	for(LL i=1;i<=m;i++){
		scanf("%s",s); LL x=read(),y=read()-1;
		if(s[0]=='C') Modify(1,x,y,read());
		if(s[0]=='Q'){
			LL X=Quary(x,y),Y=(y-x+1)*(y-x+2)/2;
			LL G=gcd(X,Y); 
			printf("%lld/%lld\n",X/G,Y/G);
		}
 	}return 0;
}