●BZOJ 4821 [Sdoi2017]相关分析

题链：

http://www.lydsy.com/JudgeOnline/problem.php?id=4821

题解：

线段树
是真的恶心，(也许是我的方法麻烦了一些吧)
首先那个式子可以做如下化简：

${a}=\frac {\sum{(}{x}_{i}-\overline{x}{)}{(}{y}_{i}-\overline{y}{)} } {\sum{(}{x}_{i}-\overline{x}{)}{(}{x}_{i}-\overline{x}{)} }$

$\;\;=\frac{{(}\sum{{x}_{i}{y}_{i}}{)}-{n}\overline{x}\overline{y}} {{(}\sum{{x}_{i}{x}_{i}}{)}-{n}\overline{x}\overline{x}}$

然后可以发现，记录区间内的：
x的和(sx)，y的和(sy)，x*y的和(sxy)，x*x的和(sxx)，再来两个lazy标记表示区间x,y增量。
以上的东西用线段树维护就可以解决掉第一个和第二个操作。
但是第三个操作怎么办呢？
我们把每个 xi = i + _xi，yi = i + _yi
然后用 _xi,_yi 去建立上述线段树，及维护和上面相同的东西:
_x的和(_sx)，_y的和(_sy)，_x*_y的和(_sxy)，_x*_x的和(_sxx)，再来两个lazy标记表示区间x,y增量。
这样就可以同样以区间修改的方式完成第三个操作。
但是接下来又来了一个问题：
对于一个询问，如何从维护得到的四元组(_sx,_sy,_sxy,_sxx),
得到用于求出答案的四元组(sx,sy,sxy,sxx)
看看如下式子：（用 ' 代替 _）
${x}_{i}\times{y}_{i}$

$={{(}{x'}_{i}+{i}{)}}\times{{(}{y'}_{i}+{i}{)}}$

$={x'_iy'_i}+{2i}{(}{x'_i+y'_i}{)}+{i^2}$

所以

