题解 ABC455F - Merge Slimes 2

· · 题解

题解 ABC455F - Merge Slimes 2

其他题

自评：下位绿。

手速场毁我青春，只有不到 1900 perf。好在号上没分。

简要题意

有初值为 0、长度为 n 的数组，q 次询问，每次询问给定 u,v,w，先将下标在 [u,v] 内的数加上 w，再求下面问题的答案：

将区间内的各数进行合并，两个数 x,y 合并时得到一个新数 x+y 并产生 xy 的贡献，求合并成一个数后最大的总贡献。

后面的询问只继承前面的区间加，不继承前面的合并。

数据范围：n,q\le 10^5。

做法

首先请准备一句尽可能难听的粗话。

考虑合并问题的答案什么时候是最大的。你惊奇地发现，事实上由于合并完后的数是两数相加，所以每个数最后都会和其他所有数乘一遍，与具体的合并顺序无关。好的现在可以大声地喊出刚才准备的粗话来赞颂出题人的功德了。

于是我们需要求出每个数与其他数都乘一遍的答案。如果加上自己乘自己的贡献，那答案显然是区间和的平方；故实际的答案是区间和的平方 减去 区间每个数的平方的和。前者是线段树板子，后者其实也是，不过打 tag 的时候要用到完全平方公式 (a+b)^2=a^2+2ab+b^2，故原和为 a 的区间加上 b 之后各数和的平方就应该增加 2ab+b^2。注意别把那个 2 漏了，我因为这个浪费了 5 分钟。

复杂度 O(q\log n)。

//Please ignore those headfiles.I write them just because
//DEV-C++ won't support completion if i use <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<cctype>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<unordered_map>
#include<set>
#include<queue>
#define ll long long
#define ull unsigned long long
#define lf double
#define ld long double
#define LL __int128
#define ui unsigned int
using namespace std;
const ll mod=998244353;
struct node{
    ll ls,rs,s,ss,tag;
};
node t[200010];
ll n,q,u,v,w,p=2;
inline ll ksm(ll x,ll y){
    if(y==0)return 1;
    if(y==1)return x;
    ll tmp=ksm(x,y>>1);
    return y&1?tmp*tmp%mod*x%mod:tmp*tmp%mod;
}
void build(ll now,ll l,ll r){
    if(l==r){
        return ;
    }
    ll mid=(l+r>>1);
    t[now].ls=(p++);
    build(t[now].ls,l,mid);
    t[now].rs=(p++);
    build(t[now].rs,mid+1,r);
}
void pushdown(ll now,ll l,ll r){
    ll mid=(l+r>>1);
    t[t[now].ls].ss+=t[now].tag*t[now].tag%mod*(mid-l+1)%mod+t[now].tag*t[t[now].ls].s*2%mod;
    t[t[now].ls].s+=t[now].tag*(mid-l+1)%mod;
    t[t[now].ls].tag+=t[now].tag;
    t[t[now].rs].ss+=t[now].tag*t[now].tag%mod*(r-mid)%mod+t[now].tag*t[t[now].rs].s*2%mod;
    t[t[now].rs].s+=t[now].tag*(r-mid)%mod;
    t[t[now].rs].tag+=t[now].tag;
    t[t[now].ls].ss%=mod;
    t[t[now].ls].s%=mod;
    t[t[now].ls].tag%=mod;
    t[t[now].rs].ss%=mod;
    t[t[now].rs].s%=mod;
    t[t[now].rs].tag%=mod;
    t[now].tag=0;
}
void upd(ll now,ll l,ll r,ll L,ll R,ll c){
    pushdown(now,l,r);
    if(l>=L&&r<=R){
        t[now].ss+=(r-l+1)*c%mod*c%mod+t[now].s*c*2%mod;
        t[now].s+=(r-l+1)*c%mod;
        t[now].tag+=c;
        t[now].s%=mod;
        t[now].ss%=mod;
        t[now].tag%=mod;
        return ;
    }
    ll mid=(l+r>>1);
    if(L<=mid){
        upd(t[now].ls,l,mid,L,R,c);
    } 
    if(R>mid){
        upd(t[now].rs,mid+1,r,L,R,c);
    }
    t[now].s=t[t[now].ls].s+t[t[now].rs].s;
    t[now].ss=t[t[now].ls].ss+t[t[now].rs].ss;
    t[now].s%=mod;
    t[now].ss%=mod;
}
ll querys(ll now,ll l,ll r,ll L,ll R){
    pushdown(now,l,r);
    if(l>=L&&r<=R){
        return t[now].s;
    }
    ll mid=(l+r>>1),ans=0;
    if(L<=mid){
        ans+=querys(t[now].ls,l,mid,L,R);
    } 
    if(R>mid){
        ans+=querys(t[now].rs,mid+1,r,L,R);
    }
    return ans%mod;
}
ll queryss(ll now,ll l,ll r,ll L,ll R){
    pushdown(now,l,r);
    if(l>=L&&r<=R){
        return t[now].ss;
    }
    ll mid=(l+r>>1),ans=0;
    if(L<=mid){
        ans+=queryss(t[now].ls,l,mid,L,R);
    } 
    if(R>mid){
        ans+=queryss(t[now].rs,mid+1,r,L,R);
    }
    return ans%mod;
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>q;
    build(1,1,n);
    while(q--){
        cin>>u>>v>>w;
        upd(1,1,n,u,v,w);
        ll tmp=querys(1,1,n,u,v);
        cout<<(tmp*tmp%mod-queryss(1,1,n,u,v)+mod)%mod*ksm(2,mod-2)%mod<<endl;
    }
    return 0;
}