专栏文章

P9844

HHasNoName
P9844题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio2f5aw
此快照首次捕获于
2025/12/02 12:15
3 个月前
此快照最后确认于
2025/12/02 12:15
3 个月前
查看原文

思路

显然是线段树题。
但是区间历史和显然是主席树不好维护的，所以考虑用线段树维护矩阵。
先要知道 xk=ykx_k=y_k 的情况怎么做。
由于 (a+v)2=a2+2av+v2(a+v)^2=a^2+2av+v^2，所以考虑对于线段树上的每个节点维护区间和、区间平方和。
考虑离线。把所有询问拆成两边分别处理。
然后构造矩阵 [cbalen]\begin{bmatrix}c&b&a&len\end{bmatrix} 分别表示区间历史平方和、区间平方和、区间和、区间唱的。
对于增加操作，设增加 vv，则乘上 [1000010002v100v2v1]\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&2v&1&0\\0&v^2&v&1\end{bmatrix}。
如果要统计历史和，则乘上 [1000110000100001]\begin{bmatrix}1&0&0&0\\1&1&0&0\\0&0&1&0\\0&0&0&1\end{bmatrix}。
注意要分开乘。
然后可以通过对矩阵中定值的分析优化常数。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
const int N=50005;
const int MOD=1000000007;
typedef long long ll;
struct M//矩阵乘法
{
    ll a[4][4];
    inline void mem()
    {
        a[0][0]=0;
        a[1][0]=0;a[1][1]=0;
        a[2][0]=0;a[2][1]=0;a[2][2]=0;
        a[3][0]=0;a[3][1]=0;a[3][2]=0;a[3][3]=0;
    }
    inline void init()
    {
        a[0][0]=1;
        a[1][0]=0;a[1][1]=1;
        a[2][0]=0;a[2][1]=0;a[2][2]=1;
        a[3][0]=0;a[3][1]=0;a[3][2]=0;a[3][3]=1;
    }
    inline M operator*(struct M b)
    {
        M ans;ans.init();
        ans.a[1][0]=(a[1][0]+b.a[1][0])%MOD;
        ans.a[2][0]=(a[2][0]+a[2][1]*b.a[1][0]+b.a[2][0])%MOD;
        ans.a[2][1]=(a[2][1]+b.a[2][1])%MOD;
        ans.a[3][0]=(a[3][0]+a[3][1]*b.a[1][0]+a[3][2]*b.a[2][0]+b.a[3][0])%MOD;
        ans.a[3][1]=(a[3][1]+a[3][2]*b.a[2][1]+b.a[3][1])%MOD;
        ans.a[3][2]=(a[3][2]+b.a[3][2])%MOD;//卡常
        return ans;
    }
};
struct seg//线段树
{
    ll c,b,a,len;
    M t;
}w[8*N];
struct Q
{
    int x,y,id,t;
};
ll a[N],l[N],r[N],ad[N],ans[N];
vector<Q>q[N];
void pushup(int u)
{
    w[u].c=(w[u<<1].c+w[u<<1|1].c)%MOD;
    w[u].b=(w[u<<1].b+w[u<<1|1].b)%MOD;
    w[u].a=(w[u<<1].a+w[u<<1|1].a)%MOD;
    w[u].len=w[u<<1].len+w[u<<1|1].len;
}
void pushdown(int u)
{
    M t=w[u].t;w[u].t.init();
    w[u<<1].t=w[u<<1].t*t;
    w[u<<1|1].t=w[u<<1|1].t*t;
    ll c,b,a;
    c=w[u<<1].c+w[u<<1].b*t.a[1][0]+w[u<<1].a*t.a[2][0]+w[u<<1].len*t.a[3][0];
    b=w[u<<1].b+w[u<<1].a*t.a[2][1]+w[u<<1].len*t.a[3][1];
    a=w[u<<1].a+w[u<<1].len*t.a[3][2];
    w[u<<1].c=c%MOD;w[u<<1].b=b%MOD;w[u<<1].a=a%MOD;
    c=w[u<<1|1].c+w[u<<1|1].b*t.a[1][0]+w[u<<1|1].a*t.a[2][0]+w[u<<1|1].len*t.a[3][0];
    b=w[u<<1|1].b+w[u<<1|1].a*t.a[2][1]+w[u<<1|1].len*t.a[3][1];
    a=w[u<<1|1].a+w[u<<1|1].len*t.a[3][2];
    w[u<<1|1].c=c%MOD;w[u<<1|1].b=b%MOD;w[u<<1|1].a=a%MOD;
}
void build(int u,int l,int r)
{
    w[u].t.init();
    if(l==r)
    {
        w[u].c=0;
        w[u].b=a[l]*a[l]%MOD;
        w[u].a=a[l];
        w[u].len=1;
        return;
    }
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}
void mul(int u,int l,int r,int x,int y,M k)
{
    pushdown(u);
    if(l>=x&&r<=y)
    {
        w[u].t=w[u].t*k;
        ll c,b,a;
        c=w[u].c+w[u].b*k.a[1][0]+w[u].a*k.a[2][0]+w[u].len*k.a[3][0];
        b=w[u].b+w[u].a*k.a[2][1]+w[u].len*k.a[3][1];
        a=w[u].a+w[u].len*k.a[3][2];
        w[u].c=c%MOD;w[u].b=b%MOD;w[u].a=a%MOD;
        return;
    }
    int mid=(l+r)>>1;
    if(mid>=x)mul(u<<1,l,mid,x,y,k);
    if(mid<y)mul(u<<1|1,mid+1,r,x,y,k);
    pushup(u);
}
ll get(int u,int l,int r,int x,int y)
{
    pushdown(u);
    if(l>=x&&r<=y)return w[u].c;
    int mid=(l+r)>>1;ll sum=0;
    if(mid>=x)sum+=get(u<<1,l,mid,x,y);
    if(mid<y)sum+=get(u<<1|1,mid+1,r,x,y);
    return sum;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,T;
    cin>>n>>m>>T;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);
    for(int i=1;i<=m;i++)
        cin>>l[i]>>r[i]>>ad[i];
    for(int i=1;i<=T;i++)
    {
        int l,r,x,y;
        cin>>x>>y>>l>>r;
        q[r].push_back({x,y,i,1});
        if(l>0)q[l-1].push_back({x,y,i,-1});//离线
    }
    l[0]=1;r[0]=n;
    M A,B;A.init();B.init();
    for(int i=0;i<=m;i++)
    {
        A.a[3][2]=ad[i];
        A.a[2][1]=2*ad[i]%MOD;
        A.a[3][1]=ad[i]*ad[i]%MOD;
        B.a[1][0]=1;
        mul(1,1,n,l[i],r[i],A);//增加
        mul(1,1,n,1,n,B);//复制b->c
        for(int j=0;j<(int)q[i].size();j++)
            ans[q[i][j].id]+=get(1,1,n,q[i][j].x,q[i][j].y)*q[i][j].t;//计算答案
    }
    for(int i=1;i<=T;i++)cout<<(ans[i]%MOD+MOD)%MOD<<'\n';//一定为正数
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...