P2221 [HAOI2012]高速公路 [洛谷P2221] [HAOI2012]高速公路

题目大意：

给定序列(a1..an)，维护两个操作，区间加，区间询问对l..r区间内的点对，求期望距离。

因为题目是边的贡献，考虑把l+1转化为点的贡献。
考虑对于([l..r])的答案如何计算

[ans=frac{sum_{l<r}dis[l][r]}{(r-l+1) imes(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 imes 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 imes i)为(s3),
答案就可以写成

[ans=-s3+(l+r)s2+(r-l+1-lr)s1 ]

答案想好了考虑区间l..r加w的时候s1,s2,s3的变化

[s1+=(r-l+1) imes w ]

[s2+=sum_{i=l}^r i imes w ]

[s2+=sum_{i=l}^r i^2 imes 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
",ans/g,mu/g);
		}
	}
	return 0;
}

P2221 [HAOI2012]高速公路 [洛谷P2221] [HAOI2012]高速公路

题目大意：

相关推荐