矩阵与线段树标记

First Post:

Last Update:

Word Count:
6.5k

Read Time:
37 min

今天在做 [NOIP2022] 比赛 的时候，发现用矩阵刻画线段树是个非常好的东西，遂记录下来。

矩阵维护普通信息

我们先来看最基础的线段树操作：区间加，区间求和。

因为维护区间和需要长度，所以把长度也放到矩阵里，易得区间加转移为：

这里的矩阵乘法是 矩乘。

再困难一点：区间加，区间乘，区间求和。

易得区间乘转移为：

修改只需要和普通线段树一样打标记即可，复杂度 。

这里给出【模板】线段树 2 的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include"bits/stdc++.h"
#define re register
#define int long long
#define ls(p) tr[p].ls
#define rs(p) tr[p].rs
using namespace std;
const int maxn=1e5+10,maxm=2;
int n,m,mod,rt,segcnt;
struct matrix{
    int n,m;
    int a[maxm][maxm];
    inline void init(int _n,int _m){n=_n,m=_m;memset(a,0,sizeof(a));}
    inline void build(){for(re int i=0;i<n;++i) a[i][i]=1;}
    inline matrix operator +(matrix B){
        matrix res;
        res.init(n,m);
        for(re int i=0;i<n;++i){
            for(re int j=0;j<m;++j){
                res.a[i][j]=(a[i][j]+B.a[i][j])%mod;
            }
        }
        return res;
    }
    inline matrix operator *(matrix B){
        matrix res;
        res.init(n,B.m);
        for(re int i=0;i<n;++i){
            for(re int j=0;j<B.m;++j){
                for(re int k=0;k<m;++k){
                    res.a[i][j]+=a[i][k]*B.a[k][j];
                    res.a[i][j]%=mod;
                }
            }
        }
        return res;
    }
    inline bool operator !=(matrix B){
        for(re int i=0;i<n;++i){
            for(re int j=0;j<m;++j){
                if(a[i][j]!=B.a[i][j]) return 1;
            }
        }
        return 0;
    }
}I;
struct tree{
    int ls,rs;
    matrix s,tag;
}tr[maxn<<1];
inline void up(int p){tr[p].s=tr[ls(p)].s+tr[rs(p)].s;}
inline void add(int p,matrix val){tr[p].s=val*tr[p].s,tr[p].tag=val*tr[p].tag;}
inline void down(int p){if(tr[p].tag!=I) add(ls(p),tr[p].tag),add(rs(p),tr[p].tag),tr[p].tag=I;}
inline void build(int l,int r,int &p){
    p=++segcnt;tr[p].s.init(2,1),tr[p].tag.init(2,2);tr[p].tag=I;
    if(l==r){cin>>tr[p].s.a[0][0],tr[p].s.a[1][0]=1;return;}
    int mid=(l+r)>>1;
    build(l,mid,ls(p)),build(mid+1,r,rs(p));
    up(p);
}
inline void update(int l,int r,int L,int R,matrix val,int p){
    if(l>=L&&r<=R){add(p,val);return;}
    int mid=(l+r)>>1;down(p);
    if(L<=mid) update(l,mid,L,R,val,ls(p));
    if(R>mid) update(mid+1,r,L,R,val,rs(p));
    up(p);
}
inline matrix query(int l,int r,int L,int R,int p){
    if(l>=L&&r<=R) return tr[p].s;
    int mid=(l+r)>>1;down(p);
    if(R<=mid) return query(l,mid,L,R,ls(p));
    if(L>mid) return query(mid+1,r,L,R,rs(p));
    return query(l,mid,L,R,ls(p))+query(mid+1,r,L,R,rs(p));
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>mod;I.init(2,2),I.build();build(1,n,rt);
    for(re int i=1,op,l,r,k;i<=m;++i){
        cin>>op>>l>>r;
        if(op==1){
            cin>>k;
            matrix val;val.init(2,2);
            val.a[0][0]=k,val.a[1][1]=1;
            update(1,n,l,r,val,rt);
        }
        if(op==2){
            cin>>k;
            matrix val;val.init(2,2);
            val.a[0][0]=val.a[1][1]=1,val.a[0][1]=k;
            update(1,n,l,r,val,rt);
        }
        if(op==3) cout<<query(1,n,l,r,rt).a[0][0]<<'\n';
    }
    return 0;	
}

