记录编号	453414	评测结果	AAAAAAAAAA
题目名称	[HAOI 2012]高速公路	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	1.044 s
提交时间	2017-09-21 15:49:34	内存使用	2.76 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
inline int read(){
	int sum(0),f(1);
	char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar())
		if(ch=='-')
			f=-1;
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum*f;
}
typedef long long L;
L xl[3][100005];
struct data{
	L len;
	L s0,s1,s2;
	data():len(0),s0(0),s1(0),s2(0){}
	inline void add(L w){
//		cout<<"add it in key"<<endl;
//		cout<<"now we find the problem"<<len<<endl;
		s0+=xl[0][len]*w;
		s1+=xl[1][len]*w;
		s2+=xl[2][len]*w;
//		cout<<"add key over"<<endl;
	}
	data operator+(const data &x){
		data ret;
//		cout<<"now we are in the operator "<<len<<' '<<x.len<<endl;
		ret.len=len+x.len;
		ret.s0=s0+x.s0;
		ret.s1=s1+x.s1+len*x.s0;
		ret.s2=s2+x.s2+((len*x.s1)<<1)+len*len*x.s0;
//		cout<<"s0="<<s0<<" x.s0="<<x.s0<<endl;
//		cout<<"s1="<<s1<<" x.s1="<<x.s1<<" len*x.s0="<<len*x.s0<<endl;
//		cout<<"s2="<<s2<<" x.s2="<<x.s2<<" len*x.s1<<1="<<((len*x.s1)<<1)<<" len*len*x.s0="<<len*len*x.s0<<endl;
//		cout<<"now we operate it over "<<ret.len<<' '<<ret.s0<<" "<<ret.s1<<' '<<ret.s2<<endl;
		return ret;
	}
};
struct node{
	int l,r;
	L lazy;
	node *lch,*rch;
	data key;
	node():lazy(0),lch(NULL),rch(NULL){
		key.len=0,key.s0=0,key.s1=0,key.s2=0;
	}
	inline void add(L w){
//		cout<<"now we add it"<<endl;
		key.add(w);
		lazy+=w;
//		cout<<"now we are back"<<endl;
	}
	inline void pushdown(){
//		cout<<"now we pushdown it"<<endl;
		if(lazy){
			if(lch!=NULL)
				lch->add(lazy);
			if(rch!=NULL)
				rch->add(lazy);
			lazy=0;
		}
	}
	inline void pushup(){
		if(lch!=NULL)
			key=lch->key+rch->key;
	}
	inline void update(const int &l,const int &r,const L &w){
//		cout<<l<<" "<<r<<' '<<this->l<<' '<<this->r<<endl;
		if(l<=this->l&&this->r<=r){
//		cout<<"add it?"<<endl;
			this->add(w);
//			cout<<"can we return?"<<endl;
			return;
		}
		this->pushdown();
//		cout<<"non add yet"<<endl;
		int mid((this->l+this->r)>>1);
		if(l<=mid)
			lch->update(l,r,w);
		if(mid<r)
			rch->update(l,r,w);
		this->pushup();
	}
	data query(const int &l,const int &r){
//		cout<<"now we have a query from"<<l<<"to"<<r<<endl;
//		cout<<"check its key"<<key.s0<<" "<<key.s1<<' '<<key.s2<<endl;
		if(l<=this->l&&this->r<=r)
			return this->key;
		this->pushdown();
		int mid((this->l+this->r)>>1);
		if(r<=mid)
			return lch->query(l,r);
		if(mid<l)
			return rch->query(l,r);
		return lch->query(l,r)+rch->query(l,r);
	}
};
int n,m;
inline void play_table(){
//	cout<<"play it"<<endl;
	for(L i=1;i<=n;++i){
		xl[0][i]=xl[0][i-1]+1;
		xl[1][i]=xl[1][i-1]+i;
		xl[2][i]=xl[2][i-1]+i*i;
//		cout<<"now we check the array "<<i<<" "<<xl[0][i]<<' '<<xl[1][i]<<' '<<xl[2][i]<<endl;
	}
}
inline node* build(int l,int r){
//	cout<<"build "<<l<<' '<<r<<endl;
	node *ret=new node();
	ret->l=l,ret->r=r,ret->key.len=r-l+1;
//	cout<<"build it for len"<<ret->key.len<<endl;
	if(l==r)
		return ret;
	int mid((l+r)>>1);
	ret->lch=build(l,mid);
	ret->rch=build(mid+1,r);
	ret->pushup();
	return ret;
}
char op[2];
inline L GCD(L x,L y){
	return x%y?GCD(y,x%y):y;
}
inline void ask(data tmp){
//	cout<<"now we have a ask"<<endl;
//	cout<<tmp.s0<<' '<<tmp.s1<<' '<<tmp.s2<<endl;
	L tp1((tmp.len+1)*tmp.s1-tmp.s2),tp2((tmp.len+1)*tmp.len>>1);
	if(tp1==0){
		printf("0/1\n",0,1);
		return;
	}
	L gcd(GCD(tp1,tp2));
	tp1/=gcd,tp2/=gcd;
	if(tp2<0)
		tp1=-tp1,tp2=-tp2;
	printf("%lld/%lld\n",tp1,tp2);
}
inline int gg(){
	freopen("roadxw.in","r",stdin);
	freopen("roadxw.out","w",stdout);
	n=read(),m=read();
	play_table();
	node *root=build(1,n-1);
//	cout<<"build over"<<endl;
//	if(root->lch==NULL)
//		cout<<"build error"<<endl;
//	cout<<"check what we build"<<endl;
//	for(int i=1;i<n;++i)
//		cout<<"check "<<i<<' '<<(root->query(i,i).s0)<<' '<<(root->query(i,i).s1)<<' '<<(root->query(i,i).s2)<<endl;
	while(m--){
		scanf("%s",op);
		if(op[0]=='C'){
			int x(read()),y(read()),z(read());
			root->update(x,y-1,z);
//			cout<<"update over   now we check the whole tree"<<endl;
//			for(int i=1;i<n;++i)
//				cout<<"check now"<<i<<' '<<(root->query(i,i).s0)<<endl;
//			cout<<"check over";
		}
		else{
			int x(read()),y(read());
			ask(root->query(x,y-1));
		}
	}
	return 0;
}
int K(gg());
int main(){;}