2752: [HAOI2012]高速公路(road)
Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 2102 Solved: 887
[Submit][Status][Discuss]
Description
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将期望花费多少费用呢?
Input
第一行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
Output
对于每次询问操作回答一行，输出一个既约分数
若答案为整数a，输出a/1
Sample Input
C 1 4 2
C 1 2 -1
Q 1 2
Q 2 4
Q 1 4
Sample Output
8/3
17/6
HINT
数据规模
所有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
这道题所有操作都是对边进行的，所以我们化点编号为边编号，询问时将$Q_r--$。
一眼看出这应该是假期望，真正所求为
$\frac{\sum \limits_{i=l}^r \sum \limits_{j=l}^r dis[i][j]}{C_{r-l+1}^{2}}$
不要忘了我们已经将化点为边了，所以其实是
$\frac{\sum \limits_{i=l}^r \sum \limits_{j=l}^r dis[i][j]}{C_{r-l+2}^{2}}$
分母很好算，即$\frac {(r-l+2)(r-l+1)}{2}$
分子是需要我们维护的，但这种形式令我们无从下手。所以尝试换一种思路表示它。
对于每一段路，向左向右分别考虑它被经过的次数：
$\sum \limits_{i=l}^r{a[i]*(r-i+1)(i-l+1)}$
我们令$sum_1=\sum \limits_{i=l}^{r}{a[i]}$
$sum_2=\sum \limits_{i=l}^{r}{a[i]*i}$
$sum_3=\sum \limits_{i=l}^{r}{a[i]*i^2}$
把$\sum$拆开，化简一下得到$(r-l+1-r*l)*sum_1+(r+l)*sum_2-sum_3$
然后这三个$sum$用线段树维护的话左右儿子合并直接相加就行了，
但是本题还需要区间修改
对于$sum_1$,直接按照普通线段树区间加数的方式修改，区间长度乘上值
对于$sum_2$,我们需要对区间加上$val*\sum i$,这个建树时处理一下区间和即可
对于$sum_3$,我们需要对区间加上$val*\sum i^2$，类似于上面直接建树时处理
（所谓建树时处理，就是建树$l,r$重合时存进去就行了）
出题人真是毒瘤……第一次用$define\ int\ ll$这么粗糙的方式……
对于性质类似的变量，以数组形式存储、for循环更新能大幅减少代码长度和调试难度。
另外，输出答案时需要求gcd约分一下。
完结撒花！
#include<cstdio>
#include<iostream>
#include<cstring>
#define ls(k) k<<1
#define rs(k) k<<1|1
const int N=;
typedef long long ll;
#define int ll
int n,m;
ll gcd(ll x,ll y){while(y^=x^=y^=x%=y);return x;}
ll read()
{
ll x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();
return x*f;
}
int lsd[N<<],rsd[N<<];
ll sum[N<<][],lz[N<<],ans[];
void update(int k)
{
for(int i=;i<=;i++)
sum[k][i]=sum[ls(k)][i]+sum[rs(k)][i];
return ;
}
void build(int k,int l,int r)
{
lsd[k]=l,rsd[k]=r;
if(l==r)
{
sum[k][]=l*l;
sum[k][]=l;
return ;
}
int mid=l+r>>;
build(ls(k),l,mid);
build(rs(k),mid+,r);
for(int i=;i<=;i++)
sum[k][i]=sum[ls(k)][i]+sum[rs(k)][i];
return ;
}
void pdown(int k,ll val)
{
sum[k][]+=1LL*(rsd[k]-lsd[k]+)*val;
sum[k][]+=val*sum[k][];
sum[k][]+=val*sum[k][];
lz[k]+=val;
return ;
}
void down(int k)
{
pdown(ls(k),lz[k]);
pdown(rs(k),lz[k]);
lz[k]=;
return ;
}
void change(int k,int L,int R,ll val)
{
if(lsd[k]>=L&&rsd[k]<=R)
{
pdown(k,val);
return ;
}
if(lz[k])down(k);
int mid=lsd[k]+rsd[k]>>;
if(mid>=L)change(ls(k),L,R,val);
if(mid<R)change(rs(k),L,R,val);
update(k);
return ;
}
void query(int k,int L,int R)
{
if(lsd[k]>=L&&rsd[k]<=R)
{
for(int i=;i<=;i++)
ans[i]+=sum[k][i];
return ;
}
if(lz[k])down(k);
int mid=lsd[k]+rsd[k]>>;
if(mid>=L)query(ls(k),L,R);
if(mid<R)query(rs(k),L,R);
return ;
}
signed main()
{
n=read();m=read();
build(,,n);char op[];
int ql,qr;
while(m--)
{
scanf("%s",op);
ql=read();qr=read()-;
if(op[]=='C')
{
int val=read();
change(,ql,qr,val);
}
else
{
for(int i=;i<=;i++)ans[i]=;
query(,ql,qr);
ll res=1LL*(qr-ql+-qr*ql)*ans[]+1LL*(qr+ql)*ans[]-ans[];
ll mot=1LL*(qr-ql+)*(qr-ql+)/,GCD=gcd(res,mot);
res/=GCD;mot/=GCD;
printf("%lld/%lld\n",res,mot);
}
}
return ;
}