把操作换一下：区间加，区间推平，区间最大值。

事实上，区间推平也是可以用矩阵刻画的：只需要在矩阵里加个 即可。

易得区间加转移为：

易得区间推平转移为：

这里的矩阵乘法是 矩乘。

这里给出 扶苏的问题 的代码：

upd：然而因为矩阵乘法的常数无法通过，但我感觉把矩阵展开一下啥的应该能卡过去，我懒得写了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include"bits/stdc++.h"
#define re register
#define int long long
#define ls(p) tr[p].ls
#define rs(p) tr[p].rs
using namespace std;
const int maxn=1e6+10,maxm=2,inf=1e18;
int n,m,rt,segcnt;
struct matrix{
    int n,m;
    int a[maxm][maxm];
    inline void init(int _n,int _m){n=_n,m=_m;for(re int i=0;i<n;++i) for(re int j=0;j<m;++j) a[i][j]=-inf;}
    inline void build(){for(re int i=0;i<n;++i) a[i][i]=0;}
    inline matrix operator +(matrix B){
        matrix res;
        res.init(n,m);
        for(re int i=0;i<n;++i){
            for(re int j=0;j<m;++j){
                res.a[i][j]=max(a[i][j],B.a[i][j]);
            }
        }
        return res;
    }
    inline matrix operator *(matrix B){
        matrix res;
        res.init(n,B.m);
        for(re int i=0;i<n;++i){
            for(re int j=0;j<B.m;++j){
                for(re int k=0;k<m;++k){
                    res.a[i][j]=max(res.a[i][j],a[i][k]+B.a[k][j]);
                }
            }
        }
        return res;
    }
    inline bool operator !=(matrix B){
        for(re int i=0;i<n;++i){
            for(re int j=0;j<m;++j){
                if(a[i][j]!=B.a[i][j]) return 1;
            }
        }
        return 0;
    }
}I;
struct tree{
    int ls,rs;
    matrix s,tag;
}tr[maxn<<1];
inline void up(int p){tr[p].s=tr[ls(p)].s+tr[rs(p)].s;}
inline void add(int p,matrix val){tr[p].s=val*tr[p].s,tr[p].tag=val*tr[p].tag;}
inline void down(int p){if(tr[p].tag!=I) add(ls(p),tr[p].tag),add(rs(p),tr[p].tag),tr[p].tag=I;}
inline void build(int l,int r,int &p){
    p=++segcnt;tr[p].s.init(2,1),tr[p].tag.init(2,2);tr[p].tag=I;
    if(l==r){cin>>tr[p].s.a[0][0],tr[p].s.a[1][0]=0;return;}
    int mid=(l+r)>>1;
    build(l,mid,ls(p)),build(mid+1,r,rs(p));
    up(p);
}
inline void update(int l,int r,int L,int R,matrix val,int p){
    if(l>=L&&r<=R){add(p,val);return;}
    int mid=(l+r)>>1;down(p);
    if(L<=mid) update(l,mid,L,R,val,ls(p));
    if(R>mid) update(mid+1,r,L,R,val,rs(p));
    up(p);
}
inline matrix query(int l,int r,int L,int R,int p){
    if(l>=L&&r<=R) return tr[p].s;
    int mid=(l+r)>>1;down(p);
    if(R<=mid) return query(l,mid,L,R,ls(p));
    if(L>mid) return query(mid+1,r,L,R,rs(p));
    return query(l,mid,L,R,ls(p))+query(mid+1,r,L,R,rs(p));
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;I.init(2,2),I.build();build(1,n,rt);
    for(re int i=1,op,l,r,k;i<=m;++i){
        cin>>op>>l>>r;
        if(op==3) cout<<query(1,n,l,r,rt).a[0][0]<<'\n';
        if(op==1){
            cin>>k;
            matrix val;val.init(2,2);
            val.a[0][1]=k,val.a[1][1]=0;
            update(1,n,l,r,val,rt);
        }
        if(op==2){
            cin>>k;
            matrix val;val.init(2,2);
            val.a[0][0]=k,val.a[1][1]=0;
            update(1,n,l,r,val,rt);
        }
    }
    return 0;	
}

