题面
BZOJ https://lydsy.com/JudgeOnline/problem.php?id=4821
洛谷 https://www.luogu.org/problemnew/show/P3707
题解
看看询问要求的东西是什么. 把所有的括号拆开, 不难发现要求的就是 \(\sum x,\sum y,\sum xy,\sum x^2\)
考虑修改操作. 先是区间加法, 对于 \(\sum x,\sum y\) 而言直接加就好了.
而 \(\sum (x+S)^2=\sum (x^2+S^2+2Sx)\), 分开维护一下也做完了.
\(\sum (x+S)(y+T)\) 也只需要把括号拆开之后分开维护就行了.
另外一种是区间赋值, 我们看做先令 \(x_i=y_i=i\), 然后再对应的加上 \(S,T\) 就好了. 注意一下这里要把之前操作里面的 \(S,T\) 标记清空.
- #include<iostream>
- #include<cstdio>
- #include<cstdlib>
- #include<cstring>
- #include<cmath>
- #include<algorithm>
- #include<vector>
- using namespace std;
- #define MAX 100100
- #define lson (now<<1)
- #define rson (now<<1|1)
- #define ll long long
- inline int read()
- {
- int x=0;bool t=false;char ch=getchar();
- while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
- if(ch=='-')t=true,ch=getchar();
- while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
- return t?-x:x;
- }
- int n,m,X[MAX],Y[MAX];
- struct Node{double x,y,xy,xx,S,T;int eql;}t[MAX<<2];
- Node operator+(Node a,Node b){return (Node){a.x+b.x,a.y+b.y,a.xy+b.xy,a.xx+b.xx,0,0,0};}
- void pushup(int now)
- {
- t[now].x=t[lson].x+t[rson].x;
- t[now].y=t[lson].y+t[rson].y;
- t[now].xx=t[lson].xx+t[rson].xx;
- t[now].xy=t[lson].xy+t[rson].xy;
- }
- void Build(int now,int l,int r)
- {
- if(l==r)
- {
- t[now].x=X[l],t[now].y=Y[l];
- t[now].xx=t[now].x*t[now].x;
- t[now].xy=t[now].x*t[now].y;
- return;
- }
- int mid=(l+r)>>1;
- Build(lson,l,mid);Build(rson,mid+1,r);
- pushup(now);
- }
- double S1(int x){return 0.5*x*(x+1);}
- double S2(int x){return 1.0/6*x*(x+1)*(x+x+1);}
- void addST(int now,int l,int r,double S,double T)
- {
- int len=r-l+1;
- t[now].xx+=len*S*S+2*S*t[now].x;
- t[now].xy+=t[now].x*T+t[now].y*S+len*S*T;
- t[now].x+=len*S;t[now].y+=len*T;
- t[now].S+=S;t[now].T+=T;
- }
- void addeql(int now,int l,int r)
- {
- t[now].x=t[now].y=S1(r)-S1(l-1);
- t[now].xx=t[now].xy=S2(r)-S2(l-1);
- t[now].eql=1;t[now].S=t[now].T=0;
- }
- void pushdown(int now,int l,int r)
- {
- int mid=(l+r)>>1;
- if(t[now].eql)
- {
- addeql(lson,l,mid);addeql(rson,mid+1,r);
- t[now].eql=0;
- }
- if(t[now].S||t[now].T)
- {
- addST(lson,l,mid,t[now].S,t[now].T);
- addST(rson,mid+1,r,t[now].S,t[now].T);
- t[now].S=t[now].T=0;
- }
- }
- void Modify(int now,int l,int r,int L,int R,double S,double T)
- {
- if(L<=l&&r<=R){addST(now,l,r,S,T);return;}
- int mid=(l+r)>>1;pushdown(now,l,r);
- if(L<=mid)Modify(lson,l,mid,L,R,S,T);
- if(R>mid)Modify(rson,mid+1,r,L,R,S,T);
- pushup(now);
- }
- void Modify(int now,int l,int r,int L,int R)
- {
- if(L<=l&&r<=R){addeql(now,l,r);return;}#include<iostream>
- #include<cstdio>
- #include<cstdlib>
- #include<cstring>
- #include<cmath>
- #include<algorithm>
- #include<vector>
- using namespace std;
- #define MAX 100100
- #define lson (now<<1)
- #define rson (now<<1|1)
- #define ll long long
- inline int read()
- {
- int x=0;bool t=false;char ch=getchar();
- while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
- if(ch=='-')t=true,ch=getchar();
- while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
- return t?-x:x;
- }
- int n,m,X[MAX],Y[MAX];
- struct Node{double x,y,xy,xx,S,T;int eql;}t[MAX<<2];
- Node operator+(Node a,Node b){return (Node){a.x+b.x,a.y+b.y,a.xy+b.xy,a.xx+b.xx,0,0,0};}
- void pushup(int now)
- {
- t[now].x=t[lson].x+t[rson].x;
- t[now].y=t[lson].y+t[rson].y;
- t[now].xx=t[lson].xx+t[rson].xx;
- t[now].xy=t[lson].xy+t[rson].xy;
- }
- void Build(int now,int l,int r)
- {
- if(l==r)
- {
- t[now].x=X[l],t[now].y=Y[l];
- t[now].xx=t[now].x*t[now].x;
- t[now].xy=t[now].x*t[now].y;
- return;
- }
- int mid=(l+r)>>1;
- Build(lson,l,mid);Build(rson,mid+1,r);
- pushup(now);
- }
- double S1(int x){return 0.5*x*(x+1);}
- double S2(int x){return 1.0/6*x*(x+1)*(x+x+1);}
- void addST(int now,int l,int r,double S,double T)
- {
- int len=r-l+1;
- t[now].xx+=len*S*S+2*S*t[now].x;
- t[now].xy+=t[now].x*T+t[now].y*S+len*S*T;
- t[now].x+=len*S;t[now].y+=len*T;
- t[now].S+=S;t[now].T+=T;
- }
- void addeql(int now,int l,int r)
- {
- t[now].x=t[now].y=S1(r)-S1(l-1);
- t[now].xx=t[now].xy=S2(r)-S2(l-1);
- t[now].eql=1;t[now].S=t[now].T=0;
- }
- void pushdown(int now,int l,int r)
- {
- int mid=(l+r)>>1;
- if(t[now].eql)
- {
- addeql(lson,l,mid);addeql(rson,mid+1,r);
- t[now].eql=0;
- }
- if(t[now].S||t[now].T)
- {
- addST(lson,l,mid,t[now].S,t[now].T);
- addST(rson,mid+1,r,t[now].S,t[now].T);
- t[now].S=t[now].T=0;
- }
- }
- void Modify(int now,int l,int r,int L,int R,double S,double T)
- {
- if(L<=l&&r<=R){addST(now,l,r,S,T);return;}
- int mid=(l+r)>>1;pushdown(now,l,r);
- if(L<=mid)Modify(lson,l,mid,L,R,S,T);
- if(R>mid)Modify(rson,mid+1,r,L,R,S,T);
- pushup(now);
- }
- void Modify(int now,int l,int r,int L,int R)
- {
- if(L<=l&&r<=R){addeql(now,l,r);return;}
- int mid=(l+r)>>1;pushdown(now,l,r);
- if(L<=mid)Modify(lson,l,mid,L,R);
- if(R>mid)Modify(rson,mid+1,r,L,R);
- pushup(now);
- }
- Node Query(int now,int l,int r,int L,int R)
- {
- if(l==L&&r==R)return t[now];
- int mid=(l+r)>>1;pushdown(now,l,r);
- if(R<=mid)return Query(lson,l,mid,L,R);
- if(L>mid)return Query(rson,mid+1,r,L,R);
- return Query(lson,l,mid,L,mid)+Query(rson,mid+1,r,mid+1,R);
- }
- int main()
- {
- n=read();m=read();
- for(int i=1;i<=n;++i)X[i]=read();
- for(int i=1;i<=n;++i)Y[i]=read();
- Build(1,1,n);
- while(m--)
- {
- int opt=read(),l=read(),r=read();
- if(opt==1)
- {
- Node a=Query(1,1,n,l,r);
- double u=a.xy-a.x*a.y/(r-l+1);
- double v=a.xx-a.x*a.x/(r-l+1);
- printf("%.10lf\n",u/v);
- }
- else
- {
- double S=read(),T=read();
- if(opt==3)Modify(1,1,n,l,r);
- Modify(1,1,n,l,r,S,T);
- }
- }
- return 0;
- }
- int mid=(l+r)>>1;pushdown(now,l,r);
- if(L<=mid)Modify(lson,l,mid,L,R);
- if(R>mid)Modify(rson,mid+1,r,L,R);
- pushup(now);
- }
- Node Query(int now,int l,int r,int L,int R)
- {
- if(l==L&&r==R)return t[now];
- int mid=(l+r)>>1;pushdown(now,l,r);
- if(R<=mid)return Query(lson,l,mid,L,R);
- if(L>mid)return Query(rson,mid+1,r,L,R);
- return Query(lson,l,mid,L,mid)+Query(rson,mid+1,r,mid+1,R);
- }
- int main()
- {
- n=read();m=read();
- for(int i=1;i<=n;++i)X[i]=read();
- for(int i=1;i<=n;++i)Y[i]=read();
- Build(1,1,n);
- while(m--)
- {
- int opt=read(),l=read(),r=read();
- if(opt==1)
- {
- Node a=Query(1,1,n,l,r);
- double u=a.xy-a.x*a.y/(r-l+1);
- double v=a.xx-a.x*a.x/(r-l+1);
- printf("%.10lf\n",u/v);
- }
- else
- {
- double S=read(),T=read();
- if(opt==3)Modify(1,1,n,l,r);
- Modify(1,1,n,l,r,S,T);
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2875585.html