洛谷 P2221 [HAOI2012]高速公路

链接：

题意：

有 \(n(1\leq n\leq 10^5)\) 个点,从第 \(i(1\leq i< n)\) 个点向第 \(i+1\) 个点连有边。最初所有边长 \(v_i\) 为 \(0\)。

有 \(m(1\leq m\leq 10^5)\) 次操作：

操作 \(1\)：'C' l r v 表示将 \(l\) 和 \(r\) 之间的所有边长度加上 \(v\)。
操作 \(2\)：'Q' l r 在第 \(l\) 个到第 \(r\) 个点里等概率随机取出两个不同的点 \(a\) 和 \(b\)，询问 \(a,b\) 的期望距离。

保证：\(1\leq l\leq r\leq n,-10^4\leq v\leq 10^4\)，任意时刻满足 \(0\leq v_i\leq 10^4\)。

分析：

分析询问操作，显然是问距离的平均数，也就是\(\dfrac{\sum\limits_{i=l}^{r-1}\sum\limits_{j=i+1}^rdis[i][j]}{(r-l+1)\times(r-l)/2}\)。

分母可以直接算，分子比较难算。

首先化边为点，查询 \([l,r]\) 之间的边也就是 \([l,r-1]\) 的边。

考虑每条边被计算的次数，枚举左右两边的端点，则 \(ans=\sum\limits_{i=l}^{r-1}v[i]\times(i-l+1)\times(r-i+1)\)。

把式子拆开后得到：

\(ans=\sum\limits_{i=l}^{r-1}v[i]*i^2+(l+r)\sum\limits_{i=l}^{r-1}v[i]*i+(-l*r+r-l+1)*\sum\limits_{i=l}^{r-1}v[i]\)

\(\sum\) 前面的东西可以提出来，所以我们只需要每次查询 \(\sum\limits_{i=l}^{r-1}v[i]*i^2,\sum\limits_{i=l}^{r-1}v[i]*i,\sum\limits_{i=l}^{r-1}v[i]\)

线段树维护这三个值，分别记为 \(sum1,sum2,sum3\)

pushup 时直接相加：

inline void pushup(int p){

	sum1(p)=sum1(p<<1)+sum1(p<<1|1);

	sum2(p)=sum2(p<<1)+sum2(p<<1|1);

	sum3(p)=sum3(p<<1)+sum3(p<<1|1);

}

修改时，\(sum1\) 加上 \(d*\sum\limits_{i=l}^ri^2\)，\(sum2\) 加上 \(d*\sum\limits_{i=l}^ri\)，\(sum3\) 加上 \(d*\sum\limits_{i=l}^r1\)。这些东西都可以 \(O(1)\) 搞出来。

所以分子就维护好了。

由于对边的操作需要我们让 \(r-1\)，但分母中的 \(r\) 不能减，所以在 \(r-1\) 后，分母要变成 \((r-l+2)\times(r-l+1)/2\)。

于是这道题就做完了。时间复杂度 \(O(n\log n)\)。

代码：

#include<bits/stdc++.h>

using namespace std;

#define int long long

#define in read()

inline int read(){

	int p=0,f=1;

	char c=getchar();

	while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}

	while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}

	return p*f;

}

const int N=1e5+5;

int n,m;

inline int gcd(int a,int b){return b?gcd(b,a%b):a;}

#define sum1(x) t[x].sum1

#define sum2(x) t[x].sum2

#define sum3(x) t[x].sum3

#define tag(x) t[x].tag

inline int sumi1(int l,int r){return (l+r)*(r-l+1)/2;}

inline int sumi2(int l,int r){return r*(r+1)/2*(2*r+1)/3-(l-1)*l/2*(2*l-1)/3;}

struct node{

	int sum1,sum2,sum3,tag;

}t[N<<2];

inline void pushup(int p){

	sum1(p)=sum1(p<<1)+sum1(p<<1|1);

	sum2(p)=sum2(p<<1)+sum2(p<<1|1);

	sum3(p)=sum3(p<<1)+sum3(p<<1|1);

}

inline void f(int l,int r,int p,int d){

	tag(p)+=d;

	sum1(p)+=sumi2(l,r)*d;

	sum2(p)+=sumi1(l,r)*d;

	sum3(p)+=(r-l+1)*d;

}

inline void pushdown(int l,int r,int p){

	if(tag(p)){

		int mid=(l+r)>>1;

		f(l,mid,p<<1,tag(p));

		f(mid+1,r,p<<1|1,tag(p));

		tag(p)=0;

	}

}

inline void change(int l,int r,int p,int cl,int cr,int d){

	if(l>=cl&&r<=cr){f(l,r,p,d);return ;}

	pushdown(l,r,p);

	int mid=(l+r)>>1;

	if(cl<=mid)change(l,mid,p<<1,cl,cr,d);

	if(cr>mid)change(mid+1,r,p<<1|1,cl,cr,d);

	pushup(p);

}

struct ret{

	int sum1,sum2,sum3;

};

ret operator+(const ret &x,const ret &y){

	ret z;

	z.sum1=x.sum1+y.sum1;

	z.sum2=x.sum2+y.sum2;

	z.sum3=x.sum3+y.sum3;

	return z;

}

inline ret query(int l,int r,int p,int ql,int qr){

	if(l>=ql&&r<=qr){return {sum1(p),sum2(p),sum3(p)};}

	pushdown(l,r,p);

	int mid=(l+r)>>1;

	ret t={0,0,0};

	if(ql<=mid)t=t+query(l,mid,p<<1,ql,qr);

	if(qr>mid)t=t+query(mid+1,r,p<<1|1,ql,qr);

	return t;

}

signed main(){

	n=in,m=in;

	for(int i=1;i<=m;i++){

		char c[5];

		cin>>c;

		if(c[0]=='C'){

			int l=in,r=in-1,d=in;

			change(1,n,1,l,r,d);

		}

		else{

			int l=in,r=in-1;

			ret ans=query(1,n,1,l,r);

			int ans1=-ans.sum1+(l+r)*ans.sum2+(r-l+1-l*r)*ans.sum3;

			int ans2=(r-l+2)*(r-l+1)/2;

			int t=gcd(ans1,ans2);

			ans1/=t,ans2/=t;

			cout<<ans1<<"/"<<ans2<<'\n';

		}

	}

	return 0;

}

巴特西

洛谷 P2221 [HAOI2012]高速公路

链接：

题意：

分析：

代码：

最新文章

热门文章