再加强一下呢：区间加，区间乘，区间推平，区间最大值，区间求和。

然而区间最大值和区间和无法在一个矩阵里维护，因为一个需要 矩乘，一个需要 矩乘。

但可以用两个矩阵分别维护，标记分开打即可。

具体的不写了，跟之前的一样。

可以发现，矩阵的刻画让标记的形式统一了，从而避免了对标记下放顺序的讨论。

矩阵维护历史信息

此外，矩阵还能把历史信息的维护变的十分清晰。

例题1：CPU 监控

一道维护历史最值的题目。

只需要把东西都塞到矩阵里就行了，设 为最大值， 为历史最大值，易得区间加转移为：

区间推平转移为：

这里的矩阵乘法是 矩乘。

代码极其好写。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include"bits/stdc++.h"
#define re register
#define int long long
#define ls(p) tr[p].ls
#define rs(p) tr[p].rs
using namespace std;
const int maxn=1e5+10,maxm=3,inf=1e18;
int n,m,rt,segcnt;
struct matrix{
    int n,m;
    int a[maxm][maxm];
    inline void init(int _n,int _m){n=_n,m=_m;for(re int i=0;i<n;++i) for(re int j=0;j<m;++j) a[i][j]=-inf;}
    inline void build(){for(re int i=0;i<n;++i) a[i][i]=0;}
    inline matrix operator +(matrix B){
        matrix res;
        res.init(n,m);
        for(re int i=0;i<n;++i){
            for(re int j=0;j<m;++j){
                res.a[i][j]=max(a[i][j],B.a[i][j]);
            }
        }
        return res;
    }
    inline matrix operator *(matrix B){
        matrix res;
        res.init(n,B.m);
        for(re int i=0;i<n;++i){
            for(re int j=0;j<B.m;++j){
                for(re int k=0;k<m;++k){
                    res.a[i][j]=max(res.a[i][j],a[i][k]+B.a[k][j]);
                }
            }
        }
        return res;
    }
    inline bool operator !=(matrix B){
        for(re int i=0;i<n;++i){
            for(re int j=0;j<m;++j){
                if(a[i][j]!=B.a[i][j]) return 1;
            }
        }
        return 0;
    }
}I;
struct tree{
    int ls,rs;
    matrix s,tag;
}tr[maxn<<1];
inline void up(int p){tr[p].s=tr[ls(p)].s+tr[rs(p)].s;}
inline void add(int p,matrix val){tr[p].s=val*tr[p].s,tr[p].tag=val*tr[p].tag;}
inline void down(int p){if(tr[p].tag!=I) add(ls(p),tr[p].tag),add(rs(p),tr[p].tag),tr[p].tag=I;}
inline void build(int l,int r,int &p){
    p=++segcnt;tr[p].s.init(3,1),tr[p].tag.init(3,3);tr[p].tag=I;
    if(l==r){cin>>tr[p].s.a[0][0],tr[p].s.a[1][0]=tr[p].s.a[0][0],tr[p].s.a[2][0]=0;return;}
    int mid=(l+r)>>1;
    build(l,mid,ls(p)),build(mid+1,r,rs(p));
    up(p);
}
inline void update(int l,int r,int L,int R,matrix val,int p){
    if(l>=L&&r<=R){add(p,val);return;}
    int mid=(l+r)>>1;down(p);
    if(L<=mid) update(l,mid,L,R,val,ls(p));
    if(R>mid) update(mid+1,r,L,R,val,rs(p));
    up(p);
}
inline matrix query(int l,int r,int L,int R,int p){
    if(l>=L&&r<=R) return tr[p].s;
    int mid=(l+r)>>1;down(p);
    if(R<=mid) return query(l,mid,L,R,ls(p));
    if(L>mid) return query(mid+1,r,L,R,rs(p));
    return query(l,mid,L,R,ls(p))+query(mid+1,r,L,R,rs(p));
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;I.init(3,3),I.build();build(1,n,rt);
    cin>>m;
    for(re int i=1,l,r,k;i<=m;++i){
        char op;cin>>op>>l>>r;
        if(op=='Q') cout<<query(1,n,l,r,rt).a[0][0]<<'\n';
        if(op=='A') cout<<query(1,n,l,r,rt).a[1][0]<<'\n';
        if(op=='P'){
            cin>>k;
            matrix val;val.init(3,3);
            val.a[0][0]=val.a[1][0]=k;
            val.a[1][1]=val.a[2][2]=0;
            update(1,n,l,r,val,rt);
        }
        if(op=='C'){
            cin>>k;
            matrix val;val.init(3,3);
            val.a[0][2]=val.a[1][2]=k;
            val.a[1][1]=val.a[2][2]=0;
            update(1,n,l,r,val,rt);
        }
    }
    return 0;	
}

