https://www.luogu.org/problem/show?pid=2221
题目描述
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：
4 5
C 1 4 2
C 1 2 -1
Q 1 2
Q 2 4
Q 1 4
输出样例#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 期望值= Σ 可能情况*出现概率
因为所有概率相等，所以本题可以转化为求 子集和/子集个数
根据组合数，子集个数=C（r-l+1,2）= （r-l+1）*（r-l）/2
子集和呢
推公式
子集和=Σ (i-l+1)*(r-i+1)*cost[i]
其中，(i-l+1)*(r-i+1) 是每个数用到的次数
拆开，= (l+r)* Σ i*cost[i] + (r-l+1-l*r) * Σ cost[i] - Σ i*i*cost[i]
线段树维护 Σcost[i] ，Σ i*cost[i]，Σ i*i*cost[i]
更新，以+w为例：Σcost[i] 加了size 个w，所以Σcost[i] +=size*w
Σ i*cost[i] 加了 szie 个Σ i，所以Σ i*cost[i] += size*Σ i
Σ i*i*cost[i] 加了 size个 Σ i*i，所以Σ i*i*cost[i] += size *Σ i*i
所以线段树需要另外维护 Σi，Σi*i
#include<cstdio>
#define N 100001
using namespace std;
int n,m,opl,opr,w;
long long ans1,ans2,ans3;
long long fz,fm,g;
struct node
{
long long i,a,ia,ii,iia,f;
int mid;
}e[N<<];
long long gcd(long long c,long long d) { return !d ? c : gcd(d,c%d); }
void build(int k,int l,int r)
{
if(l==r)
{
e[k].i=l; e[k].ii=1ll*l*l;
return;
}
e[k].mid=l+r>>;
build(k<<,l,e[k].mid);
build(k<<|,e[k].mid+,r);
e[k].i=e[k<<].i+e[k<<|].i;
e[k].ii=e[k<<].ii+e[k<<|].ii;
}
void down(int k,int l,int r)
{
int fl=e[k].f; e[k].f=;
e[k<<].f+=fl;
e[k<<].a+=1ll*fl*(e[k].mid-l+);
e[k<<].ia+=1ll*fl*e[k<<].i;
e[k<<].iia+=1ll*fl*e[k<<].ii;
e[k<<|].f+=fl;
e[k<<|].a+=1ll*fl*(r-e[k].mid);
e[k<<|].ia+=1ll*fl*e[k<<|].i;
e[k<<|].iia+=1ll*fl*e[k<<|].ii;
}
void change(int k,int l,int r)
{
if(l>=opl &&r<=opr)
{
e[k].a+=1ll*w*(r-l+);
e[k].ia+=1ll*w*e[k].i;
e[k].iia+=1ll*w*e[k].ii;
e[k].f+=w;
return;
}
if(e[k].f) down(k,l,r);
if(opl<=e[k].mid) change(k<<,l,e[k].mid);
if(opr>e[k].mid) change(k<<|,e[k].mid+,r);
e[k].a=e[k<<].a+e[k<<|].a;
e[k].ia=e[k<<].ia+e[k<<|].ia;
e[k].iia=e[k<<].iia+e[k<<|].iia;
}
void query(int k,int l,int r)
{
if(l>=opl && r<=opr)
{
ans1+=e[k].ia;
ans2+=e[k].a;
ans3+=e[k].iia;
return;
}
if(e[k].f) down(k,l,r);
if(opl<=e[k].mid) query(k<<,l,e[k].mid);
if(opr>e[k].mid) query(k<<|,e[k].mid+,r);
}
void read(int &x)
{
x=; int f=; char c=getchar();
while(c<'' || c>'') { if(c=='-') f=-; c=getchar(); }
while(c>='' && c<='') { x=x*+c-''; c=getchar(); }
x*=f;
}
int main()
{
read(n); read(m);
build(,,n-);
char s[];
while(m--)
{
scanf("%s",s);
if(s[]=='C')
{
read(opl); read(opr); read(w);
opr--;
change(,,n-);
}
else
{
read(opl); read(opr);
opr--;
ans1=ans2=ans3=;
query(,,n-);
fz=(opl+opr)*ans1+(1ll*opr-opl+-1ll*opl*opr)*ans2-ans3;
fm=1ll*(opr-opl+)*(opr-opl+)/;
g=gcd(fz,fm);
fz/=g; fm/=g;
printf("%lld/%lld\n",fz,fm);
}
}
}