[洛谷 P2221] [HAOI2012]高速公路
题目大意:
给定序列 \(a1..an\), 维护两个操作, 区间加, 区间询问对 l..r 区间内的点对, 求期望距离.
因为题目是边的贡献, 考虑把 l+1 转化为点的贡献.
考虑对于 \([l..r]\)的答案如何计算
\[ans=\frac{\sum_{l<r}dis[l][r]}{(r-l+1)\times(r-l)/2}\]
先不看下面的, 只算上面的 ans, 最后除一下就行
考虑权值 \(a_i\)在所有点对中被贡献的次数
\[ans=\sum_{i=l}^r a_i*(r-i+1)*(i-l+1)\]
怎么理解这个式子呢? 考虑只有跨过 \(a_i\)的点对会包含 \(a_i\), 那在 \(a_i\)左边的 \(l\)就有 \((i-l+1)\)个, 在 \(a_i\)右边的 \(r\)有 \((r-i+1)\)个 (注:\(l,r\)可以取到 \(a_i\) 因为转换成了点的贡献)
发现还是不太好维护, 考虑先展开
\[ans=\sum_{i=l}^r a_i*(ir-i^2-lr-l+r+1)\]
整理一下 把含 i^2 项的, i 项的, 和常数项分开
\[ans=\sum_{i=l}^r a_i*[-i^2+(l+r)i+(r-l+1-lr)]\]
考虑写成 \(3\)个求和分别维护
\[ans=-\sum_{i=l}^r a_i*i^2+(l+r)\sum_{i=l}^r a_i\times i+(r-l+1-lr)\sum_{i=l}^r a_i\]
分别记 \(\sum_{i=l}^r a_i\)为 $s1, $ \(\sum_{i=l}^r a_i*i^2\)为 \(s2\), \(\sum_{i=l}^r a_i\times i\)为 \(s3\),
答案就可以写成
\[ans=-s3+(l+r)s2+(r-l+1-lr)s1\]
答案想好了 考虑区间 l..r 加 w 的时候 s1,s2,s3 的变化
- \[s1+=(r-l+1)\times w\]
- \[s2+=\sum_{
- i=l
- }^r i \times w\]
- \[s2+=\sum_{
- i=l
- }^r i^2 \times w\]
对于 \(\sum_{i=l}^r i\)可以预处理出来, 记为 \(s4\)
同理 \(\sum_{i=l}^r i^2\) 预处理出来记为 \(s5\)
而且很好的,\(s4,s5\)具有可加性, 在线段树上维护的时候直接 \(s4[rt]=s4[lc]+s4[rc]\), 不需要做其他事情
大概分析完了, 有一些细节注意的地方:
1, 记得 \(l..r\)换成 \(l+1..r\)或者 \(l..r-1\), 而且这里的变化会影响到 \(ans\)那里的计算 (简而言之就是算分子的时候把 \(l\) 换成 \(l+1\)就行)
2, 别忘了除掉 \(gcd\)
3, 由于乘法很多, 所有参与计算的变量要开 \(longlong\), 而且写的时候记得加上 \(1ll*\)
- #include<bits/stdc++.h>
- #define lc root<<1
- #define rc root<<1|1
- #define lson root<<1,l,mid
- #define rson root<<1|1,mid+1,r
- using namespace std;
- const int maxn=100010;
- typedef long long ll;
- ll s1[maxn<<2],s2[maxn<<2],s3[maxn<<2],s4[maxn<<2],s5[maxn<<2],lazy[maxn<<2];
- int n,m;
- inline void pushup(int root){
- s1[root]=s1[lc]+s1[rc];
- s2[root]=s2[lc]+s2[rc];
- s3[root]=s3[lc]+s3[rc];
- }
- void build(int root,int l,int r){
- lazy[root]=s1[root]=s2[root]=s3[root]=0;
- if (l==r){
- s4[root]=l;
- s5[root]=1ll*l*l;
- return;
- }
- int mid=l+r>>1;
- build(lson);build(rson);
- s4[root]=s4[lc]+s4[rc];
- s5[root]=s5[lc]+s5[rc];
- }
- void pushdown(int root,int l,int r){
- if (!lazy[root]) return;
- int t=lazy[root];lazy[root]=0;
- lazy[lc]+=t;lazy[rc]+=t;
- int mid=l+r>>1;
- s1[lc]+=1ll*(mid-l+1)*t;s1[rc]+=1ll*(r-mid)*t;
- s2[lc]+=1ll*s4[lc]*t;s2[rc]+=1ll*s4[rc]*t;
- s3[lc]+=1ll*s5[lc]*t;s3[rc]+=1ll*s5[rc]*t;
- }
- void update(int root,int l,int r,int L,int R,int w){
- if (L<=l && r<=R){
- s1[root]+=1ll*(r-l+1)*w;
- s2[root]+=1ll*w*s4[root];
- s3[root]+=1ll*w*s5[root];
- lazy[root]+=w;
- return;
- }
- pushdown(root,l,r);
- int mid=l+r>>1;
- if (L<=mid) update(lson,L,R,w);
- if (R>mid) update(rson,L,R,w);
- pushup(root);
- }
- void query(int root,int l,int r,int L,int R,ll &sum1,ll &sum2,ll &sum3){
- if (L<=l && r<=R){
- sum1+=s1[root];sum2+=s2[root];sum3+=s3[root];
- return;
- }
- pushdown(root,l,r);
- int mid=l+r>>1;
- if (L<=mid) query(lson,L,R,sum1,sum2,sum3);
- if (R>mid) query(rson,L,R,sum1,sum2,sum3);
- }
- ll gcd(ll x,ll y){
- if (x%y==0) return y;
- else return gcd(y,x%y);
- }
- inline int read(){
- int x=0,f=1;char ch=getchar();
- while (ch<'0' || ch>'9') {if (ch=='-') f=-1;ch=getchar();}
- while (ch>='0' && ch<='9') {x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
- return x*f;
- }
- int main(){
- n=read();m=read();
- build(1,1,n);
- ll sum1=0,sum2=0,sum3=0;char st[10];
- int l,r,v;ll ans,mu,g;
- while (m--){
- scanf("%s",st);l=read();r=read();
- if (st[0]=='C'){
- v=read();
- update(1,1,n,l+1,r,v);
- }else{
- sum1=sum2=sum3=0;
- query(1,1,n,l+1,r,sum1,sum2,sum3);
- ans=1ll*(l+1+r)*sum2+1ll*(r-l-1ll*(l+1)*r)*sum1-sum3;
- mu=1ll*(r-l+1)*(r-l)/2;
- g=gcd(ans,mu);
- printf("%lld/%lld\n",ans/g,mu/g);
- }
- }
- return 0;
- }
P2221 [HAOI2012]高速公路
来源: http://www.bubuko.com/infodetail-3211918.html