例题2:[NOIP2022] 比赛

一道维护历史版本和的题目。

对于这种区间子区间问题，很常见的做法是离线扫描线，然后线段树维护历史信息和。

这道题前面部分就不讲了，和 Pudding Monsters 几乎一样，单调栈维护一下就行。

我们只考虑这样一个问题：

有两个序列 ，维护如下操作：

  1. 对 区间加。
  2. 对 区间加。
  3. 查询 的区间历史版本和。

这里我遇到了一个不太懂的东西：双半群模型。感兴趣的可以了解一下。

容易发现，我们需要维护： 的区间和， 的区间和， 的区间和， 的区间历史版本和。

设 的区间和为 ， 的区间历史版本和为 。

直接把这堆东西塞到矩阵里，易得对 区间加的转移为：

易得对 区间加的转移为：

上面的转移里没有更新历史版本和，我们还需要更新这个东西。

易得转移为：

这里的矩阵乘法是 矩乘。

但这个矩阵太大了，导致复杂度也很高。

可以发现，这个矩阵大部分都是 ，根本用不上，所以把矩阵展开即可。

那么怎么展开呢？

可以发现，有用的贡献只有 这五种，所以只需要记录系数即可。

然后你高兴的写起了代码，结果发现不对。

这是因为有用的贡献其实有九种，这条贡献链为 ，所以要把这九种贡献的系数都得记录下来。

具体的转移可以用矩阵乘法推一下或者根据这条贡献链理解一下，这里不详细推了，具体可以见代码注释。

