记录编号	158163	评测结果	AAAAAAAAAA
题目名称	[HAOI 2012]高速公路	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	2.391 s
提交时间	2015-04-13 07:45:22	内存使用	2.60 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define Nil NULL
typedef long long LL;
const int SIZEN=100010;
LL gcd(LL a,LL b){return !b?a:gcd(b,a%b);}
LL series_pref[3][SIZEN];
class Data{
public:
	LL n;
	LL S0,S1,S2;
	Data(){n=S0=S1=S2=0;}
	//S0是和
	//S1是1*a1+2*a2+...
	//S2是1*1*a1+2*2*a2+...
	void alladd(LL w){
		S0+=series_pref[0][n]*w;
		S1+=series_pref[1][n]*w;
		S2+=series_pref[2][n]*w;
	}
};
void print(Data D){
	cout<<"("<<D.n<<" "<<D.S0<<" "<<D.S1<<" "<<D.S2<<")";
}
Data operator + (const Data &a,const Data &b){
	Data c;
	c.n=a.n+b.n;
	c.S0=a.S0+b.S0;
	c.S1=a.S1+(b.S1+a.n*b.S0);
	c.S2=a.S2+(b.S2+2*a.n*b.S1+a.n*a.n*b.S0);
	return c;
}
class Node{
public:
	int l,r;
	Node *lc,*rc;
	Data key;
	int lazy;
	Node(){lazy=0;lc=rc=Nil;}
	void alladd(LL w){
		key.alladd(w);
		lazy+=w;
	}
	void push_down(void){
		if(lazy){
			if(lc!=Nil) lc->alladd(lazy);
			if(rc!=Nil) rc->alladd(lazy);
			lazy=0;
		}
	}
	void push_up(void){
		if(lc!=Nil){
			key=lc->key+rc->key;
		}
	}
	void modify(const int &a,const int &b,const LL &w){
		push_down();
		if(l>b||r<a) return;
		if(l>=a&&r<=b){
			alladd(w);
			return;
		}
		if(lc!=Nil) lc->modify(a,b,w);
		if(rc!=Nil) rc->modify(a,b,w);
		push_up();
	}
	Data query(const int &a,const int &b){
		push_down();
		if(l>b||r<a) return Data();
		if(l>=a&&r<=b) return key;
		return lc->query(a,b)+rc->query(a,b);
	}
};
Node* build(int l,int r){
	Node *ans=new Node;
	ans->l=l,ans->r=r;
	ans->key.n=r-l+1;
	if(l<r){
		int mid=(l+r)/2;
		ans->lc=build(l,mid);
		ans->rc=build(mid+1,r);
		ans->push_up();
	}
	return ans;
}
void answer(const Data &D){
	LL p=(D.n+1)*D.S1-D.S2;
	LL q=(D.n+1)*D.n/2;
	LL g=gcd(p,q);
	p/=g,q/=g;
	printf("%lld/%lld\n",p,q);
}
void prepare(void){
	series_pref[0][0]=series_pref[1][0]=series_pref[2][0]=0;
	for(int i=1;i<SIZEN;i++){
		series_pref[0][i]=series_pref[0][i-1]+1;
		series_pref[1][i]=series_pref[1][i-1]+i;
		series_pref[2][i]=series_pref[2][i-1]+i*i;
	}
}
int N,M;
int main(){
	freopen("roadxw.in","r",stdin);
	freopen("roadxw.out","w",stdout);
	prepare();
	scanf("%d %d\n",&N,&M);
	Node *root=build(1,N-1);
	char cmd;
	LL a,b,w;
	for(int i=1;i<=M;i++){
		scanf("%c ",&cmd);
		if(cmd=='C'){
			scanf("%lld %lld %lld\n",&a,&b,&w);
			root->modify(a,b-1,w);
		}
		else if(cmd=='Q'){
			scanf("%lld %lld\n",&a,&b);
			answer(root->query(a,b-1));
		}
	}
	return 0;
}