day1
数字表格
Description
\(fib[i]= \begin{cases}0 & i=0 \\ 1&i=1\\ fib[n]=fib[n-1]+fib[n-2]&n\leq2\end{cases}\)
对于一个\(n\times{m}\)的表格,第\(i\)行第\(j\)列的格子中的数是\(f[(i,j)]\),求表格中的数的积,答案对\(10^9+7\)取模.
HINT
多组数据, \(T\leq1000,1\leq{n},m\leq10^6\).
Solution
设 \(F(x)\) 表示 \(x|(i,j)(i\leq{n},j\leq{m})\) 的个数,则 \(F(x)=\lfloor\frac{n}{x}\rfloor\times\lfloor\frac{m}{x}\rfloor\).
设 \(f(x)\) 表示 \((i,j)=x(i\leq{n},j\leq{m})\) 的个数,则 \(F(d)=\sum_{d|g}f(g)\).
莫比乌斯反演一下,
\(\begin{split}f(d)&=\sum_{d|g}\mu(\frac{g}{d})F(g)\\&=\sum_{d|g}\mu(\frac{g}{d})\times\lfloor\frac{n}{g}\rfloor\times\lfloor\frac{m}{g}\rfloor\end{split}\)
即
\(\begin{split}ans&=\prod_{d=1}^{min(n,m)}fib[d]^{f(d)}\\&=\prod_{d=1}^{min(n,m)}fib[d]^{\sum_{d|g}\;\mu(\frac{g}{d})\times\lfloor\frac{n}{g}\rfloor\times\lfloor\frac{m}{g}\rfloor}\\&=\prod_{g=1}^{min(n,m)}(\prod_{d|g}fib[d]^{\mu(\frac{g}{d})})^{\lfloor\frac{n}{g}\rfloor\times\lfloor\frac{m}{g}\rfloor}\end{split}\)
因为 \(\lfloor\frac{n}{g}\rfloor\times\lfloor\frac{m}{g}\rfloor\) 的取值是 \(\sqrt{n}\) 个的,所以记录 \(\prod_{d|g}fib[d]^{\mu(\frac{g}{d})}\) 的关于 \(g\) 的前缀积 , 枚举 \(\lfloor\frac{n}{g}\rfloor\times\lfloor\frac{m}{g}\rfloor\) 的取值 即可.
#define K 80000
#define N 1000001
#define M 1000000007
int f[N],rev[N],s[N],mu[N],p[K],n,m,t,cnt,ans;
bool b[N];
inline void prime(){
mu[1]=1;
for(int i=2;i<N;++i){
if(!b[i]) p[++cnt]=i,mu[i]=-1;
for(int j=1;j<=cnt&&i*p[j]<N;++j){
b[i*p[j]]=true;
if(!(i%p[j])){
mu[i*p[j]]=0;break;
}
mu[i*p[j]]=-mu[i];
}
}
}
inline int po(int x,int k){
if(x<0) x+=M;
int ret=1;
while(k){
if(k&1) ret=1ll*ret*x%M;
x=1ll*x*x%M;k>>=1;
}
return ret;
}
inline void Aireen(){
prime();
f[0]=0;f[1]=1;
for(int i=2;i<N;++i){
f[i]=f[i-1]+f[i-2];
if(f[i]>=M) f[i]-=M;
}
for(int i=0;i<N;++i)
rev[i]=po(f[i],M-2);
for(int i=0;i<N;++i) s[i]=1;
for(int i=1;i<N;++i)
for(int j=i;j<N;j+=i){
if(mu[j/i]==-1) s[j]=1ll*s[j]*rev[i]%M;
else if(mu[j/i]==1) s[j]=1ll*s[j]*f[i]%M;
}
for(int i=1;i<N;++i)
s[i]=1ll*s[i-1]*s[i]%M;
for(int i=0;i<N;++i)
rev[i]=po(s[i],M-2);
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
ans=1;
for(int l=1,r;l<=min(n,m);l=r+1){
r=min(n/(n/l),m/(m/l));
ans=1ll*ans*po(po(1ll*s[r]*rev[l-1]%M,n/l)%M,m/l)%M;
}
printf("%d\n",ans);
}
}
树点涂色
Description
给定一棵n个点的有根树,其中1号点是根节点.Bob在每个点上涂了颜色,并且每个点上的颜色不同.
定义一条路径的权值是:这条路径上的点(包括起点和终点)共有多少种不同的颜色.Bob可能会进行这几种操作:
- 1 x:把点x到根节点的路径上所有的点染上一种没有用过的新颜色.
- 2 x y:求x到y的路径的权值.
- 3 x y:在以x为根的子树中选择一个点,使得这个点到根节点的路径权值最大,求最大权值.
Bob一共会进行m次操作.
HINT
\(1\leq{n,m}\leq100000\).
Solution
记 \(f(x)\) 表示 \(x\) 与其父亲的颜色是否相同 ( 相同为 \(0\) , 不同为 \(1\) ) , 默认 \(f(x)=1\) .
显然一个点到根的路径权值为路径上的 \(f(x)\) 之和 , 记为 \(g(x)\) .
\((u,v)\)的路径权值为 \(g(u)-g(v)-2(lca(u,v))+1\) .
所以只需按 \(dfs\) 序建棵线段树 , 维护区间 \(g(x)\) 最大值.
操作一相当于 \(access\) 操作 , 将路径上原来的 \(preferred\;child\) 子树中的 \(g(x)+1\),将 \(access\) 后的 \(preferred\;child\) 子树中的 \(g(x)-1\)
#define N 100005
#define M 1000005
struct graph{
int nxt,to;
}e[N<<1];
int g[N],n,m,cnt,tot;
inline void addedge(int x,int y){
e[++cnt]=(graph){g[x],y};g[x]=cnt;
}
inline void adde(int x,int y){
addedge(x,y);addedge(y,x);
}
int l[N],r[N],p[N],fa[N],dep[N],siz[N],son[N],top[N];
inline void dfs1(int u){
int mx=0;siz[u]=1;
for(int i=g[u];i;i=e[i].nxt)
if(!dep[e[i].to]){
fa[e[i].to]=u;
dep[e[i].to]=dep[u]+1;
dfs1(e[i].to);
siz[u]+=siz[e[i].to];
if(siz[e[i].to]>mx){
son[u]=e[i].to;
mx=siz[e[i].to];
}
}
}
inline void dfs2(int u,int tp){
top[u]=tp;p[++cnt]=u;l[u]=cnt;
if(son[u]) dfs2(son[u],tp);
for(int i=g[u];i;i=e[i].nxt)
if(e[i].to!=son[u]&&e[i].to!=fa[u])
dfs2(e[i].to,e[i].to);
r[u]=cnt;
}
inline int lca(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=fa[top[x]];
}
return dep[x]<dep[y]?x:y;
}
struct SegTree{
int l,r,mx,lzy;
}lt[M];
inline void build(int u,int l,int r){
tot=max(u,tot);
lt[u].l=l;lt[u].r=r;
if(lt[u].l<lt[u].r){
int lef=u<<1,rig=u<<1|1;
int mid=(lt[u].l+lt[u].r)>>1;
build(lef,l,mid);build(rig,mid+1,r);
lt[u].mx=max(lt[lef].mx,lt[rig].mx);
}
else lt[u].mx=dep[p[lt[u].l]];
}
inline void pushdown(int u){
if(lt[u].l==lt[u].r||!lt[u].lzy) return;
int lef=u<<1,rig=u<<1|1;
lt[lef].mx+=lt[u].lzy;
lt[rig].mx+=lt[u].lzy;
lt[lef].lzy+=lt[u].lzy;
lt[rig].lzy+=lt[u].lzy;
lt[u].lzy=0;
}
inline void add(int u,int l,int r,int k){
if(lt[u].l>=l&<[u].r<=r){
lt[u].mx+=k;lt[u].lzy+=k;return;
}
if(lt[u].l<lt[u].r){
pushdown(u);
int lef=u<<1,rig=u<<1|1;
int mid=(lt[u].l+lt[u].r)>>1;
if(l<=mid) add(lef,l,r,k);
if(r>mid) add(rig,l,r,k);
lt[u].mx=max(lt[lef].mx,lt[rig].mx);
}
}
inline int ask(int u,int l,int r){
if(lt[u].l>=l&<[u].r<=r)
return lt[u].mx;
if(lt[u].l<lt[u].r){
pushdown(u);
int lef=u<<1,rig=u<<1|1,ret=0;
int mid=(lt[u].l+lt[u].r)>>1;
if(l<=mid) ret=max(ret,ask(lef,l,r));
if(r>mid) ret=max(ret,ask(rig,l,r));
return ret;
}
}
inline int asks(int u,int v){
int k=lca(u,v);
return ask(1,l[u],l[u])+ask(1,l[v],l[v])-2*ask(1,l[k],l[k])+1;
}
struct LCT{
int c[2],f;
}tr[N];
inline bool isroot(int u){
return tr[tr[u].f].c[0]!=u&&tr[tr[u].f].c[1]!=u;
}
inline bool sn(int u){
return tr[tr[u].f].c[1]==u;
}
inline void ins_p(int f,int u,int c){
tr[f].c[c]=u;tr[u].f=f;
}
inline void rotate(int u){
int f=tr[u].f,c=sn(u);
if(isroot(f)) tr[u].f=tr[f].f;
else ins_p(tr[f].f,u,sn(f));
ins_p(f,tr[u].c[c^1],c);
ins_p(u,f,c^1);
}
inline void splay(int u){
while(!isroot(u)){
if(isroot(tr[u].f)) rotate(u);
else if(sn(u)==sn(tr[u].f)){
rotate(tr[u].f);rotate(u);
}
else{
rotate(u);rotate(u);
}
}
}
inline int lef(int u){
while(tr[u].c[0]) u=tr[u].c[0];
return u;
}
inline void access(int u){
for(int lst=0,y;u;lst=u,u=tr[u].f){
splay(u);
y=lef(lst);
if(y) add(1,l[y],r[y],-1);
y=lef(tr[u].c[1]);
if(y) add(1,l[y],r[y],1);
tr[u].c[1]=lst;
}
}
inline void Aireen(){
n=read();m=read();
for(int i=1;i<n;++i)
adde(read(),read());
dep[1]=1;dfs1(1);cnt=0;dfs2(1,1);build(1,1,n);
for(int i=1;i<=n;++i) tr[i].f=fa[i];
int ty,x,y;
while(m--){
ty=read();
if(ty==1) access(read());
else if(ty==2) printf("%d\n",asks(read(),read()));
else if(ty==3){
x=read();printf("%d\n",ask(1,l[x],r[x]));
}
}
}
序列计数
Description
对于一个长度为 \(n\) 的合法序列,要求 \(\forall{1\leq{i}\leq{n}},0<{a_i}\leq{m},p|\sum_{i=1}^{n}a_i,\)这 \(n\) 个数中,至少有一个数是质数.求有多少合法序列.
HINT
\(1\leq{n}\leq10^9,1\leq{m}\leq2\times10^7,1\leq{p}\leq100\).
Solution
答案为所有和为 \(p\) 的倍数的情况-没有质数且和为 \(p\) 的倍数的情况.
\(f[i][j]\) 表示前 \(i\) 个数和 \(mod\;p=j\) 的方案数.
\(f[i][j]=f[i-1][k]\times g[(j-k+p)\;mod\;p]\;(g[i]\)表示可以填的数中 \(mod\;p=i\) 的数的个数\().\)
矩乘优化一下即可.
#define P 100
#define K 1300000
#define N 20000001
#define M 20170408
struct matrix{
int a[P][P],n,m;
inline void init(){
memset(a,0,sizeof(a));
for(int i=0;i<P;++i) a[i][i]=1;
}
inline void ini(){
memset(a,0,sizeof(a));
}
}a,b;
int n,m,p,t[P],ans;
int pri[N],cnt;bool v[N];
inline void prime(int n){
v[1]=true;
for(int i=2;i<=n;++i){
if(!v[i]) pri[++cnt]=i;
for(int j=1;j<=cnt&&pri[j]*i<=n;++j){
v[i*pri[j]]=true;
if(!(i%pri[j])) break;
}
}
for(int i=1;i<=n;++i)
if(v[i]) ++t[i%p];
}
matrix operator *(matrix a,matrix b){
matrix c;
c.ini();c.n=b.n;c.m=b.m;
for(int i=0;i<c.n;++i)
for(int j=0;j<c.m;++j)
for(int k=0;k<c.n;++k){
c.a[i][j]+=1ll*a.a[i][k]*b.a[k][j]%M;
if(c.a[i][j]>=M) c.a[i][j]-=M;
}
return c;
}
inline matrix po(matrix x,int k){
matrix ret;ret.init();ret.n=ret.m=x.n;
while(k){
if(k&1) ret=ret*x;
x=x*x;k>>=1;
}
return ret;
}
inline void Aireen(){
scanf("%d%d%d",&n,&m,&p);
prime(m);
a.n=p;a.m=1;
a.a[0][0]=1;
b.n=b.m=p;
for(int j=0;j<p;++j)
for(int k=0;k<p;++k)
b.a[j][k]=t[(j-k+p)%p];
a=po(b,n)*a;
ans=a.a[0][0];
memset(t,0,sizeof(t));
for(int i=1;i<=m;++i)
++t[i%p];
a.ini();
a.n=p;a.m=1;
a.a[0][0]=1;
b.ini();
b.n=b.m=p;
for(int j=0;j<p;++j)
for(int k=0;k<p;++k)
b.a[j][k]=t[(j-k+p)%p];
a=po(b,n)*a;
ans=(a.a[0][0]-ans+M)%M;
printf("%d\n",ans);
}
day2
新生舞会
Description
男女生两两配对跳舞,第i个男生与第j个女生一起跳舞的喜悦程度为\(a_{i,j}\),不喜悦程度为\(b_{i,j}\),求\(\frac{\sum{a_i}}{\sum{b_i}}\)的最大值.
HINT
\(1\leq{n}\leq100,1\leq{a_{i,j},b_{i,j}}\leq10^4\).
Solution
二分\(C=\frac{\sum{a_i}}{\sum{b_i}}\),
判断是否存在\(\sum{a_i}\geq{C\times\sum{b_i}}\),即\(\sum{a_i}-{\sum{b_i\times{C}}}\geq0\)
建立二分图,\((i,j)=a_{i,j}-b_{i,j}\times{C}\),用KM求二分图最大权匹配.
#define N 101
#define INF 1e7
#define eps 1e-7
int fr[N],n;
bool vx[N],vy[N];
double a[N][N],b[N][N],w[N][N],x[N],y[N],sla[N];
inline bool match(int u){
double tmp;vx[u]=true;
for(int j=1;j<=n;++j){
if(vy[j]) continue;
tmp=x[u]+y[j]-w[u][j];
if(fabs(tmp)<eps){
vy[j]=true;
if(!fr[j]||match(fr[j])){
fr[j]=u;return true;
}
}
else if(tmp<sla[j]) sla[j]=tmp;
}
return false;
}
inline bool KM(){
for(int i=1;i<=n;++i){
x[i]=-INF;
for(int j=1;j<=n;++j)
x[i]=max(x[i],w[i][j]);
}
memset(y,0,sizeof(y));
memset(fr,0,sizeof(fr));
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j) sla[j]=INF;
while(true){
memset(vx,0,sizeof(vx));
memset(vy,0,sizeof(vy));
if(match(i)) break;
double tmp=INF;
for(int j=1;j<=n;++j)
if(!vy[j]&&tmp>sla[j]) tmp=sla[j];
for(int j=1;j<=n;++j)
if(vx[j]) x[j]-=tmp;
for(int j=1;j<=n;++j)
if(vy[j]) y[j]+=tmp;
else sla[j]-=tmp;
}
}
double cnt=0.0,sum=0.0;
for(int i=1;i<=n;++i)
cnt+=a[fr[i]][i];
for(int i=1;i<=n;++i)
sum+=b[fr[i]][i];
double ret=0.0;
for(int i=1;i<=n;++i)
ret+=w[fr[i]][i];
return ret>-1e-13;
}
inline bool chk(double k){
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
w[i][j]=a[i][j]-b[i][j]*k;
return KM();
}
inline void Aireen(){
double mxa=0.0,mia=1e4,mxb=0.0,mib=1e4;
scanf("%d",&n);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j){
scanf("%lf",&a[i][j]);
mxa=max(mxa,a[i][j]);
mia=min(mia,a[i][j]);
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j){
scanf("%lf",&b[i][j]);
mxb=max(mxb,b[i][j]);
mib=min(mib,b[i][j]);
}
double l=mia/mxb,r=mxa/mib,mid;
while(l+eps<r){
mid=(l+r+eps)/2.0;
if(chk(mid)) l=mid;
else r=mid-eps;
}
printf("%.6lf\n",l);
}
硬币游戏
Description
n个人各猜一个长度为\(m\)的H/T序列,扔很多次硬币,记录下落后的翻面情况,得到一个硬币序列.如果有人的序列为硬币序列的子序列,游戏结束,此人获胜.保证不存在相同的序列.
HINT
\(1\leq{n,m}\leq300\).
Solution
设N为一个未结束的状态.对于序列a,b,如果序列a的后缀是序列b的前缀,那么a会对b的胜利产生影响:\(\sum\frac{1}{2}^k\)(a的后缀a[k+1...n]是序列b的前缀)的概率a获胜.
这样列出n个方程,但是存在n+1个未知数,所以还需要所有序列的概率之和为1这个方程.
#define N 305
#define eps 1e-13
int nxt[N],n,m;
char a[N],b[N],c[N][N];
double f[N][N],mul[N],ans[N];
inline void kmp(int x,int y){
int k=0;
for(int i=1;i<=m;++i)
a[i]=c[x][i],b[i]=c[y][i];
for(int i=2,j=0;i<=m;++i){
while(j&&b[j+1]!=b[i]) j=nxt[j];
j+=(b[j+1]==b[i]);nxt[i]=j;
}
for(int i=1,j=0;i<=m;++i){
while(j&&b[j+1]!=a[i]) j=nxt[j];
j+=(b[j+1]==a[i]);k=j;
}
while(k){
f[y][x]+=mul[m-k];k=nxt[k];
}
}
inline void gauss(int n){
double tmp;
for(int i=0;i<n;++i){
if(fabs(f[i][i])<eps)
for(int j=i+1;j<=n;++j)
if(f[j][i]){
for(int k=i;k<=n;++k)
swap(f[i][k],f[j][k]);
break;
}
for(int j=0;j<n;++j)
if(j!=i&&f[j][i]){
tmp=f[j][i]/f[i][i];
for(int k=i;k<=n;++k)
f[j][k]=(f[j][k]-tmp*f[i][k]);
}
}
for(int i=1;i<=n;++i)
ans[i]=f[i][n]/f[i][i];
}
inline void Aireen(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%s",c[i]+1);
mul[0]=1.0;
for(int i=1;i<=m;++i)
mul[i]=mul[i-1]*0.5;
for(int j=1;j<=n;++j)for(int i=1;i<=n;++i)
kmp(i,j);
for(int i=1;i<=n;++i)
f[i][0]=-mul[m];
for(int i=1;i<=n+1;++i)
f[0][i]=1.0;
gauss(n+1);
for(int i=1;i<=n;++i)
printf("%.10lf\n",ans[i]);
}
相关分析
Description
给定n个点\((x_i,y_i)\),维护三种操作:
- \(1\;l\;r:\overline{x}=\sum_{i=l}^{r}\frac{x_i}{r-l+1},\overline{y}=\sum_{i=l}^{r}\frac{y_i}{r-l+1}\),求\(a=\frac{\sum_{i=l}^{r}(x_i-\overline{x})(y_i-\overline{y})}{\sum_{i=l}^{r}(x_i-\overline{x})^2}\)
- \(2\;l\;r\;s\;t:\)对于区间 \([l,r],x_i+s,y_i+t\).
- \(3\;l\;r\;s\;t:\)对于区间 \([l,r],x_i+s+i,y_i+t+i\).
HINT
\(1\leq{n,m}\leq10^5\).
Solution
把式子拆开,线段树维护.
#define N 100005
#define M 1000005
struct SegTree{
int l,r,fl;double sx,sy,sxx,sxy,cx,cy;
}lt[M];
double X[N],Y[N];
int n,m;
inline void build(int u,int l,int r){
lt[u].l=l;lt[u].r=r;
if(lt[u].l<lt[u].r){
int lef=u<<1,rig=u<<1|1;
int mid=(lt[u].l+lt[u].r)>>1;
build(lef,l,mid);build(rig,mid+1,r);
lt[u].sx=lt[lef].sx+lt[rig].sx;
lt[u].sy=lt[lef].sy+lt[rig].sy;
lt[u].sxx=lt[lef].sxx+lt[rig].sxx;
lt[u].sxy=lt[lef].sxy+lt[rig].sxy;
}
else{
lt[u].sx=X[lt[u].l];
lt[u].sy=Y[lt[u].l];
lt[u].sxx=lt[u].sx*lt[u].sx;
lt[u].sxy=lt[u].sx*lt[u].sy;
}
}
inline double sum(int s,int t){
double l=1.0*s,r=1.0*t;
return (l+r)*(r-l+1.0)/2.0;
}
inline double sqr(int s,int t){
double l=1.0*(s-1),r=1.0*t;
return ((r*(r+1.0)*(2.0*r+1.0))-(l*(l+1.0)*(2.0*l+1.0)))/6.0;
}
inline void down1(int u,double s,double t){
if(!lt[u].fl) lt[u].fl=1;
lt[u].cx+=s;lt[u].cy+=t;
lt[u].sxx+=2*lt[u].sx*s+s*s*(lt[u].r-lt[u].l+1);
lt[u].sxy+=lt[u].sx*t+lt[u].sy*s+s*t*(lt[u].r-lt[u].l+1);
lt[u].sx+=s*(lt[u].r-lt[u].l+1);lt[u].sy+=t*(lt[u].r-lt[u].l+1);
}
inline void down2(int u,double s,double t){
lt[u].fl=2;lt[u].cx=s;lt[u].cy=t;
lt[u].sxx=s*s*(lt[u].r-lt[u].l+1)+2.0*s*sum(lt[u].l,lt[u].r)+sqr(lt[u].l,lt[u].r);
lt[u].sxy=s*t*(lt[u].r-lt[u].l+1)+(s+t)*sum(lt[u].l,lt[u].r)+sqr(lt[u].l,lt[u].r);
lt[u].sx=s*(lt[u].r-lt[u].l+1)+sum(lt[u].l,lt[u].r);
lt[u].sy=t*(lt[u].r-lt[u].l+1)+sum(lt[u].l,lt[u].r);
}
inline void pushdown(int u){
if(!lt[u].fl) return;
if(lt[u].l==lt[u].r){
lt[u].fl=0;lt[u].cx=lt[u].cy=0.0;return;
}
if(lt[u].fl&1){
down1(u<<1,lt[u].cx,lt[u].cy);
down1(u<<1|1,lt[u].cx,lt[u].cy);
lt[u].fl=0;lt[u].cx=lt[u].cy=0.0;
return;
}
down2(u<<1,lt[u].cx,lt[u].cy);
down2(u<<1|1,lt[u].cx,lt[u].cy);
lt[u].fl=0;lt[u].cx=lt[u].cy=0.0;
}
inline void add(int u,int l,int r,double s,double t){
if(lt[u].l>=l&<[u].r<=r){
down1(u,s,t);return;
}
if(lt[u].l<lt[u].r){
int lef=u<<1,rig=u<<1|1;
int mid=(lt[u].l+lt[u].r)>>1;
pushdown(u);
if(l<=mid) add(lef,l,r,s,t);
if(r>mid) add(rig,l,r,s,t);
lt[u].sx=lt[lef].sx+lt[rig].sx;
lt[u].sy=lt[lef].sy+lt[rig].sy;
lt[u].sxx=lt[lef].sxx+lt[rig].sxx;
lt[u].sxy=lt[lef].sxy+lt[rig].sxy;
}
}
inline void cover(int u,int l,int r,double s,double t){
if(lt[u].l>=l&<[u].r<=r){
down2(u,s,t);return;
}
if(lt[u].l<lt[u].r){
int lef=u<<1,rig=u<<1|1;
int mid=(lt[u].l+lt[u].r)>>1;
pushdown(u);
if(l<=mid) cover(lef,l,r,s,t);
if(r>mid) cover(rig,l,r,s,t);
lt[u].sx=lt[lef].sx+lt[rig].sx;
lt[u].sy=lt[lef].sy+lt[rig].sy;
lt[u].sxx=lt[lef].sxx+lt[rig].sxx;
lt[u].sxy=lt[lef].sxy+lt[rig].sxy;
}
}
inline double askx(int u,int l,int r){
if(lt[u].l>=l&<[u].r<=r)
return lt[u].sx;
if(lt[u].l<lt[u].r){
double ret=0.0;
int lef=u<<1,rig=u<<1|1;
int mid=(lt[u].l+lt[u].r)>>1;
pushdown(u);
if(l<=mid) ret+=askx(lef,l,r);
if(r>mid) ret+=askx(rig,l,r);
return ret;
}
}
inline double asky(int u,int l,int r){
if(lt[u].l>=l&<[u].r<=r)
return lt[u].sy;
if(lt[u].l<lt[u].r){
double ret=0.0;
int lef=u<<1,rig=u<<1|1;
int mid=(lt[u].l+lt[u].r)>>1;
pushdown(u);
if(l<=mid) ret+=asky(lef,l,r);
if(r>mid) ret+=asky(rig,l,r);
return ret;
}
}
inline double askxx(int u,int l,int r){
if(lt[u].l>=l&<[u].r<=r)
return lt[u].sxx;
if(lt[u].l<lt[u].r){
double ret=0.0;
int lef=u<<1,rig=u<<1|1;
int mid=(lt[u].l+lt[u].r)>>1;
pushdown(u);
if(l<=mid) ret+=askxx(lef,l,r);
if(r>mid) ret+=askxx(rig,l,r);
return ret;
}
}
inline double askxy(int u,int l,int r){
if(lt[u].l>=l&<[u].r<=r)
return lt[u].sxy;
if(lt[u].l<lt[u].r){
double ret=0.0;
int lef=u<<1,rig=u<<1|1;
int mid=(lt[u].l+lt[u].r)>>1;
pushdown(u);
if(l<=mid) ret+=askxy(lef,l,r);
if(r>mid) ret+=askxy(rig,l,r);
return ret;
}
}
inline void Aireen(){
n=read();m=read();
for(int i=1;i<=n;++i) scanf("%lf",&X[i]);
for(int i=1;i<=n;++i) scanf("%lf",&Y[i]);
build(1,1,n);
int ty,l,r;double x,y,ax,ay,ans;
while(m--){
ty=read();l=read();r=read();
if(ty==1){
x=askx(1,l,r);y=asky(1,l,r);
ax=x/(r-l+1);ay=y/(r-l+1);
ans=askxy(1,l,r)-ax*y-ay*x+ax*ay*(r-l+1);
ans/=(askxx(1,l,r)-2.0*ax*x+ax*ax*(r-l+1));
printf("%.10lf\n",ans);
}
else if(ty==2){
scanf("%lf%lf",&x,&y);
add(1,l,r,x,y);
}
else{
scanf("%lf%lf",&x,&y);
cover(1,l,r,x,y);
}
}
}
2017-04-21 10:23:13