这是一份朴素的矩阵代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include"bits/stdc++.h"
#define re register
#define int unsigned long long
#define ls(p) tr[p].ls
#define rs(p) tr[p].rs
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int maxn=2.5e5+10,maxm=5;
int n,m,rt,segcnt;
int A[maxn],B[maxn],ans[maxn];
vector<pii> q[maxn];
struct Stack{
    int top;
    int stk[maxn];
}a,b;
struct matrix{
    int n,m;
    int a[maxm][maxm];
    inline void init(int _n,int _m){n=_n,m=_m;memset(a,0,sizeof a);}
    inline void build(){for(re int i=0;i<n;++i) a[i][i]=1;}
    inline matrix operator +(matrix B){
        matrix res;
        res.init(n,m);
        for(re int i=0;i<n;++i){
            for(re int j=0;j<m;++j){
                res.a[i][j]=a[i][j]+B.a[i][j];
            }
        }
        return res;
    }
    inline matrix operator *(matrix B){
        matrix res;
        res.init(n,B.m);
        for(re int i=0;i<n;++i){
            for(re int j=0;j<B.m;++j){
                for(re int k=0;k<m;++k){
                    res.a[i][j]+=a[i][k]*B.a[k][j];
                }
            }
        }
        return res;
    }
    inline bool operator !=(matrix B){
        for(re int i=0;i<n;++i){
            for(re int j=0;j<m;++j){
                if(a[i][j]!=B.a[i][j]) return 1;
            }
        }
        return 0;
    }
}I,upd;
struct tree{
    int ls,rs;
    matrix s,tag;
}tr[maxn<<1];
inline void up(int p){tr[p].s=tr[ls(p)].s+tr[rs(p)].s;}
inline void add(int p,matrix val){tr[p].s=val*tr[p].s,tr[p].tag=val*tr[p].tag;}
inline void down(int p){if(tr[p].tag!=I) add(ls(p),tr[p].tag),add(rs(p),tr[p].tag),tr[p].tag=I;}
inline void build(int l,int r,int &p){
    p=++segcnt;tr[p].s.init(5,1),tr[p].tag.init(5,5);tr[p].tag=I;
    if(l==r){
        tr[p].s.a[0][0]=A[l];
        tr[p].s.a[1][0]=B[l];
        tr[p].s.a[2][0]=A[l]*B[l];
        tr[p].s.a[3][0]=0;
        tr[p].s.a[4][0]=1;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,ls(p)),build(mid+1,r,rs(p));
    up(p);
}
inline void update(int l,int r,int L,int R,matrix val,int p){
    if(l>=L&&r<=R){add(p,val);return;}
    int mid=(l+r)>>1;down(p);
    if(L<=mid) update(l,mid,L,R,val,ls(p));
    if(R>mid) update(mid+1,r,L,R,val,rs(p));
    up(p);
}
inline matrix query(int l,int r,int L,int R,int p){
    if(l>=L&&r<=R) return tr[p].s;
    int mid=(l+r)>>1;down(p);
    if(R<=mid) return query(l,mid,L,R,ls(p));
    if(L>mid) return query(mid+1,r,L,R,rs(p));
    return query(l,mid,L,R,ls(p))+query(mid+1,r,L,R,rs(p));
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int _;cin>>_;
    cin>>n;
    for(re int i=1;i<=n;++i) cin>>A[i];
    for(re int i=1;i<=n;++i) cin>>B[i];
    I.init(5,5),I.build();build(1,n,rt);
    upd.init(5,5),upd.build();upd.a[3][2]=1;
    cin>>m;
    for(re int i=1,l,r;i<=m;++i){
        cin>>l>>r;
        q[r].push_back({l,i});
    }
    for(re int i=1;i<=n;++i){
        while(a.top&&A[a.stk[a.top]]<A[i]){
            matrix val;val.init(5,5);val=I;
            val.a[0][4]=val.a[2][1]=A[i]-A[a.stk[a.top]];
            update(1,n,a.stk[a.top-1]+1,a.stk[a.top],val,rt);
            --a.top;
        }
        a.stk[++a.top]=i;
        while(b.top&&B[b.stk[b.top]]<B[i]){
            matrix val;val.init(5,5);val=I;
            val.a[1][4]=val.a[2][0]=B[i]-B[b.stk[b.top]];
            update(1,n,b.stk[b.top-1]+1,b.stk[b.top],val,rt);
            --b.top;
        }
        b.stk[++b.top]=i;
        update(1,n,1,i,upd,rt);
        for(auto x:q[i]) ans[x.se]=query(1,n,x.fi,i,rt).a[3][0];
    }
    for(re int i=1;i<=m;++i) cout<<ans[i]<<'\n';
    return 0;	
}

