记录编号	272577	评测结果	AAAAAAAAAA
题目名称	[HAOI 2012]高速公路	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	6.516 s
提交时间	2016-06-17 15:23:31	内存使用	0.31 MiB

#include<stdio.h>
#include<stdlib.h>
#define ll long long
ll GCD(ll a,ll b){
	for(ll c;b;c=b,b=a%b,a=c);
	return a;
}
struct node{
	node*l,*r;
	int fix;
	ll val,ans,sum,lsum,rsum,size,tag;
	node(){val=ans=sum=lsum=rsum=tag=0,fix=rand(),size=1,l=r=NULL;}
	ll lsize(){return l?l->size:0;}
	ll rsize(){return r?r->size:0;}
	void update(){
		if(l)l->pushdown();
		if(r)r->pushdown();
///////////////update ans///////////////
		ans=(lsize()+1)*(rsize()+1)*val;
		if(l)ans+=l->ans,ans+=l->rsum*(rsize()+1);
		if(r)ans+=r->ans,ans+=r->lsum*(lsize()+1);
///////////////update sum///////////////
		sum=val;
		if(l)sum+=l->sum;
		if(r)sum+=r->sum;
///////////////update lsum//////////////
		if(l)lsum=l->lsum+(l->sum+val)*(rsize()+1)+(r?r->lsum:0);
		else lsum=val*(rsize()+1)+(r?r->lsum:0);
///////////////update rsum//////////////
		if(r)rsum=r->rsum+(r->sum+val)*(lsize()+1)+(l?l->rsum:0);
		else rsum=val*(lsize()+1)+(l?l->rsum:0);
///////////////update size//////////////
		size=1+lsize()+rsize();
	}
	void pushdown(){
/////////////pushdown val///////////////
		val+=tag;
/////////////pushdown ans///////////////
		ans+=tag*size*(size+1)*(size+2)/6;
/////////////pushdown sum///////////////
		sum+=tag*size;
/////////////pushdown lsum//////////////
		lsum+=tag*size*(size+1)>>1;
/////////////pushdown rsum//////////////
		rsum+=tag*size*(size+1)>>1;
/////////////pushdown tag///////////////
		if(l)l->tag+=tag;
		if(r)r->tag+=tag;
		tag=0;
	}
}*rt;
struct pair{node*x,*y;};
void build(int l,int r,node*&x){
	x=new node();
	if(l>=r)return;
	int mid=l+r>>1;
	build(l,mid-1,x->l);
	build(mid+1,r,x->r);
	x->update();
}
node*merge(node*&a,node*&b){
	if(!a)return b;
	if(!b)return a;
	if(a->fix<b->fix){
		a->pushdown();
		a->r=merge(a->r,b);
		a->update();
		return a;
	}else{
		b->pushdown();
		b->l=merge(a,b->l);
		b->update();
		return b;
	}
}
pair split(node*&x,int k){
	if(!k)return (pair){NULL,x};
	pair y;x->pushdown();
	if(x->lsize()>=k){
		y=split(x->l,k);
		x->l=y.y,x->update();
		y.y=x;
	}else{
		y=split(x->r,k-x->lsize()-1);
		x->r=y.x,x->update();
		y.x=x;
	}return y;
}
char ch[2];
int n,m;
int main(){
	freopen("roadxw.in","r",stdin);
	freopen("roadxw.out","w",stdout);
	scanf("%d%d",&n,&m);
	build(1,n-1,rt);
	for(int l,r,x;m--;){
		scanf("%s",ch);
		if(*ch=='C'){
			scanf("%d%d%d",&l,&r,&x);
			pair a=split(rt,r-1);
			pair b=split(a.x,l-1);
			b.y->tag+=x;
			a.x=merge(b.x,b.y);
			rt=merge(a.x,a.y);
		}else{
			scanf("%d%d",&l,&r);
			pair a=split(rt,r-1);
			pair b=split(a.x,l-1);
			b.y->pushdown();
			ll A=b.y->ans,B=b.y->size,gcd;
			B=B*(B+1)>>1;
			gcd=GCD(A,B);
			printf("%lld/%lld\n",A/gcd,B/gcd);
			a.x=merge(b.x,b.y);
			rt=merge(a.x,a.y);
		}
	}
//	while(1);
}