那些相望相随的，彼此明亮的年纪

Imerance1018 · 2025-08-01 08:27:52 · 题解

提供一个思维难度不大的做法。（对比更无脑的矩阵乘法常数小很多）

Description

传送门

Solution

使用线段树维护 v，ab，a 和 b 的区间和，分别记作 sumv，sumab，suma，sumb，这些信息显然具有可合并性。

发现单独的加标记 adda，addb 无法下传到信息。注意到 v 的增加量一定是一个仅包含有 ab，a，b 和常数项的多项式，套路地定义 cab，ca，cb，c 表示在区间加了 adda 和 addb 后 v 的增加量中各项的系数，c 表示常数项。

同样可定义 sa，sb 和 s 表示在区间加 adda 和 addb 这一操作中 ab 的增加量中各项的系数，s 表示常数项。

那么标记下传到信息就很好写了，注意常数项要乘上区间长度。

标记间的合并直接推柿子，令 tag' 表示新下传的标记，那么 v 的增加量即为 cab'(sumab+sa \times suma+sb \times sumb +s)+ca'(suma+adda)+cb'(sumb+addb)+c，把贡献分别加到各个系数里去即可。

同理 ab 的增加量为 sa'(suma+adda)+sb'(sumb+addb)+s，拆开括号后把对应系数相加即可。

线段树其他部分不难写出，总时间复杂度 O(n \log n)。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,mod=1e8+7;
int n,q;
int v[N],b[N],a[N];

#define lc x<<1
#define rc x<<1|1
#define mid ((l+r)>>1)
struct Segtree
{
    struct D
    {
        int sumv,sumab,suma,sumb,len;
        D operator +(const D &x)const
        {
            return {(sumv+x.sumv)%mod,(sumab+x.sumab)%mod,(suma+x.suma)%mod,(sumb+x.sumb)%mod,len+(x.len)%mod};
        }
    }val[N<<2];
    struct M
    {
        int cab,ca,cb,c,adda,addb,sa,sb,s;
    }tag[N<<2];
    void pushup(int x)//合并信息
    {
        val[x].sumv=(val[lc].sumv+val[rc].sumv)%mod;
        val[x].sumab=(val[lc].sumab+val[rc].sumab)%mod;
        val[x].suma=(val[lc].suma+val[rc].suma)%mod;
        val[x].sumb=(val[lc].sumb+val[rc].sumb)%mod;
    }
    void upd(int x,M tg)//标记下传到信息，按定义写
    {
        val[x].sumv=(val[x].sumv+val[x].sumab*tg.cab%mod+val[x].suma*tg.ca%mod+val[x].sumb*tg.cb%mod+tg.c*val[x].len%mod)%mod;
        val[x].sumab=(val[x].sumab+val[x].suma*tg.sa%mod+val[x].sumb*tg.sb%mod+tg.s*val[x].len%mod)%mod;
        val[x].suma=(val[x].suma+tg.adda*val[x].len%mod)%mod;
        val[x].sumb=(val[x].sumb+tg.addb*val[x].len%mod)%mod;
    }
    void make_tag(int x,M tg)//标记间的合并
    {
        tag[x].cab=(tag[x].cab+tg.cab)%mod;
        tag[x].ca=(tag[x].ca+tg.ca+tg.cab*tag[x].sa%mod)%mod;
        tag[x].cb=(tag[x].cb+tg.cb+tg.cab*tag[x].sb%mod)%mod;
        tag[x].c=(tag[x].c+tg.c+tg.cab*tag[x].s%mod+tg.ca*tag[x].adda%mod+tg.cb*tag[x].addb%mod)%mod;

        tag[x].sa=(tag[x].sa+tg.sa)%mod;
        tag[x].sb=(tag[x].sb+tg.sb)%mod;
        tag[x].s=(tag[x].s+tg.s+tg.sa*tag[x].adda%mod+tg.sb*tag[x].addb%mod)%mod;

        tag[x].adda=(tag[x].adda+tg.adda)%mod;
        tag[x].addb=(tag[x].addb+tg.addb)%mod;
    }
    void pushdown(int x)
    {
        upd(lc,tag[x]);
        make_tag(lc,tag[x]);
        upd(rc,tag[x]);
        make_tag(rc,tag[x]);
        tag[x]={0,0,0,0,0,0,0,0,0};
    }

    //其他部分就是线段树板子了

    void build(int x,int l,int r)
    {
        val[x]={0,0,0,0,r-l+1};
        tag[x]={0,0,0,0,0,0,0,0,0};
        if(l==r)
        {
            val[x].sumv=v[l]%mod;
            val[x].sumab=a[l]*b[l]%mod;
            val[x].suma=a[l]%mod;
            val[x].sumb=b[l]%mod;
            return;
        }
        build(lc,l,mid);
        build(rc,mid+1,r);
        pushup(x);
    }
    void update(int x,int l,int r,int L,int R,M v)
    {
        if(L<=l&&r<=R)
        {
            upd(x,v);
            make_tag(x,v);
            return;
        }
        pushdown(x);
        if(L<=mid)update(lc,l,mid,L,R,v);
        if(mid+1<=R)update(rc,mid+1,r,L,R,v);
        pushup(x);
    }
    D query(int x,int l,int r,int L,int R)
    {
        if(L<=l&&r<=R)return val[x];
        pushdown(x);
        D res={0,0,0,0,0};
        if(L<=mid)res=res+query(lc,l,mid,L,R);
        if(mid+1<=R)res=res+query(rc,mid+1,r,L,R);
        return res;
    }
}tree;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>v[i]>>a[i]>>b[i];
    tree.build(1,1,n);
    int lst=0;
    while(q--)
    {
        int opt,t,l,r,x;
        cin>>opt>>t>>l>>r;
        if(opt!=1)cin>>x;
        tree.update(1,1,n,1,n,{t-lst,0,0,0,0,0,0,0,0});//处理时间流逝
        if(opt==1)
        {
            int res=tree.query(1,1,n,l,r).sumv;
            cout<<(res%mod+mod)%mod<<"\n";
        }
        else
        {
            if(opt==2)tree.update(1,1,n,l,r,{0,0,0,0,x,0,0,x,0});
            else if(opt==3)tree.update(1,1,n,l,r,{0,0,0,0,0,x,x,0,0});
            else tree.update(1,1,n,l,r,{0,0,0,x,0,0,0,0,0});
            //注意由于对标记的定义，修改 a 和 b 时对 ab 会造成增量，需要同步修改 sa 和 sb
        }

        lst=t;
    }
    return 0;
}
// in memory