这是一份拆开矩阵的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include"bits/stdc++.h"
#define re register
#define int unsigned long long
#define ls(p) tr[p].ls
#define rs(p) tr[p].rs
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int maxn=2.5e5+10,maxm=9;
int n,m,rt,segcnt;
int A[maxn],B[maxn],ans[maxn];
vector<pii> q[maxn];
struct Stack{
    int top;
    int stk[maxn];
}a,b;
struct matrix{
    int a[maxm];
    /*0:len->A 的贡献：直接加*/
    /*1:len->B 的贡献：直接加*/
    /*2:len->AB 的贡献：额外加上 len->A 的贡献*A->AB 的贡献+len->B 的贡献*B->AB 的贡献*/
    /*3:len->AB' 的贡献：额外加上 len->A 的贡献*A->AB' 的贡献+len->B 的贡献*B->AB' 的贡献+len->AB 的贡献*AB->AB' 的贡献*/
    /*4:A->AB 的贡献：直接加*/
    /*5:B->AB 的贡献：直接加*/
    /*6:A->AB' 的贡献：额外加上 A->AB 的贡献*AB->AB' 的贡献*/
    /*7:B->AB' 的贡献：额外加上 B->AB 的贡献*AB->AB' 的贡献*/
    /*8:AB->AB' 的贡献：直接加*/
    inline matrix operator * (const matrix &val)const{
        return{
            a[0]+val.a[0],
            a[1]+val.a[1],
            a[2]+val.a[2]+a[0]*val.a[4]+a[1]*val.a[5],
            a[3]+val.a[3]+a[0]*val.a[6]+a[1]*val.a[7]+a[2]*val.a[8],
            a[4]+val.a[4],a[5]+val.a[5],
            a[6]+val.a[6]+a[4]*val.a[8],
            a[7]+val.a[7]+a[5]*val.a[8],
            a[8]+val.a[8]
        };
    }
    inline void clear(){memset(a,0,sizeof a);}
};
matrix upd={0,0,0,0,0,0,0,0,1};
struct Data{
    int a,b,ab,AB,len;
    inline void init(int A,int B){a=A,b=B,ab=A*B,AB=0,len=1;}
    inline Data operator * (const matrix &tag)const{
        return{
            a+len*tag.a[0],
            b+len*tag.a[1],
            ab+len*tag.a[2]+a*tag.a[4]+b*tag.a[5],
            AB+len*tag.a[3]+a*tag.a[6]+b*tag.a[7]+ab*tag.a[8],
            len
        };
    }
    inline Data operator + (const Data &s)const{return {a+s.a,b+s.b,ab+s.ab,AB+s.AB,len+s.len};}
};
struct tree{
    int ls,rs;
    Data s;
    matrix tag;
}tr[maxn<<1];
inline void up(int p){tr[p].s=tr[ls(p)].s+tr[rs(p)].s;}
inline void add(int p,matrix val){tr[p].s=tr[p].s*val,tr[p].tag=tr[p].tag*val;}
inline void down(int p){add(ls(p),tr[p].tag),add(rs(p),tr[p].tag),tr[p].tag.clear();}
inline void build(int l,int r,int &p){
    p=++segcnt;
    if(l==r){tr[p].s.init(A[l],B[l]);return;}
    int mid=(l+r)>>1;
    build(l,mid,ls(p)),build(mid+1,r,rs(p));
    up(p);
}
inline void update(int l,int r,int L,int R,matrix val,int p){
    if(l>=L&&r<=R){add(p,val);return;}
    int mid=(l+r)>>1;down(p);
    if(L<=mid) update(l,mid,L,R,val,ls(p));
    if(R>mid) update(mid+1,r,L,R,val,rs(p));
    up(p);
}
inline Data query(int l,int r,int L,int R,int p){
    if(l>=L&&r<=R) return tr[p].s;
    int mid=(l+r)>>1;down(p);
    if(R<=mid) return query(l,mid,L,R,ls(p));
    if(L>mid) return query(mid+1,r,L,R,rs(p));
    return query(l,mid,L,R,ls(p))+query(mid+1,r,L,R,rs(p));
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int _;cin>>_;
    cin>>n;
    for(re int i=1;i<=n;++i) cin>>A[i];
    for(re int i=1;i<=n;++i) cin>>B[i];
    build(1,n,rt);
    cin>>m;
    for(re int i=1,l,r;i<=m;++i){
        cin>>l>>r;
        q[r].push_back({l,i});
    }
    for(re int i=1;i<=n;++i){
        while(a.top&&A[a.stk[a.top]]<A[i]){
            matrix val={A[i]-A[a.stk[a.top]],0,0,0,0,A[i]-A[a.stk[a.top]],0,0,0};
            update(1,n,a.stk[a.top-1]+1,a.stk[a.top],val,rt);
            --a.top;
        }
        a.stk[++a.top]=i;
        while(b.top&&B[b.stk[b.top]]<B[i]){
            matrix val={0,B[i]-B[b.stk[b.top]],0,0,B[i]-B[b.stk[b.top]],0,0,0,0};
            update(1,n,b.stk[b.top-1]+1,b.stk[b.top],val,rt);
            --b.top;
        }
        b.stk[++b.top]=i;
        update(1,n,1,i,upd,rt);
        for(auto x:q[i]) ans[x.se]=query(1,n,x.fi,i,rt).AB;
    }
    for(re int i=1;i<=m;++i) cout<<ans[i]<<'\n';
    return 0;   
}

[HNOI2016] 序列

几乎是上道题的双倍经验。

题意：多次询问，求 。

直接单调栈+扫描线+维护历史和即可。

朴素矩阵乘法也能过，懒得拆开了。

