吉司机线段树学习笔记

First Post:

Last Update:

Word Count:
4.5k

Read Time:
26 min

本文只讲解区间最值操作，区间历史信息维护见矩阵与线段树标记。

我理解的区间最值，就是把最值通过分讨转化为了只对一种数操作的区间推平。

以区间取 为例，我们维护最大值和严格次大值，设为 和 。

假设要对 取 。

在操作时：

  • 若当前区间的 ，则直接返回。
  • 若当前区间 ，则在这个区间修改。
  • 若当前区间的 ，则向下递归。

也就是说，我们在递归到一个区间时，若修改只会对最大值产生影响，我们就在这里修改并打标记；否则向下递归。

通过势能分析，复杂度 。

例题：最佳女选手

模板题。

因为涉及到区间求和，所以我们还需要维护最大值个数，这样在修改时才能知道对区间和的影响是多少。

这里有一些问题：加法标记和最值标记的复合。

因为经过分讨，最值标记已经转化为推平标记了，所以推平怎么做这里就怎么做。

注意区间里只有一种数或两种数的情况。

通过势能分析，复杂度 。

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
#include"bits/stdc++.h"
#define re register
#define int long long
#define ls(p) tr[p].ls
#define rs(p) tr[p].rs
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
using namespace std;
const int maxn=5e5+10,inf=1e18;
int n,m,rt,segcnt;
struct node{
    int sum;
    int mx,MX,cntmx;
    int mn,MN,cntmn;
    inline node operator + (const node &a)const{
        node res;
        res.sum=sum+a.sum;
        if(mx<a.mx) res.mx=a.mx,res.cntmx=a.cntmx,res.MX=max(mx,a.MX);
        if(mx>a.mx) res.mx=mx,res.cntmx=cntmx,res.MX=max(a.mx,MX);
        if(mx==a.mx) res.mx=mx,res.cntmx=cntmx+a.cntmx,res.MX=max(MX,a.MX);
        if(mn<a.mn) res.mn=mn,res.cntmn=cntmn,res.MN=min(a.mn,MN);
        if(mn>a.mn) res.mn=a.mn,res.cntmn=a.cntmn,res.MN=min(mn,a.MN);
        if(mn==a.mn) res.mn=mn,res.cntmn=cntmn+a.cntmn,res.MN=min(MN,a.MN);
        return res;
    }
};
struct tree{
    int ls,rs;
    node s;
    int tag,tagmx,tagmn;
}tr[maxn<<1];
inline void up(int p){tr[p].s=tr[ls(p)].s+tr[rs(p)].s;}
inline void add(int l,int r,int val,int p){
    tr[p].s.sum+=val*(r-l+1);
    tr[p].s.mx+=val,tr[p].s.mn+=val;
    if(tr[p].s.MX!=-inf) tr[p].s.MX+=val;
    if(tr[p].s.MN!=inf) tr[p].s.MN+=val;
    tr[p].tag+=val;
    if(tr[p].tagmx!=-inf) tr[p].tagmx+=val;
    if(tr[p].tagmn!=inf) tr[p].tagmn+=val;
}
inline void add_mx(int p,int val){
    if(tr[p].s.mn>=val) return;
    tr[p].s.sum+=(val-tr[p].s.mn)*tr[p].s.cntmn;
    if(tr[p].s.mx==tr[p].s.mn) tr[p].s.mx=val;
    else if(tr[p].s.MX==tr[p].s.mn) tr[p].s.MX=val;
    tr[p].s.mn=val;
    tr[p].tagmx=max(tr[p].tagmx,val),tr[p].tagmn=max(tr[p].tagmn,val);
}
inline void add_mn(int p,int val){
    if(tr[p].s.mx<=val) return;
    tr[p].s.sum+=(val-tr[p].s.mx)*tr[p].s.cntmx;
    if(tr[p].s.mn==tr[p].s.mx) tr[p].s.mn=val;
    else if(tr[p].s.MN==tr[p].s.mx) tr[p].s.MN=val;
    tr[p].s.mx=val;
    tr[p].tagmx=min(tr[p].tagmx,val),tr[p].tagmn=min(tr[p].tagmn,val);
}
inline void down(int l,int r,int mid,int p){
    if(tr[p].tag) add(l,mid,tr[p].tag,ls(p)),add(mid+1,r,tr[p].tag,rs(p)),tr[p].tag=0;
    if(tr[p].tagmx!=-inf) add_mx(ls(p),tr[p].tagmx),add_mx(rs(p),tr[p].tagmx),tr[p].tagmx=-inf;
    if(tr[p].tagmn!=inf) add_mn(ls(p),tr[p].tagmn),add_mn(rs(p),tr[p].tagmn),tr[p].tagmn=inf;
}
inline void build(int l,int r,int &p){
    p=++segcnt;tr[p].tagmx=tr[p].s.MX=-inf,tr[p].tagmn=tr[p].s.MN=inf;
    if(l==r){
        cin>>tr[p].s.sum;
        tr[p].s.mx=tr[p].s.sum,tr[p].s.cntmx=1;
        tr[p].s.mn=tr[p].s.sum,tr[p].s.cntmn=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,int val,int p){
    if(l>=L&&r<=R){add(l,r,val,p);return;}
    int mid=(l+r)>>1;down(l,r,mid,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 void modify_mx(int l,int r,int L,int R,int val,int p){
    if(tr[p].s.mn>=val) return;
    if(l>=L&&r<=R&&tr[p].s.MN>=val){add_mx(p,val);return;}
    int mid=(l+r)>>1;down(l,r,mid,p);
    if(L<=mid) modify_mx(l,mid,L,R,val,ls(p));
    if(R>mid) modify_mx(mid+1,r,L,R,val,rs(p));
    up(p);
}
inline void modify_mn(int l,int r,int L,int R,int val,int p){
    if(tr[p].s.mx<=val) return;
    if(l>=L&&r<=R&&tr[p].s.MX<=val){add_mn(p,val);return;}
    int mid=(l+r)>>1;down(l,r,mid,p);
    if(L<=mid) modify_mn(l,mid,L,R,val,ls(p));
    if(R>mid) modify_mn(mid+1,r,L,R,val,rs(p));
    up(p);
}
inline node 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(l,r,mid,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;build(1,n,rt);
    cin>>m;
    for(re int i=1,op,l,r,x;i<=m;++i){
        cin>>op>>l>>r;
        if(op==1) cin>>x,update(1,n,l,r,x,rt);
        if(op==2) cin>>x,modify_mx(1,n,l,r,x,rt);
        if(op==3) cin>>x,modify_mn(1,n,l,r,x,rt);
        if(op==4) cout<<query(1,n,l,r,rt).sum<<'\n';
        if(op==5) cout<<query(1,n,l,r,rt).mx<<'\n';
        if(op==6) cout<<query(1,n,l,r,rt).mn<<'\n';
    }
    return 0;	
}

那么，区间最值操作能不能也用矩阵刻画呢？

答案是：可以的。

因为在经过分讨后，区间最值被转化为了对最值的推平，推平又可以转化为加减。

所以打标记时，我们只需要对最值和非最值分别打标记即可。

例题1：线段树经典题

注意：pushdown 的时候，只能给有最大值的儿子下放最大值的标记，否则要下放非最大值的标记！！！

因为这个错误调了一天。

有点卡空间。

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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
#include"bits/stdc++.h"
#define re register
// #define int long long
#define LL long long
#define ls(p) tr[p].ls
#define rs(p) tr[p].rs
#define max(a,b) (a>b?a:b)
using namespace std;
const int maxn=2e5+10,maxm=3;
const LL inf=1e18;
int n,m,rt,segcnt;
struct matrix1{
    int n,m;
    LL 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 matrix1 operator + (const matrix1 &B)const{
        matrix1 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 matrix1 operator * (const matrix1 &B)const{
        matrix1 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 != (matrix1 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;
    }
}I1,upd;
struct matrix2{
    int n,m;
    LL 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 matrix2 operator + (const matrix2 &B)const{
        matrix2 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 matrix2 operator * (const matrix2 &B)const{
        matrix2 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 != (matrix2 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;
    }
}I2;
struct Data{
    matrix1 s1,s2;
    matrix2 mx1,mx2;
    inline void init(){
        s1.init(3,1),s2.init(3,1);
        mx1.init(2,1),mx2.init(2,1);
    } 
    inline Data operator + (const Data &A)const{
        Data res;
        if(mx1.a[0][0]>A.mx1.a[0][0]){
            res.mx1=mx1;
            res.s1=s1;
            res.mx2=mx2+A.mx1+A.mx2;
            res.s2=s2+A.s1+A.s2;
        }
        if(mx1.a[0][0]<A.mx1.a[0][0]){
            res.mx1=A.mx1;
            res.s1=A.s1;
            res.mx2=A.mx2+mx1+mx2;
            res.s2=A.s2+s1+s2;
        }
        if(mx1.a[0][0]==A.mx1.a[0][0]){
            res.mx1=A.mx1+mx1;
            res.s1=A.s1+s1;
            res.mx2=A.mx2+mx2;
            res.s2=A.s2+s2;
        }
        return res;
    }
};
struct tree{
    int ls,rs;
    Data s;
    matrix1 tag1,tag2;
    matrix2 mxtag1,mxtag2;
}tr[maxn<<1];
inline void init(int p){
    tr[p].s.init();
    tr[p].tag1=tr[p].tag2=I1;
    tr[p].mxtag1=tr[p].mxtag2=I2;
} 
inline void up(int p){tr[p].s=tr[ls(p)].s+tr[rs(p)].s;}
inline void add1(int p,matrix1 val1,matrix2 val2){
    tr[p].s.s1=val1*tr[p].s.s1,tr[p].tag1=val1*tr[p].tag1;
    tr[p].s.mx1=val2*tr[p].s.mx1,tr[p].mxtag1=val2*tr[p].mxtag1;
}
inline void add2(int p,matrix1 val1,matrix2 val2){
    tr[p].s.s2=val1*tr[p].s.s2,tr[p].tag2=val1*tr[p].tag2;
    tr[p].s.mx2=val2*tr[p].s.mx2,tr[p].mxtag2=val2*tr[p].mxtag2;
}
inline void down(int p){
    LL mxval=max(tr[ls(p)].s.mx1.a[0][0],tr[rs(p)].s.mx1.a[0][0]);
    if(tr[ls(p)].s.mx1.a[0][0]==mxval) add1(ls(p),tr[p].tag1,tr[p].mxtag1);
    else  add1(ls(p),tr[p].tag2,tr[p].mxtag2);
    if(tr[rs(p)].s.mx1.a[0][0]==mxval) add1(rs(p),tr[p].tag1,tr[p].mxtag1);
    else  add1(rs(p),tr[p].tag2,tr[p].mxtag2);
    add2(ls(p),tr[p].tag2,tr[p].mxtag2),add2(rs(p),tr[p].tag2,tr[p].mxtag2);
    tr[p].tag1=tr[p].tag2=I1;tr[p].mxtag1=tr[p].mxtag2=I2;
}
inline void build(int l,int r,int &p){
    p=++segcnt;init(p);
    if(l==r){
        int x;cin>>x;
        tr[p].s.mx1.a[0][0]=tr[p].s.mx1.a[1][0]=x;
        tr[p].s.s1.a[0][0]=x,tr[p].s.s1.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,LL val,int p){
    if(tr[p].s.mx1.a[0][0]<=val) return;
    if(l>=L&&r<=R&&tr[p].s.mx2.a[0][0]<=val){
        matrix1 val1;val1.init(3,3),val1.build();
        val1.a[0][2]=val-tr[p].s.mx1.a[0][0];
        matrix2 val2;val2.init(2,2),val2.build();
        val2.a[0][0]=val2.a[1][0]=val-tr[p].s.mx1.a[0][0];
        val2.a[1][1]=0;
        add1(p,val1,val2);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 void modify(int l,int r,int L,int R,LL val,int p){
    if(l>=L&&r<=R){
        matrix1 val1;val1.init(3,3),val1.build();
        val1.a[0][2]=val;
        matrix2 val2;val2.init(2,2),val2.build();
        val2.a[0][0]=val2.a[1][0]=val;
        val2.a[1][1]=0;
        add1(p,val1,val2),add2(p,val1,val2);return;
    }
    int mid=(l+r)>>1;down(p);
    if(L<=mid) modify(l,mid,L,R,val,ls(p));
    if(R>mid) modify(mid+1,r,L,R,val,rs(p));
    up(p); 
}
inline matrix1 query1(int l,int r,int L,int R,int p){
    if(l>=L&&r<=R) return tr[p].s.s1+tr[p].s.s2;
    int mid=(l+r)>>1;down(p);
    if(R<=mid) return query1(l,mid,L,R,ls(p));
    if(L>mid) return query1(mid+1,r,L,R,rs(p));
    return query1(l,mid,L,R,ls(p))+query1(mid+1,r,L,R,rs(p));
}
inline matrix2 query2(int l,int r,int L,int R,int p){
    if(l>=L&&r<=R) return tr[p].s.mx1+tr[p].s.mx2;
    int mid=(l+r)>>1;down(p);
    if(R<=mid) return query2(l,mid,L,R,ls(p));
    if(L>mid) return query2(mid+1,r,L,R,rs(p));
    return query2(l,mid,L,R,ls(p))+query2(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;
    I1.init(3,3),I1.build();
    I2.init(2,2),I2.build();
    upd.init(3,3),upd.build(),upd.a[1][0]=1;
    build(1,n,rt);
    for(re int i=1,op,l,r,x;i<=m;++i){
        cin>>op>>l>>r;
        if(op==1){
            cin>>x;
            update(1,n,l,r,x,rt);
            add1(rt,upd,I2),add2(rt,upd,I2);
        }
        if(op==2){
            cin>>x;
            modify(1,n,l,r,x,rt);
            add1(rt,upd,I2),add2(rt,upd,I2);
        }
        if(op==3) cout<<query1(1,n,l,r,rt).a[0][0]<<'\n';
        if(op==4) cout<<query1(1,n,l,r,rt).a[1][0]<<'\n';
        if(op==5) cout<<query2(1,n,l,r,rt).a[1][0]<<'\n';
    }
    return 0;	
}

例题2：【模板】线段树 3

完全是上题的弱化版。

不过我写的是朴素矩阵乘法，需要把矩阵展开才能过，否则会 T 两个点。

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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include"bits/stdc++.h"
#define re register
#define int long long
#define ls(p) tr[p].ls
#define rs(p) tr[p].rs
#define max(a,b) (a>b?a:b)
using namespace std;
const int maxn=5e5+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;
    int sum,cnt;
    matrix mx,tag1;
    matrix se,tag2;
}tr[maxn<<1];
inline void init(int p){
    tr[p].mx.init(2,1),tr[p].se.init(2,1);
    tr[p].tag1=tr[p].tag2=I;
}
inline void up(int p){
    tr[p].sum=tr[ls(p)].sum+tr[rs(p)].sum;
    if(tr[ls(p)].mx.a[0][0]>tr[rs(p)].mx.a[0][0]){
        tr[p].mx=tr[ls(p)].mx;
        tr[p].se=tr[ls(p)].se+tr[rs(p)].mx+tr[rs(p)].se;
        tr[p].cnt=tr[ls(p)].cnt;
    }
    if(tr[ls(p)].mx.a[0][0]<tr[rs(p)].mx.a[0][0]){
        tr[p].mx=tr[rs(p)].mx;
        tr[p].se=tr[rs(p)].se+tr[ls(p)].mx+tr[ls(p)].se;
        tr[p].cnt=tr[rs(p)].cnt;
    }
    if(tr[ls(p)].mx.a[0][0]==tr[rs(p)].mx.a[0][0]){
        tr[p].mx=tr[ls(p)].mx+tr[rs(p)].mx;
        tr[p].se=tr[ls(p)].se+tr[rs(p)].se;
        tr[p].cnt=tr[ls(p)].cnt+tr[rs(p)].cnt;
    }
}
inline void addmx(int p,matrix val){
    tr[p].mx=val*tr[p].mx,tr[p].tag1=val*tr[p].tag1;
    tr[p].sum+=tr[p].cnt*val.a[0][0];
}
inline void addse(int p,matrix val,int siz){
    tr[p].se=val*tr[p].se,tr[p].tag2=val*tr[p].tag2;
    tr[p].sum+=(siz-tr[p].cnt)*val.a[0][0];
}
inline void down(int l,int r,int mid,int p){
    if(tr[p].tag1!=I){
        int mxval=max(tr[ls(p)].mx.a[0][0],tr[rs(p)].mx.a[0][0]);
        addmx(ls(p),tr[ls(p)].mx.a[0][0]==mxval?tr[p].tag1:tr[p].tag2);
        addmx(rs(p),tr[rs(p)].mx.a[0][0]==mxval?tr[p].tag1:tr[p].tag2);
        tr[p].tag1=I;
    }
    if(tr[p].tag2!=I){
        addse(ls(p),tr[p].tag2,mid-l+1);
        addse(rs(p),tr[p].tag2,r-mid);
        tr[p].tag2=I;
    }
}
inline void build(int l,int r,int &p){
    p=++segcnt;init(p);
    if(l==r){
        int x;cin>>x;
        tr[p].sum=tr[p].mx.a[0][0]=tr[p].mx.a[1][0]=x;
        tr[p].cnt=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,int k,int p){
    if(tr[p].mx.a[0][0]<=k) return;
    if(l>=L&&r<=R&&tr[p].se.a[0][0]<=k){
        matrix val;val.init(2,2);
        val.a[0][0]=val.a[1][0]=k-tr[p].mx.a[0][0];
        val.a[1][1]=0;
        addmx(p,val);return;
    }
    int mid=(l+r)>>1;down(l,r,mid,p);
    if(L<=mid) update(l,mid,L,R,k,ls(p));
    if(R>mid) update(mid+1,r,L,R,k,rs(p));
    up(p); 
}
inline void modify(int l,int r,int L,int R,int k,int p){
    if(l>=L&&r<=R){
        matrix val;val.init(2,2);
        val.a[0][0]=val.a[1][0]=k;
        val.a[1][1]=0;
        addmx(p,val),addse(p,val,r-l+1);return;
    }
    int mid=(l+r)>>1;down(l,r,mid,p);
    if(L<=mid) modify(l,mid,L,R,k,ls(p));
    if(R>mid) modify(mid+1,r,L,R,k,rs(p));
    up(p); 
}
inline int query1(int l,int r,int L,int R,int p){
    if(l>=L&&r<=R) return tr[p].sum;
    int mid=(l+r)>>1;down(l,r,mid,p);
    if(R<=mid) return query1(l,mid,L,R,ls(p));
    if(L>mid) return query1(mid+1,r,L,R,rs(p));
    return query1(l,mid,L,R,ls(p))+query1(mid+1,r,L,R,rs(p));
}
inline matrix query2(int l,int r,int L,int R,int p){
    if(l>=L&&r<=R) return tr[p].mx+tr[p].se;
    int mid=(l+r)>>1;down(l,r,mid,p);
    if(R<=mid) return query2(l,mid,L,R,ls(p));
    if(L>mid) return query2(mid+1,r,L,R,rs(p));
    return query2(l,mid,L,R,ls(p))+query2(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,x;i<=m;++i){
        cin>>op>>l>>r;
        if(op==1) cin>>x,modify(1,n,l,r,x,rt);
        if(op==2) cin>>x,update(1,n,l,r,x,rt);
        if(op==3) cout<<query1(1,n,l,r,rt)<<'\n';
        if(op==4) cout<<query2(1,n,l,r,rt).a[0][0]<<'\n';
        if(op==5) cout<<query2(1,n,l,r,rt).a[1][0]<<'\n';
    }
    return 0;	
}