kuoying 2019-11-02
传送门: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() { ; }
完结撒花!