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

· · 题解

线段树维护懒标记

对，就和题面中写的一样

经过打表、找规律或者推式子可以发现，题目要求我们动态维护\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

于是就很好维护了不明白为什么这题上了黑

先看看代码

#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