题解 P4927 【[1007]梦美与线段树】
xzyxzy
2018-10-08 19:19:12
# 线段树维护懒标记
对,就和题面中写的一样
经过打表、找规律或者推式子可以发现,题目要求我们动态维护$$\frac{\sum_{i=1}^{tot}val[i]^2}{totval}$$
其中tot表示线段树结点总数,val表示线段树结点的权值,totval表示序列的总和
还是考虑懒标记
对于每个点维护四个东西,$l,val,tag,v$,分别表示该点子树内$\sum len^2$、子树内$\sum lenv$,加标记,权值。其中len表示该点所统管的叶子结点个数。pushup很好做,注意pushup要更新答案
维护一个全局答案,考虑每次给区间加一个值,有两个操作需要考虑
## upd_ans
原$val^2$,现$val^2+2vallenk+len^2k^2$,于是加$lk^2+2valk$即可
这样可以把整个子树的答案都统计上
## put_tag
l不变,$v+=len×k$,$tag+=k$,$val=\sum len_i(v_i+len_ik)=val_{old}+lk$
于是就很好维护了~~不明白为什么这题上了黑~~
先看看代码
```cpp
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define lc now<<1
#define rc now<<1|1
#define int __int128
using namespace std;
int read()
{
char ch=getchar();int h=0,t=1;
while((ch>'9'||ch<'0')&&ch!='-') ch=getchar();
if(ch=='-') t=-1,ch=getchar();
while(ch>='0'&&ch<='9') h=h*10+ch-'0',ch=getchar();
return h*t;
}
const int N=1e5+100,mod=998244353;
struct Que{int op,l,r,k;}A[N];
int n,m,P[N];
int ksm(int x,int k)
{
int s=1;for(;k;k>>=1,x=x*x%mod)
if(k&1) s=s*x%mod;return s;
}
void print(int x) {if(x>9) print(x/10);putchar(x%10+'0');}
struct Seg {int l,val,tag,v;}t[N<<2];
int tot,ans;
int f(int x) {return x*x;}
void pushup(int now,int l,int r)
{
ans-=f(t[now].v);
t[now].v=t[lc].v+t[rc].v;
ans+=f(t[now].v);
t[now].l=t[lc].l+t[rc].l+f(r-l+1);
t[now].val=t[lc].val+t[rc].val+(r-l+1)*t[now].v;
}
void build(int now,int l,int r)
{
if(l==r)
{
t[now]=(Seg){1,P[l],0,P[l]};
tot+=P[l];ans+=f(P[l]);return;
}
int mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
pushup(now,l,r);
}
void put(int now,int l,int r,int k,int op)
{
if(op)
{
ans+=2*k*t[now].val;
ans+=k*k*t[now].l;
}
t[now].tag+=k;
t[now].v+=k*(r-l+1);
t[now].val+=t[now].l*k;
}
void pushdown(int now,int l,int mid,int r)
{
int &s=t[now].tag;if(!s) return;
put(lc,l,mid,s,0);put(rc,mid+1,r,s,0);s=0;
}
void Add(int now,int l,int r,int gl,int gr,int k)
{
if(l>=gl&&r<=gr) {put(now,l,r,k,1);return;}
int mid=(l+r)>>1;
pushdown(now,l,mid,r);
if(gl<=mid) Add(now<<1,l,mid,gl,gr,k);
if(gr>mid) Add(now<<1|1,mid+1,r,gl,gr,k);
pushup(now,l,r);
}
signed main()
{
n=read();m=read();
for(int i=1;i<=n;i++) P[i]=read();
for(int i=1;i<=m;i++)
{
int op=read(),l=0,r=0,k=0;
if(op==1) l=read(),r=read(),k=read();
A[i]=(Que){op,l,r,k};
}
build(1,1,n);
for(int i=1;i<=m;i++)
if(A[i].op==2)
{
int fz=ans/__gcd(ans,tot);
int fm=tot/__gcd(ans,tot);
print(fz%mod*ksm(fm,mod-2)%mod),puts("");
}
else tot+=(A[i].r-A[i].l+1)*A[i].k,Add(1,1,n,A[i].l,A[i].r,A[i].k);
}
```
然后我们发现出题人设置了一个陷阱(于是把我比赛时卡成了90分)
保证答案约分后分母不是mod的倍数、
于是答案可能是$\frac{2mod}{mod}=2$,于是你边做边取模会发现分母变成了0
答案不大($10^{32}$左右),可以用std=c++11近乎作弊的方法使用__int128,然后中间计算不再取模,就可以很好地完成这题了
最后安利一道同样是线段树的模板题:https://www.luogu.org/problemnew/show/P4247
可以来博客玩玩:https://www.cnblogs.com/xzyxzy