$\begin{align}{sxy}&={sxy'}\\&+{2(\;\;}{{i(}x'_i+y'_i{)}}+{{{(}i+1{)}(}x'_{i+1}+y'_{i+1}{)}}+{{{(}i+2{)}(}x'_{i+2}+y'_{i+2}{)}}+\cdots{)}\\&+{(}i^2+{{(}i+1{)}}^2+{{(}i+2{)}}^2+\cdots{)}\end{align}$
所以只需再维护一些东西用于计算上面式子的中间项和末尾项即可。
即对每个区间 l~r 维护：

_sufxx：${l}\times{(}{x'}_{l}+{x'}_{l}{)} +{(l+1)}\times{(}{x'}_{l+1}+{x'}_{l+1}{)} +\cdots+ {r}\times{(}{x'}_{r}+{x'}_{r}{)}$

_sufxy：${l}\times{(}{x'}_{l}+{y'}_{l}{)} +{(l+1)}\times{(}{x'}_{l+1}+{y'}_{l+1}{)} +\cdots+ {r}\times{(}{x'}_{r}+{y'}_{r}{)}$

再预处理一个数组 ${pi2[i]}=1^2+2^2+3^2+\cdots+i^2$
然后就可以搞出四元组 (sx,sy,sxy,sxx)，进而得出答案。

代码：

#include<cstdio>

#include<cstring>

#include<iostream>

#define MAXN 100500

#define filein(x) freopen(#x".out","r",stdin)

#define fileout(x) freopen(#x".out","w",stdout)

using namespace std;

double pi2[MAXN];

int x[MAXN],y[MAXN];

struct Info{

	double _x,_y,_xy,_xx,_sufxy,_sufxx,_s,_t; int len;

	void Clear(){

		_x=_y=_xy=_xx=_sufxy=_sufxx=_s=_t=0;

	}

	void Modify(double s,double t,int type){

		if(type==2) Clear();

		_xx+=_x*s+_x*s+s*s*len;

		_xy+=_x*t+_y*s+s*t*len;

		_sufxx+=(s+s)*(1.0+(1+len-1))*len/2;

		_sufxy+=(s+t)*(1.0+(1+len-1))*len/2;

		_x+=s*len; _y+=t*len;

		_s+=s; _t+=t;

	}

	void Update(const Info &ls,const Info &rs){

		_x=ls._x+rs._x; _y=ls._y+rs._y;

		_xx=ls._xx+rs._xx; _xy=ls._xy+rs._xy;

		_sufxx=ls._sufxx+rs._sufxx+(rs._x+rs._x)*ls.len;

		_sufxy=ls._sufxy+rs._sufxy+(rs._x+rs._y)*ls.len;

	}

	double Calc(const int &l){

		double X,Y,XX,XY;

		X=_x+(1.0*l+(l+len-1))*len/2; X=X/len;

		Y=_y+(1.0*l+(l+len-1))*len/2; Y=Y/len;

		XX=_xx+(_sufxx+1.0*(l-1)*(_x+_x))+(pi2[l+len-1]-pi2[l-1]);

		XY=_xy+(_sufxy+1.0*(l-1)*(_x+_y))+(pi2[l+len-1]-pi2[l-1]);

		return (XY-X*Y*len)/(XX-X*X*len);

	}

};

struct SGT{

	#define ls lson[u]

	#define rs rson[u]

	#define alen ((r<ar?r:ar)-(l>al?l:al)+1)

	int lson[MAXN*2],rson[MAXN*2],lazy[MAXN*2],sz,rt;

	Info nd[MAXN*2];

	void pushup(Info &ndu,const Info &ndls,const Info &ndrs){

		ndu.Update(ndls,ndrs);

	}

	void pushdown(int u){

		nd[ls].Modify(nd[u]._s,nd[u]._t,lazy[u]),

		nd[rs].Modify(nd[u]._s,nd[u]._t,lazy[u]);

		lazy[ls]=max(lazy[ls],lazy[u]);

		lazy[rs]=max(lazy[rs],lazy[u]);

		lazy[u]=nd[u]._s=nd[u]._t=0;

	}

	void build(int &u,int l,int r){

		u=++sz; nd[u].len=r-l+1;

		if(l==r){

			nd[u].Modify(x[l],y[l],2);

			return;

		}

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

		build(ls,l,mid);

		build(rs,mid+1,r);

		pushup(nd[u],nd[ls],nd[rs]);

	}

	void Modify(int u,int l,int r,int al,int ar,double s,double t,int type){

		if(al<=l&&r<=ar){

			lazy[u]=max(lazy[u],type);

			nd[u].Modify(s,t,type);

			return;

		}

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

		if(lazy[u]) pushdown(u);

		if(al<=mid) Modify(ls,l,mid,al,ar,s,t,type);

		if(mid<ar) Modify(rs,mid+1,r,al,ar,s,t,type);

		pushup(nd[u],nd[ls],nd[rs]);

	}

	Info Query(int u,int l,int r,int al,int ar){

		if(al<=l&&r<=ar) return nd[u];

		int mid=(l+r)>>1; Info ret,lret,rret;

		ret.Clear(); lret.Clear(); rret.Clear();

		ret.len=alen; lret.len=0; rret.len=0;

		if(lazy[u]) pushdown(u);

		if(al<=mid) lret=Query(ls,l,mid,al,ar);

		if(mid<ar) rret=Query(rs,mid+1,r,al,ar);

		pushup(ret,lret,rret);

		return ret;

	}

	#undef ls

	#undef rs

	#undef alen

}T;

int N,M;

void read(int &X){

	static int f; static char ch;

	scanf("%d",&X); return;

	X=0; f=1; ch=getchar();

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

	while('0'<=ch&&ch<='9'){X=X*10+ch-'0'; ch=getchar();}

	X=X*f;

}

int main(){

	read(N); read(M);

	for(int i=1;i<=N;i++) pi2[i]=pi2[i-1]+1.0*i*i;

	for(int i=1;i<=N;i++) read(x[i]),x[i]-=i;

	for(int i=1;i<=N;i++) read(y[i]),y[i]-=i;

	T.build(T.rt,1,N);

	Info ret; int c,l,r,s,t;

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

		read(c); read(l); read(r);

		if(c==1){

			ret=T.Query(T.rt,1,N,l,r);

			printf("%.10lf\n",ret.Calc(l));

		}

		else{

			read(s); read(t);

			T.Modify(T.rt,1,N,l,r,s,t,c-1);

		}

	}

	return 0;

}

巴特西

●BZOJ 4821 [Sdoi2017]相关分析

最新文章

热门文章