「Luogu2221」[HAOI2012]高速公路
题目描述
(Y901)高速公路是一条重要的交通纽带，政府部门建设初期的投入以及使用期间的养护费用都不低，因此政府在这条高速公路上设立了许多收费站。
(Y901)高速公路是一条由(N-1)段路以及(N)个收费站组成的东西向的链，我们按照由西向东的顺序将收费站依次编号为(1)~(N)，从收费站(i)行驶到(i+1)(或从(i+1)行驶到(i))需要收取(V_i)的费用。高速路刚建成时所有的路段都是免费的。
政府部门根据实际情况，会不定期地对连续路段的收费标准进行调整，根据政策涨价或降价。
无聊的小(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)操作中保证(1le l < rle 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
Solution
首先非常感谢@GoldenPotato先辈和我一起颓柿子
讲真
这个题除了最终计算答案稍微要用一下期望
跟期望基本没有关系（绝望）
首先，对于每次询问，在区间([l,r])中，任选两个点显然有(C_{r-l+1}^{2})种选法，每种选法的概率都是(frac{1}{C_{r-l+1}^{2}})
令所有选法的长度之和为(sum)，那么答案即为
好了上面就是跟期望有关的部分，现在来看(sum)如何维护
令(v_i)表示收费站(i,i+1)之间的的收费
画图可知，对于每次询问(l,r)，考虑每一段的贡献，有(sum=sum_{i=1}^{r-l}i*(r-l-i+1)*v_{l+i-1})
以(l=2,r=6)为例，那么(sum)即为(1*4*v_2+2*3*v_3+3*2*v_4+4*1*v_5)
显然这玩意很难维护，我们来颓柿子
然而柿子中的各项依然比较难维护，因为每次(l)都是不同的，我们来继续变形
这样我们只需要维护(i*v_i)和(v_i)的区间和即可求出(sum_{i=1}^{r-l}i*v_{l+i-1})
这不禁令我们想到我们是否可以通过维护(i^2*v_i)的区间和来处理剩下的一项
首先经过变形可得((l+i-1)^2=(l-1)^2+(2l-2)i+i^2)
于是有
这样我们就又可以通过维护(i^2*v_i)的区间和求出(sum_{i=1}^{r-l}i^2*v_{l+i-1})推死我了我去
区间修改及区间求和显然可以通过线段树来维护
然而这几个量维护起来也挺恶心的
所以这个题其实是披着期望的外皮，实际上是颓柿子和数据结构的题
实际实现中要注意分清楚点和边的编号
Code
非常丑，慎看
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define maxn 100005
#define maxm 100005
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> void read(T &t)
{
t=0;ull f=0;char c=getchar();
while(!isdigit(c)){f|=c=='-';c=getchar();}
while(isdigit(c)){t=t*10+c-'0';c=getchar();}
if(f)t=-t;
}
ull n,m;
ull gcd(ull a,ull b)
{
return b?gcd(b,a%b):a;
}
inline ull IS(ull l,ull r)//{n}数列区间求和
{
--l;
return (r*(r+1)/2)-(l*(l+1)/2);
}
inline ull QS(ull l,ull r)//{n^2}数列区间求和
{
--l;
return (r*(r+1)*(2*r+1)/6)-(l*(l+1)*(2*l+1)/6);
}
#define lson (num<<1)
#define rson ((num<<1)|1)
struct sgt
{
struct node
{
ull l,r;
ull nons,is,qs,lazy;//vi,i*vi,i^2*vi
}t[maxn<<2];
void Build(ull l,ull r,ull num=1)
{
t[num].l=l;
t[num].r=r;
if(l==r)return;
ull mid=(l+r)>>1;
Build(l,mid,lson);
Build(mid+1,r,rson);
}
void maintain(ull num)
{
t[num].nons=t[lson].nons+t[rson].nons;
t[num].is=t[lson].is+t[rson].is;
t[num].qs=t[lson].qs+t[rson].qs;
}
void pushdown(ull num)
{
ull llen=t[lson].r-t[lson].l+1,rlen=t[rson].r-t[rson].l+1;
t[lson].lazy+=t[num].lazy,t[rson].lazy+=t[num].lazy;
t[lson].nons+=llen*t[num].lazy;
t[rson].nons+=rlen*t[num].lazy;
t[lson].is+=t[num].lazy*IS(t[lson].l,t[lson].r);
t[rson].is+=t[num].lazy*IS(t[rson].l,t[rson].r);
t[lson].qs+=t[num].lazy*QS(t[lson].l,t[lson].r);
t[rson].qs+=t[num].lazy*QS(t[rson].l,t[rson].r);
t[num].lazy=0;
}
void ADD(ull l,ull r,ull x,ull num=1)
{
if(t[num].l>r || t[num].r<l)return;
if(l<=t[num].l && r>=t[num].r)
{
t[num].lazy+=x;
ull len=t[num].r-t[num].l+1;
t[num].nons+=len*x;
t[num].is+=IS(t[num].l,t[num].r)*x;
t[num].qs+=QS(t[num].l,t[num].r)*x;//更新答案部分，至于为什么是这样可以自己推一下
return;
}
pushdown(num);
ADD(l,r,x,lson),ADD(l,r,x,rson);
maintain(num);
}
ull nonsQuery(ull l,ull r,ull num=1)
{
if(t[num].l>r || t[num].r<l)return 0;
if(l<=t[num].l && r>=t[num].r)
return t[num].nons;
pushdown(num);
return nonsQuery(l,r,lson)+nonsQuery(l,r,rson);
}
ull isQuery(ull l,ull r,ull num=1)
{
if(t[num].l>r || t[num].r<l)return 0;
if(l<=t[num].l && r>=t[num].r)
return t[num].is;
pushdown(num);
return isQuery(l,r,lson)+isQuery(l,r,rson);
}
ull qsQuery(ull l,ull r,ull num=1)
{
if(t[num].l>r || t[num].r<l)return 0;
if(l<=t[num].l && r>=t[num].r)
return t[num].qs;
pushdown(num);
return qsQuery(l,r,lson)+qsQuery(l,r,rson);
}
}t;
int main()
{
read(n),read(m);
t.Build(1,n-1);
while(m--)
{
char op=getchar();
while(op!='C' && op!='Q')op=getchar();
if(op=='C')
{
ull l,r;ull x;
read(l),read(r),read(x);
t.ADD(l,r-1,x);
}
else
{
ull l,r;
read(l),read(r);
ull a=t.isQuery(l,r-1)-(l-1)*t.nonsQuery(l,r-1);
ull b=t.qsQuery(l,r-1)-(l-1)*(l-1)*t.nonsQuery(l,r-1)-(2*l-2)*a;
ull fz=a*(r-l+1)-b,fm=(r-l+1)*(r-l)/2,g=gcd(fz,fm);
fz/=g,fm/=g;
printf("%llu/%llu
",fz,fm);
}
}
return 0;
}
一点思考
请忽略以下胡言乱语
我发现这样算的话用(longspace long)是会豹的（捂脸）
所以我干脆把所有变量都改成(unsignedspace longspace long)
至于为什么在负数存在的情况下是正确的
如果使用(ull)，实际上就是在模(2^{64}-1)的意义下做运算，而最终答案是在(ll)范围内的，并且为正整数
所以就阔以啦