但这题事实上是存在更优秀的在线做法的，想学习的可以看题解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include"bits/stdc++.h"
#define re register
#define int long long
#define ls(p) tr[p].ls
#define rs(p) tr[p].rs
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int maxn=1e5+10,maxm=3;
int n,m,rt,segcnt;
int a[maxn],ans[maxn];
vector<pii> q[maxn];
struct Stack{
    int top;
    int stk[maxn];
}mn;
struct matrix{
    int n,m;
    int a[maxm][maxm];
    inline void init(int _n,int _m){n=_n,m=_m;memset(a,0,sizeof a);}
    inline void build(){for(re int i=0;i<n;++i) a[i][i]=1;}
    inline matrix operator +(matrix B){
        matrix res;
        res.init(n,m);
        for(re int i=0;i<n;++i){
            for(re int j=0;j<m;++j){
                res.a[i][j]=a[i][j]+B.a[i][j];
            }
        }
        return res;
    }
    inline matrix operator *(matrix B){
        matrix res;
        res.init(n,B.m);
        for(re int i=0;i<n;++i){
            for(re int j=0;j<B.m;++j){
                for(re int k=0;k<m;++k){
                    res.a[i][j]+=a[i][k]*B.a[k][j];
                }
            }
        }
        return res;
    }
    inline bool operator !=(matrix B){
        for(re int i=0;i<n;++i){
            for(re int j=0;j<m;++j){
                if(a[i][j]!=B.a[i][j]) return 1;
            }
        }
        return 0;
    }
}I,upd;
struct tree{
    int ls,rs;
    matrix s,tag;
}tr[maxn<<1];
inline void up(int p){tr[p].s=tr[ls(p)].s+tr[rs(p)].s;}
inline void add(int p,matrix val){tr[p].s=val*tr[p].s,tr[p].tag=val*tr[p].tag;}
inline void down(int p){if(tr[p].tag!=I) add(ls(p),tr[p].tag),add(rs(p),tr[p].tag),tr[p].tag=I;}
inline void build(int l,int r,int &p){
    p=++segcnt;tr[p].s.init(3,1),tr[p].tag.init(3,3);tr[p].tag=I;
    if(l==r){
        tr[p].s.a[0][0]=a[l];
        tr[p].s.a[1][0]=0;
        tr[p].s.a[2][0]=1;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,ls(p)),build(mid+1,r,rs(p));
    up(p);
}
inline void update(int l,int r,int L,int R,matrix val,int p){
    if(l>=L&&r<=R){add(p,val);return;}
    int mid=(l+r)>>1;down(p);
    if(L<=mid) update(l,mid,L,R,val,ls(p));
    if(R>mid) update(mid+1,r,L,R,val,rs(p));
    up(p);
}
inline matrix query(int l,int r,int L,int R,int p){
    if(l>=L&&r<=R) return tr[p].s;
    int mid=(l+r)>>1;down(p);
    if(R<=mid) return query(l,mid,L,R,ls(p));
    if(L>mid) return query(mid+1,r,L,R,rs(p));
    return query(l,mid,L,R,ls(p))+query(mid+1,r,L,R,rs(p));
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(re int i=1;i<=n;++i) cin>>a[i];
    I.init(3,3),I.build();build(1,n,rt);
    upd.init(3,3),upd.build();upd.a[1][0]=1;
    for(re int i=1,l,r;i<=m;++i){
        cin>>l>>r;
        q[r].push_back({l,i});
    }
    for(re int i=1;i<=n;++i){
        while(mn.top&&a[mn.stk[mn.top]]>a[i]){
            matrix val;val.init(3,3);val=I;
            val.a[0][2]=a[i]-a[mn.stk[mn.top]];
            update(1,n,mn.stk[mn.top-1]+1,mn.stk[mn.top],val,rt);
            --mn.top;
        }
        mn.stk[++mn.top]=i;
        update(1,n,1,i,upd,rt);
        for(auto x:q[i]) ans[x.se]=query(1,n,x.fi,i,rt).a[1][0];
    }
    for(re int i=1;i<=m;++i) cout<<ans[i]<<'\n';
    return 0;	
}

参考文章：

算法学习笔记(34): 矩阵乘法与线段树标记 - jeefy - 博客园

区间历史操作，从矩阵乘法到标记 - 洛谷专栏

题解 P6242 【模板】线段树 3 - 洛谷专栏

数据结构闲谈：范围分治的「双半群」模型 - Meatherm - 博客园

≡