记录编号	366208	评测结果	AAAAAAAAAA
题目名称	[HAOI 2012]高速公路	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	5.365 s
提交时间	2017-01-23 11:04:32	内存使用	26.01 MiB

#include<cstdio>
typedef long long ll;
const int N=5e5+10;
int n,m,son[N][2],tag[N],v[N],fa[N],Root;
ll S[N],S1[N],S2[N],SV[N],s[N];
#define lc son[x][0]
#define rc son[x][1]
inline void update(int x){//暴力(求导)出奇迹 
	s[x]=s[lc]+s[rc]+1;
	SV[x]=SV[lc]+v[x]+SV[rc];
	S1[x]=S1[lc]+(s[lc]+1)*(v[x]+SV[rc])+S1[rc];
	S2[x]=S2[lc]+(s[rc]+1)*SV[lc]+v[x]*s[rc]+S2[rc];
	S[x]=S[lc]+(s[rc]+1)*S1[lc]+(s[lc]+1)*s[rc]*v[x]+S[rc]+S2[rc]*(s[lc]+1);
}
inline void update(int x,ll Tag){
	v[x]+=Tag;
	tag[x]+=Tag;
	SV[x]+=Tag*s[x];
	S1[x]+=Tag*(s[x]+1)*s[x]/2;
	S2[x]+=Tag*(s[x]-1)*s[x]/2;
	S[x]+=Tag*s[x]*(s[x]*s[x]-1)/6;
}
inline void pushdown(int x){
	if (x&&tag[x]){
		update(lc,tag[x]);
		update(rc,tag[x]);
		tag[x]=tag[0]=0;
	}
}
inline void rot(int x){
	int y=fa[x],z=fa[y];
	bool b=(x==son[y][1]);
	fa[son[y][b]=son[x][!b]]=y;
	fa[son[x][!b]=y]=x;
	fa[x]=z;
	if (y==son[z][0]) son[z][0]=x;else
	if (y==son[z][1]) son[z][1]=x;
	update(y);
	update(x);
}
inline void splay(int x){
	pushdown(x);
	while (fa[x]){
		int y=fa[x],z=fa[y];
		pushdown(z);pushdown(y);pushdown(x);
		if (!fa[y]||!fa[z]){rot(x);continue;}
		if (x==son[y][0]) rot(y==son[z][0]?y:x);
			else rot(y==son[z][1]?y:x);
		rot(x);
	}
	Root=x;
}
inline void find(int key){
	int x=Root;
	while (1){
		int i=s[lc]+1;
		if (key==i) break;
		if (key>i) x=rc,key-=i;
			else x=lc;
	}
	splay(x);
}
char ch[5];int l,r,d;
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
int read(){
	int x=0;bool sign=1;char ch=getchar();
	while ((ch>'9'||ch<'0')&&ch!='-') ch=getchar();
	if (ch=='-') sign=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return sign?x:-x;
}
int main()
{
	freopen("roadxw.in","r",stdin);
	freopen("roadxw.out","w",stdout);
	scanf("%d%d",&n,&m);
	//初始化splay 
	Root=1;
	for (int i=1;i<n+2;i++) fa[son[i][1]=i+1]=i;
	for (int i=1;i<=n+2;i++) s[i]=n+3-i;
	//求解 
	while (m--){
		scanf("%s",ch);l=read();r=read();
		if (ch[0]=='C') r--;
		find(l);find(r+2);
		int le=son[Root][0],th=son[le][1];
		if (ch[0]=='C'){
			update(th,read());
			update(le);
			update(Root);
		}
		else{
			ll s=r-l+1,fz=S[th],fm=s*(s-1)/2,d=gcd(fm,fz);
			fz/=d;fm/=d;
			printf("%lld/%lld\n",fz,fm);
		}
	}
	return 0;
}