[HAOI2012]高速公路

题目

题目描述

Y901高速公路是一条重要的交通纽带，政府部门建设初期的投入以及使用期间的养护费用都不低，因此政府在这条高速公路上设立了许多收费站。

Y901高速公路是一条由N-1段路以及N个收费站组成的东西向的链，我们按照由西向东的顺序将收费站依次编号为1~N，从收费站i行驶到i+1(或从i+1行驶到i)需要收取Vi的费用。高速路刚建成时所有的路段都是免费的。

政府部门根据实际情况，会不定期地对连续路段的收费标准进行调整，根据政策涨价或降价。

无聊的小A同学总喜欢研究一些稀奇古怪的问题，他开车在这条高速路上行驶时想到了这样一个问题:对于给定的l,r(l<r),在第l个到第r个收费站里等概率随机取出两个不同的收费站a和b，那么从a行驶到b将期望花费多少费用呢?

输入输出格式

输入格式：

第一行2个正整数N,M，表示有N个收费站，M次调整或询问

接下来M行，每行将出现以下两种形式中的一种

C l r v 表示将第l个收费站到第r个收费站之间的所有道路的通行费全部增加v

Q l r 表示对于给定的l,r，要求回答小A的问题

所有C与Q操作中保证1<=l<r<=N

输出格式：

对于每次询问操作回答一行，输出一个既约分数

若答案为整数a，输出a/1

输入输出样例

输入样例#1：

输出样例#1：

1/1
8/3
17/6

说明

所有C操作中的v的绝对值不超过10000

在任何时刻任意道路的费用均为不超过10000的非负整数

所有测试点的详细情况如下表所示

Test	$N$	$M$
$1$	$10$	$10$
$2$	$100$	$100$
$3$	$1000$	$1000$
$4$	$10000$	$10000$
$5$	$50000$	$50000$
$6$	$60000$	$60000$
$7$	$70000$	$70000$
$8$	$80000$	$80000$
$9$	$90000$	$90000$
$10$	$100000$	$100000$

题解

假设期望值为$E$，则$E=\frac{\sum_{i=l}^{r}val_i(i-l+1)(r-i+1)}{\frac{(r-l+1)(r-l+2)}{2}}$

下面的那部分显然是个常数，所以只用看上面部分

$\sum_{i=l}^{r}val_i(i-l+1)(r-i+1)$

拆开括号得：$\sum_{i=l}^{r}val_i(i\times r-i^2+i-l\times r+i\times l-l+r-i+1)$

合并得：$\sum_{i=l}^{r}val_i(i(l+r)-i^2+(r-l-l\times r+1))$

拆开得：$(l+r)\sum_{i=l}^{r}val_i\times i-\sum_{i=l}^{r}val_i\times i^2+(r-l-l\times r+1)\sum_{i=l}^{r}val_i$

显然这个东西可以用线段树维护，维护$val_i,val_i\times i,val_i\times i^2$的区间和即可

代码

# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define tl (k<<1)
# define tr (k<<1|1)
# define mid (l+r>>1)
# define LL long long
using namespace std;
const int MAX=1e5+5;
struct p{
	LL x,_x,__x,tag;
}s[MAX<<2];
int n,m;
LL sum[MAX],_sum[MAX];
char a[5];
int read()
{
	int x=0,fl=1;
	char ch=getchar();
	for(;!isdigit(ch);fl=(ch=='-')?-1:1,ch=getchar());
	for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
	return x*fl;
}
p pus(p b,p c,LL Tag=0)
{
	p a;
	a.tag=Tag,a.x=b.x+c.x,a._x=b._x+c._x,a.__x=b.__x+c.__x;
	return a;
}
void down(int l,int r,int k)
{
	if(!s[k].tag) return;
	LL f=s[k].tag;
	s[k].tag=0,s[tl].tag+=f,s[tr].tag+=f,s[tl].x+=(mid-l+1)*f,s[tr].x+=(r-mid)*f,s[tl]._x+=(sum[mid]-sum[l-1])*f,s[tr]._x+=(sum[r]-sum[mid])*f,s[tl].__x+=(_sum[mid]-_sum[l-1])*f,s[tr].__x+=(_sum[r]-_sum[mid])*f;
}
void change(int l,int r,int k,int L,int R,int dis)
{
	if(l==L&&r==R)
	{
		s[k].x+=1ll*(r-l+1)*dis,s[k]._x+=1ll*(sum[r]-sum[l-1])*dis,s[k].__x+=1ll*(_sum[r]-_sum[l-1])*dis;
		return void(s[k].tag+=dis);
	}
	down(l,r,k);
	if(R<=mid) change(l,mid,tl,L,R,dis);
	else if(L>mid) change(mid+1,r,tr,L,R,dis);
	else change(l,mid,tl,L,mid,dis),change(mid+1,r,tr,mid+1,R,dis);
	s[k]=pus(s[tl],s[tr],s[k].tag);
}
p ask(int l,int r,int k,int L,int R)
{
	if(l==L&&r==R) return s[k];
	down(l,r,k);
	if(R<=mid) return ask(l,mid,tl,L,R);
	if(L>mid) return ask(mid+1,r,tr,L,R);
	return pus(ask(l,mid,tl,L,mid),ask(mid+1,r,tr,mid+1,R));
}
void ASK(int l,int r)
{
	p A=ask(1,n,1,l,r);
	LL L=1ll*(r-l+1)*(r-l+2)>>1,A1=A.x*(r-l-1ll*l*r+1)+(l+r)*A._x-A.__x,Gcd=__gcd(A1,L);
	printf("%lld/%lld\n",A1/Gcd,L/Gcd);
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;++i)
	  sum[i]=sum[i-1]+i,_sum[i]=_sum[i-1]+1ll*i*i;
	for(int i=1,l,r;i<=m;++i)
	  {
	  	scanf("%s",a),l=read(),r=read();
	  	if(a[0]=='C') change(1,n,1,l,r-1,read());
	  	else if(a[0]=='Q') ASK(l,r-1);
	  }
	return 0;
}

题目