传送门: COGS
实际上, 拿到这道题我是懵逼的. 第一感觉是线段树维护路径费用, 然后就没了.
实际上, 好好想一想, 应该还是可以发现一些玄机的.
用线段树维护公路权值是个人都会吧, 不会右转幼儿园.
但是下面期望值怎么算?
想想教练讲的, 期望就是加权平均数, 那么对于区间 L--R 的期望实际上就是
这是分子
分母自然是(R-L+1)*(R-L)/2
但是好像这个鬼东西不能用正常的线段树来求啊.
那要想个办法, 能不能给他拆开?
考虑一下对于区间 [L,R] 的期望, 实际上某一段路一共被算了几次?
对于第 L 段路, 自然是 (R-L+1) 次, 第 L+1 段则是(R-L)+(R-L)// 两次都是从 L+1 开始数到 R
第 L+2 段路呢?(R-L-1)*3// 三次都是从 L+2 开始数到 R, 那么这个时候是不是可以发现什么?
则有:
但是好像还不能用线段树啊, 那就继续拆
考虑把后面的一坨式子合成一个, 我们可以得到
现在是不是可以发现什么了?
整个表达式可以分为三部分, 有一项为 1 的, 有一项为 i 的, 有一项为 i*i 的, 因为还要参与区间修改, 而且 L 和 R 在一次查询中可以视为常数, 那么是不是可以分别维护表达式的三部分?
假定维护 sum1,sum2,sum3,sum1 维护区间内所有 a[i]之和, sum2 维护所有 a[i]*i 之和, sum3 维护所有 a[i]*i*i 之和
现在怎么进行区间修改?
众所周知, 乘法满足分配律,(x+y)z=xz+yz, 而且因为对于一段路, i 固定, 那么我们是否可以再加两个辅助量, sum4,sum5, 分别作为区间内所有 i 的和, 所有 i*i 的和?
正确性: 假定现在为区间内所有元素 + w, 那么 sum1=sum1 + 区间长度 * w,sum2=sum2+sum4*w = 所有的(a[i]+w)* 所有的 i = 所有的 a[i]* 所有的 i+w * 所有的 i, 对于 sum3 同理.
那么, 我们就可以愉快的维护一个含有 5 个元素的线段树了, 最终的期望答案就是 sum1*(R-L-LR+1)+sum2*(L+R)-sum3, 然后除去前面算好的分母即可.
注意, 此题细节问题很多, 代码中的注释几乎都是调试时输出的辅助量, 用来判断程序某一部分的正确性的.
补一句, 这一题给出的区间是收费站, 也就是端点, 但是为了应用线段树, 手动将左边界 ++ 即可(相当于每个区间的序号是自己右边的收费站)
代码:
- #include<iostream>
- #include<cstdio>
- #include<vector>
- #define int long long int
- using namespace std;
- struct PE
- {
- int lazy,sum1,sum2,sum3,sum4,sum5,l,r;
- //sum1=∑a[i]
- //sum2=∑a[i]*i
- //sum3=∑a[i]*i*i
- //sum4=∑i;
- //sum5=∑i*i;
- //4,5 用于更新 2,3
- };
- PE t[400001];
- int a[100001];
- int n,m,a1,a2,a3;
- char xd;
- int ls(int x)
- {
- return x<<1;
- }
- int rs(int x)
- {
- return x<<1|1;
- }
- void pushup(int x)
- {
- t[x].sum1=t[ls(x)].sum1+t[rs(x)].sum1;
- t[x].sum2=t[ls(x)].sum2+t[rs(x)].sum2;
- t[x].sum3=t[ls(x)].sum3+t[rs(x)].sum3;
- t[x].l=t[ls(x)].l;
- t[x].r=t[rs(x)].r;
- }
- void build(int x,int l,int r)
- {
- if(l==r)
- {
- t[x].sum1=a[l];
- t[x].sum2=a[l]*l;
- t[x].sum3=a[l]*l*l;
- t[x].sum4=l;
- t[x].sum5=l*l;
- t[x].lazy=0;
- t[x].l=t[x].r=l;
- return ;
- }
- int mid=(l+r)>>1;
- build(ls(x),l,mid);
- build(rs(x),mid+1,r);
- t[x].sum4=t[ls(x)].sum4+t[rs(x)].sum4;
- t[x].sum5=t[ls(x)].sum5+t[rs(x)].sum5;
- pushup(x);
- }
- void pushdown(int x,int l,int r)
- {
- int mid=(l+r)>>1;
- if(t[x].lazy)
- {
- t[ls(x)].lazy+=t[x].lazy;
- t[rs(x)].lazy+=t[x].lazy;
- t[ls(x)].sum1+=(mid-l+1)*t[x].lazy;
- t[rs(x)].sum1+=(r-mid)*t[x].lazy;
- t[ls(x)].sum2+=(t[ls(x)].sum4*t[x].lazy);
- t[ls(x)].sum3+=(t[ls(x)].sum5*t[x].lazy);
- t[rs(x)].sum2+=(t[rs(x)].sum4*t[x].lazy);
- t[rs(x)].sum3+=(t[rs(x)].sum5*t[x].lazy);
- t[x].lazy=0;
- }
- }
- void QZADD(int x,int l,int r,int nl,int nr,int w)
- {
- if(nl<=l&&nr>=r)
- {
- t[x].sum1+=(r-l+1)*w;
- t[x].sum2+=(t[x].sum4*w);
- t[x].sum3+=(t[x].sum5*w);
- t[x].lazy+=w;
- return;
- }
- pushdown(x,l,r);
- int mid=(l+r)>>1;
- if(nl<=mid)
- QZADD(ls(x),l,mid,nl,nr,w);
- if(nr>mid)
- QZADD(rs(x),mid+1,r,nl,nr,w);
- pushup(x);
- }
- int QZQUERY1(int x,int l,int r,int nl,int nr)
- {
- int kel=0;
- if(nl<=l&&nr>=r)
- {
- return t[x].sum1;
- }
- pushdown(x,l,r);
- int mid=(l+r)>>1;
- if(nl<=mid)
- kel+=QZQUERY1(ls(x),l,mid,nl,nr);
- if(nr>mid)
- kel+=QZQUERY1(rs(x),mid+1,r,nl,nr);
- return kel;
- }
- int QZQUERY2(int x,int l,int r,int nl,int nr)
- {
- int kel=0;
- if(nl<=l&&nr>=r)
- {
- return t[x].sum2;
- }
- pushdown(x,l,r);
- int mid=(l+r)>>1;
- if(nl<=mid)
- kel+=QZQUERY2(ls(x),l,mid,nl,nr);
- if(nr>mid)
- kel+=QZQUERY2(rs(x),mid+1,r,nl,nr);
- return kel;
- }
- int QZQUERY3(int x,int l,int r,int nl,int nr)
- {
- int kel=0;
- if(nl<=l&&nr>=r)
- {
- return t[x].sum3;
- }
- pushdown(x,l,r);
- int mid=(l+r)>>1;
- if(nl<=mid)
- kel+=QZQUERY3(ls(x),l,mid,nl,nr);
- if(nr>mid)
- kel+=QZQUERY3(rs(x),mid+1,r,nl,nr);
- return kel;
- }
- int QUERY(int l,int r)
- {
- int s=0;
- s+=QZQUERY1(1,1,n,l,r)*(r-l-r*l+1);
- //cout<<QZQUERY1(1,1,n,l,r)<<' ';
- s+=QZQUERY2(1,1,n,l,r)*(l+r);
- //cout<<QZQUERY2(1,1,n,l,r)<<' ';
- s-=QZQUERY3(1,1,n,l,r);
- //cout<<QZQUERY3(1,1,n,l,r)<<'*'<<endl;
- return s;
- }
- int GCD(int x,int y)
- {
- return y==0?x:GCD(y,x%y);
- }
- int LINYIN()
- {
- freopen("roadxw.in","r",stdin);
- freopen("roadxw.out","w",stdout);
- scanf("%lld%lld",&n,&m);
- build(1,1,n);
- for(int i=1;i<=m;i++)
- {
- cin>>xd;
- if(xd=='C')
- {
- scanf("%lld%lld%lld",&a1,&a2,&a3);
- QZADD(1,1,n,a1+1,a2,a3);
- }
- else
- {
- scanf("%d%d",&a1,&a2);
- int kel=QUERY(a1+1,a2);
- int s=(a2-a1+1)*(a2-a1)/2;
- int G=GCD(s,kel);
- //cout<<endl<<kel<<''<<s<<' '<<G<<endl;
- printf("%lld/%lld\n",kel/G,s/G);
- }
- }
- return 0;
- }
- int LWH=LINYIN();
- signed main()
- {
- ;
- }
完结撒花!
神奇脑洞题解 --HAOI2012 高速公路(数学期望, 线段树)
来源: http://www.bubuko.com/infodetail-3269022.html