【[HAOI2012]高速公路】
披着期望外衣的数据结构? 非常毒瘤 我们要求得期望其实就是 [frac{sum_{i=l}^{r}sum_{j=i+1}^{r}dis(i,j)}{binom{r-l+1}{2}}] 好像非常难求的样子 我记得慎老师曾经教过我今天的那道线段期望的初赛题,其实这道题和那道初赛题非常的像 老师教给我的思路是每次都将区间拆成两半来考虑,之后就会得到一个无穷等比数列 好像线段树就非常自然的每次将区间拆成了两半考虑 我们用(d(x))表示线段树(x)节点管辖的区间内所有区间的和,显然合并的时候 [d(x)=d(x<<1)+d(x<<1|1)] 这是不跨区间的情况 还需要考虑跨区间的情况 [d(x)+=ls(x<<1)*len(x<<1|1)+rs(x<<1|1)*len(x<<1)] (ls,rs)表示从左/右开始的所有区间的长度和 剩下的比较简单随便推一下就好了 有点困难的是(pushdown)的时候(d(x))如何维护,由于这里是抄的题解里的柿子,所以这里手推一波 增加量应该对应到每一个区间上去,于是考虑枚举每一种长度的区间有多少个 [sum_{i=1}^{len}i*(len-i+1)*val] [=sum_{i=1}^{len}i*(len+1)*val-i^2*val] [=val*((len+1)*sum_{i=1}^{len}i-sum_{i=1}^{len}i^2)] [=val*(frac{len*(len+1)^2}{2}-frac{(len+1)(2*len+1)len}{6})] 就好了 代码 #include<iostream> #include<cstring> #include<cstdio> #define re register #define maxn 100005 #define LL long long #define int long long LL l[maxn<<2],r[maxn<<2]; LL tag[maxn<<2],d[maxn<<2],ls[maxn<<2],rs[maxn<<2],s[maxn<<2]; struct node { LL len,lc,rc,sum,t; }; int n,Q; inline int read() { char c=getchar(); int x=0,r=1; while(c<‘0‘||c>‘9‘) { if(c==‘-‘) r=-1; c=getchar(); } while(c>=‘0‘&&c<=‘9‘) x=(x<<3)+(x<<1)+c-48,c=getchar(); return x*r; } LL gcd(LL a,LL b) { if(!b) return a; return gcd(b,a%b); } void build(int x,int y,int i) { l[i]=x,r[i]=y; if(x==y) return; int mid=x+y>>1; build(x,mid,i<<1),build(mid+1,y,i<<1|1); } inline void pushup(int i) { d[i]=d[i<<1|1]+d[i<<1]; d[i]+=(r[i<<1]-l[i<<1]+1)*ls[i<<1|1]+rs[i<<1]*(r[i<<1|1]-l[i<<1|1]+1); s[i]=s[i<<1|1]+s[i<<1]; ls[i]=ls[i<<1],rs[i]=rs[i<<1|1]; ls[i]+=(r[i<<1|1]-l[i<<1|1]+1)*s[i<<1]+ls[i<<1|1]; rs[i]+=(r[i<<1]-l[i<<1]+1)*s[i<<1|1]+rs[i<<1]; } inline void pushdown(int i) { if(!tag[i]) return; s[i<<1]+=(r[i<<1]-l[i<<1]+1)*tag[i],s[i<<1|1]+=(r[i<<1|1]-l[i<<1|1]+1)*tag[i]; d[i<<1]+=((r[i<<1]-l[i<<1]+2)*(r[i<<1]-l[i<<1]+1)/2*(r[i<<1]-l[i<<1]+2)-(r[i<<1]-l[i<<1]+1)*(r[i<<1]-l[i<<1]+2)*(2*(r[i<<1]-l[i<<1]+1)+1)/6)*tag[i]; d[i<<1|1]+=((r[i<<1|1]-l[i<<1|1]+2)*(r[i<<1|1]-l[i<<1|1]+1)/2*(r[i<<1|1]-l[i<<1|1]+2)-(r[i<<1|1]-l[i<<1|1]+1)*(r[i<<1|1]-l[i<<1|1]+2)*(2*(r[i<<1|1]-l[i<<1|1]+1)+1)/6)*tag[i]; ls[i<<1]+=(r[i<<1]-l[i<<1]+2)*(r[i<<1]-l[i<<1]+1)/2*tag[i]; ls[i<<1|1]+=(r[i<<1|1]-l[i<<1|1]+2)*(r[i<<1|1]-l[i<<1|1]+1)/2*tag[i]; rs[i<<1]+=(r[i<<1]-l[i<<1]+2)*(r[i<<1]-l[i<<1]+1)/2*tag[i]; rs[i<<1|1]+=(r[i<<1|1]-l[i<<1|1]+2)*(r[i<<1|1]-l[i<<1|1]+1)/2*tag[i]; tag[i<<1]+=tag[i],tag[i<<1|1]+=tag[i]; tag[i]=0; } void change(int x,int i,int val) { if(x<=l[i]&&y>=r[i]) { s[i]+=(r[i]-l[i]+1)*val; d[i]+=((r[i]-l[i]+2)*(r[i]-l[i]+1)/2*(r[i]-l[i]+2)-(r[i]-l[i]+1)*(r[i]-l[i]+2)*(2*(r[i]-l[i]+1)+1)/6)*val; ls[i]+=(r[i]-l[i]+1)*(r[i]-l[i]+2)/2*val; rs[i]+=(r[i]-l[i]+1)*(r[i]-l[i]+2)/2*val; tag[i]+=val; return; } pushdown(i); int mid=l[i]+r[i]>>1; if(y<=mid) change(x,i<<1,val); else if(x>mid) change(x,i<<1|1,val); else change(x,val),change(x,val); pushup(i); } node query(int x,int i) { if(x<=l[i]&&y>=r[i]) return (node){r[i]-l[i]+1,ls[i],rs[i],s[i],d[i]}; pushdown(i); int mid=l[i]+r[i]>>1; if(y<=mid) return query(x,i<<1); if(x>mid) return query(x,i<<1|1); node L=query(x,R=query(x,i<<1|1),now; now.sum=L.sum+R.sum; now.t=L.t+R.t; now.t+=R.len*L.rc+L.len*R.lc; now.len=R.len+L.len; now.lc=L.lc,now.rc=R.rc; now.lc+=R.len*L.sum+R.lc; now.rc+=L.len*R.sum+L.rc; return now; } signed main() { n=read(),Q=read(); char opt[1]; build(1,n-1,1); int x,z; while(Q--) { scanf("%s",opt); if(opt[0]==‘C‘) { x=read(),y=read(),z=read(); if(x<y) change(x,y-1,1,z); } else { x=read(),y=read(); node ans=query(x,1); LL r=gcd(ans.t,(y-x)*(y-x+1)/2); printf("%lld/%lldn",ans.t/r,(y-x)*(y-x+1)/2/r); } } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |