题解 P3373 【【模板】线段树 2】

egret · 2019-11-06 21:46:23 · 题解

（这是一道超级水的模板题）

看到好多用运算优先级强制转化的题解，感觉挺巧妙的，但是我看到这个题的时候，完全没往这上面想

（就是完全没想到）

然后我想起了一条以前做的精(sang)妙(xin)绝(bing)伦(kuang)的题目，那条题目要维护三个区间和，好多修改操作，天真的我线段树WA成了**......

言归正传来讲讲这道题

实际上，本题的难点在于加法操作与乘法操作交替进行时的运算顺序会乱，所以就有了运算优先级规定的想法

但是——

假如再来几个操作不就很难处理了吗

所以，我要做的是——将操作统一！

怎么统一？

矩阵乘法！

-----------------------------------------------分割线----------------------------------------------

前置知识时间：线段树维护矩阵

基本概念请右转P1939 矩阵加速（又是模板题.jpg）

好了，学完矩阵乘法的你应该明白了它的基本性质，那么，线段树如何维护一个矩阵呢？

由于矩阵乘法满足结合律，因此，我们可以将线段树中的信息，懒标记的信息，以及每次修改操作都改为以矩阵实现

举个例子

线段树维护这样一个表格

表(1)

而每次的修改操作为区间乘上

表(2)

那么我们的懒标记也可以记录这样为的一个表格

表(3)

当整体修改区间时用(1)与(2)分别乘(3)

而下传标记时，即同样类似于修改操作进行乘法

上传子节点信息直接把子节点信息加给父亲节点即可

（其实说白了就是把原来的加法等操作改成矩阵乘法即可）

至于正确性，由于矩阵乘法满足结合律，那么在矩阵乘法操作的时候，将多个矩乘的操作先乘在标记上，然后下传的时候再乘在线段树的子节点上，这样子与暴力处理时，一个一个乘比较，显然就是运用了一个结合律

-----------------------------------------------分割线----------------------------------------------

滚回来讲这道题

上文说到我们要统一操作，讲了这么多想法已经很明显了

构造矩阵！

观察到本题由乘法与加法构成，因此我们计算时用到的值为原来的区间和以及区间长度 （废话）

那么我们构造矩阵

s代表维护的区间和，l代表该区间的长度

而每次的修改操作也是乘上一个矩阵

例如加法

而乘法的矩阵长这样

每个点的懒标记也是一个矩阵，初始如下

（为了保证该矩阵为一个“1”值，即乘上以后不变）

（上面几个矩阵乘下来的结果请读者自行验证）

那么按照上文所说把常规的线段树加法改成矩阵乘法即可

这种做法维护之后就可以将操作完全统一啦，这样子就再也不用烦先加还是先乘了，大家都是矩乘，平等对待 (还可以少写一个修改操作)

（注意：在子节点信息合并时当然是直接相加上传了，别想太多......）

PS：1.矩乘常数巨大，用循环过不了，所以得把循环拆开,详见代码

2.码风略丑将就着看看

完结撒花！

#include<bits/stdc++.h>
#define maxn 100010 
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
struct node{
    int l,r;
    ll s[2],p[2][2];
};
node tr[maxn<<2];
ll a[maxn];
int n,m,p;
void build(int x,int l,int r)
{
    tr[x].l=l;
    tr[x].r=r;
    tr[x].p[0][0]=1,tr[x].p[0][1]=0,tr[x].p[1][0]=0,tr[x].p[1][1]=1;
    if(l==r)
    {
        tr[x].s[0]=a[l];
        tr[x].s[1]=1;
        return;
    }
    int mid=l+r>>1,lc=x<<1,rc=x<<1|1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    tr[x].s[0]=(tr[lc].s[0]+tr[rc].s[0])%p;
    tr[x].s[1]=r-l+1;
}
void calc1(ll a[2],ll b[2][2])
{
    ll tmp[2]={0,0};
    tmp[0]=(a[0]*b[0][0]+a[1]*b[1][0])%p;
    tmp[1]=(a[0]*b[0][1]+a[1]*b[1][1])%p;
    a[0]=tmp[0];
    a[1]=tmp[1];
}
void calc2(ll a[2][2],ll b[2][2])
{
    ll tmp[2][2];
    tmp[0][0]=(a[0][0]*b[0][0]+a[0][1]*b[1][0])%p;
    tmp[0][1]=(a[0][0]*b[0][1]+a[0][1]*b[1][1])%p;
    tmp[1][0]=(a[1][0]*b[0][0]+a[1][1]*b[1][0])%p;
    tmp[1][1]=(a[1][0]*b[0][1]+a[1][1]*b[1][1])%p;
    a[0][0]=tmp[0][0];
    a[0][1]=tmp[0][1];
    a[1][0]=tmp[1][0];
    a[1][1]=tmp[1][1];
}
void down(int x)
{
    if(tr[x].p[0][0]==1&&tr[x].p[0][1]==0&&tr[x].p[1][0]==0&&tr[x].p[1][1]==1) return;
    int mid=tr[x].l+tr[x].r>>1,lc=x<<1,rc=x<<1|1;
    calc1(tr[lc].s,tr[x].p);
    calc1(tr[rc].s,tr[x].p);
    calc2(tr[lc].p,tr[x].p);
    calc2(tr[rc].p,tr[x].p);
    tr[x].p[0][0]=1,tr[x].p[0][1]=0,tr[x].p[1][0]=0,tr[x].p[1][1]=1;
}
void add(int x,int l,int r,ll v[2][2])
{
    if(l<=tr[x].l&&tr[x].r<=r)
    {
        calc1(tr[x].s,v);
        calc2(tr[x].p,v);
        return;
    }
    down(x);
    int mid=tr[x].l+tr[x].r>>1,lc=x<<1,rc=x<<1|1;
    if(l<=mid) add(lc,l,r,v);
    if(mid<r) add(rc,l,r,v);
    tr[x].s[0]=(tr[lc].s[0]+tr[rc].s[0])%p;
}
ll query(int x,int l,int r)
{
    if(l<=tr[x].l&&tr[x].r<=r) return tr[x].s[0];
    down(x);
    int mid=tr[x].l+tr[x].r>>1,lc=x<<1,rc=x<<1|1;
    ll tmp=0;
    if(l<=mid) tmp=query(lc,l,r);
    if(mid<r) tmp+=query(rc,l,r);
    return tmp%p;
}
int main()
{
    scanf("%d%d%lld",&n,&m,&p);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int op,l,r;
        ll x;
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d%lld",&l,&r,&x);
            ll v[2][2]={x,0,0,1};
            add(1,l,r,v);
        }
        if(op==2)
        {
            scanf("%d%d%lld",&l,&r,&x);
            ll v[2][2]={1,0,x,1};
            add(1,l,r,v);
        }
        if(op==3)
        {
            scanf("%d%d",&l,&r);
            printf("%lld\n",query(1,l,r));
        }
    }
}