题解 P4927 【[1007]梦美与线段树】

xzyxzy

2018-10-08 19:19:12

Solution

# 线段树维护懒标记 对,就和题面中写的一样 经过打表、找规律或者推式子可以发现,题目要求我们动态维护$$\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