分类目录归档：线段树

洛谷 P2023 [AHOI2009]维护序列

发表评论

没啥说的，和上一道题一模一样。。只是把输入改掉就可以了。。

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
#include<iostream>
using namespace std;
struct segmentTree{
    typedef long long ll;
    const static int MAX=100000;
    ll MOD;
    ll v[4*MAX],aTg[4*MAX],mTg[4*MAX];
    inline static ll lson(ll r){return r*2;}
    inline static ll rson(ll r){return r*2+1;}
    void build(ll r,ll* a,ll s,ll e){
        aTg[r]=0;mTg[r]=1;
        if(s==e){v[r]=a[s]%MOD;return;}
        ll m=(s+e)>>1;
        build(lson(r),a,s,m);
        build(rson(r),a,m+1,e);
        v[r]=(v[lson(r)]+v[rson(r)])%MOD;
    }
    void pushDown(ll r,ll s,ll e){
        if(aTg[r]==0&&mTg[r]==1)return;
        ll m=(s+e)>>1;
        v[lson(r)]=(v[lson(r)]*mTg[r]%MOD+aTg[r]*(m-s+1)%MOD)%MOD;
        v[rson(r)]=(v[rson(r)]*mTg[r]%MOD+aTg[r]*(e-m)%MOD)%MOD;
        aTg[lson(r)]=(aTg[lson(r)]*mTg[r]%MOD+aTg[r]%MOD)%MOD;
        aTg[rson(r)]=(aTg[rson(r)]*mTg[r]%MOD+aTg[r]%MOD)%MOD;
        mTg[lson(r)]=(mTg[lson(r)]*mTg[r])%MOD;
        mTg[rson(r)]=(mTg[rson(r)]*mTg[r])%MOD;
        aTg[r]=0;mTg[r]=1;
    }
    ll query(ll r,ll cs,ll ce,ll qs,ll qe){
        if(qe<cs||ce<qs)return 0;
        if(qs<=cs&&ce<=qe)return v[r]%MOD;
        pushDown(r,cs,ce);
        ll cmd=(cs+ce)>>1;
        return (query(lson(r),cs,cmd,qs,qe)+query(rson(r),cmd+1,ce,qs,qe))%MOD;
    }
    void update(ll r,ll cs,ll ce,ll us,ll ue,ll addv=0,ll mulv=1){
        if(ue<cs||ce<us)return;
        if(us<=cs&&ce<=ue){
            v[r]=(v[r]*mulv%MOD+addv*(ce-cs+1))%MOD;
            aTg[r]=(aTg[r]*mulv%MOD+addv)%MOD;
            mTg[r]=(mTg[r]*mulv)%MOD;
            return;
        }
        pushDown(r,cs,ce);
        ll cmd=(cs+ce)>>1;
        update(lson(r),cs,cmd,us,ue,addv,mulv);
        update(rson(r),cmd+1,ce,us,ue,addv,mulv);
        v[r]=(v[lson(r)]+v[rson(r)])%MOD;
    }
}ST;
typedef long long ll;
ll n,m,p;
ll a[100005];
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>p;
    for(int i=1;i<=n;i++)cin>>a[i];
    cin>>m;
    ST.MOD=p;
    ST.build(1,a,1,n);
    for(int i=1;i<=m;i++){
        ll op,x,y,k;
        cin>>op;
        if(op==1||op==2){
            cin>>x>>y>>k;
            if(op==1)ST.update(1,1,n,x,y,0,k);
            else ST.update(1,1,n,x,y,k);
        }else{
            cin>>x>>y;
            cout<<ST.query(1,1,n,x,y)%p<<endl;
        }
    }
}

洛谷 P3373 【模板】线段树 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
#include<iostream>
using namespace std;
struct segmentTree{
    typedef long long ll;
    const static int MAX=100000;
    ll MOD;
    ll v[4*MAX],aTg[4*MAX],mTg[4*MAX];
    inline static ll lson(ll r){return r*2;}
    inline static ll rson(ll r){return r*2+1;}
    void build(ll r,ll* a,ll s,ll e){
        aTg[r]=0;mTg[r]=1;
        if(s==e){v[r]=a[s]%MOD;return;}
        ll m=(s+e)>>1;
        build(lson(r),a,s,m);
        build(rson(r),a,m+1,e);
        v[r]=(v[lson(r)]+v[rson(r)])%MOD;
    }
    void pushDown(ll r,ll s,ll e){
        if(aTg[r]==0&&mTg[r]==1)return;
        ll m=(s+e)>>1;
        v[lson(r)]=(v[lson(r)]*mTg[r]%MOD+aTg[r]*(m-s+1)%MOD)%MOD;
        v[rson(r)]=(v[rson(r)]*mTg[r]%MOD+aTg[r]*(e-m)%MOD)%MOD;
        aTg[lson(r)]=(aTg[lson(r)]*mTg[r]%MOD+aTg[r]%MOD)%MOD;
        aTg[rson(r)]=(aTg[rson(r)]*mTg[r]%MOD+aTg[r]%MOD)%MOD;
        mTg[lson(r)]=(mTg[lson(r)]*mTg[r])%MOD;
        mTg[rson(r)]=(mTg[rson(r)]*mTg[r])%MOD;
        aTg[r]=0;mTg[r]=1;
    }
    ll query(ll r,ll cs,ll ce,ll qs,ll qe){
        if(qe<cs||ce<qs)return 0;
        if(qs<=cs&&ce<=qe)return v[r]%MOD;
        pushDown(r,cs,ce);
        ll cmd=(cs+ce)>>1;
        return (query(lson(r),cs,cmd,qs,qe)+query(rson(r),cmd+1,ce,qs,qe))%MOD;
    }
    void update(ll r,ll cs,ll ce,ll us,ll ue,ll addv=0,ll mulv=1){
        if(ue<cs||ce<us)return;
        if(us<=cs&&ce<=ue){
            v[r]=(v[r]*mulv%MOD+addv*(ce-cs+1))%MOD;
            aTg[r]=(aTg[r]*mulv%MOD+addv)%MOD;
            mTg[r]=(mTg[r]*mulv)%MOD;
            return;
        }
        pushDown(r,cs,ce);
        ll cmd=(cs+ce)>>1;
        update(lson(r),cs,cmd,us,ue,addv,mulv);
        update(rson(r),cmd+1,ce,us,ue,addv,mulv);
        v[r]=(v[lson(r)]+v[rson(r)])%MOD;
    }
}ST;
typedef long long ll;
ll n,m,p;
ll a[100005];
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m>>p;
    for(int i=1;i<=n;i++)cin>>a[i];
    ST.MOD=p;
    ST.build(1,a,1,n);
    for(int i=1;i<=m;i++){
        ll op,x,y,k;
        cin>>op;
        if(op==1||op==2){
            cin>>x>>y>>k;
            if(op==1)ST.update(1,1,n,x,y,0,k);
            else ST.update(1,1,n,x,y,k);
        }else{
            cin>>x>>y;
            cout<<ST.query(1,1,n,x,y)%p<<endl;
        }
    }
}

洛谷 【模板】线段树 1

发表评论

题号：P3372

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cassert>
#include<vector>
#include<list>
#include<stack>
#include<queue>
struct node{
    long long value;
    long long lazymark;
}segment_tree[400005];
void build(int root, long long * arr, int start, int end){
    segment_tree[root].lazymark = 0;
    if (start == end){
        segment_tree[root].value = arr[start];
        return;
    }
    int mid = (start + end) / 2;
    build(root * 2 + 1, arr, start, mid);
    build(root * 2 + 2, arr, mid + 1, end);
    segment_tree[root].value = segment_tree[root * 2 + 1].value + segment_tree[root * 2 + 2].value;
}
void pushdown(int root,int start,int end){
    if (segment_tree[root].lazymark == 0)return;
    int mid = (start + end) / 2;
    segment_tree[root * 2 + 1].lazymark += segment_tree[root].lazymark;
    segment_tree[root * 2 + 2].lazymark += segment_tree[root].lazymark;
    segment_tree[root * 2 + 1].value += segment_tree[root].lazymark*(mid - start + 1);
    segment_tree[root * 2 + 2].value += segment_tree[root].lazymark*(end - mid);
    segment_tree[root].lazymark = 0;
}
long long query(int root, int cstart, int cend, int qstart, int qend){
    if (qstart > cend || qend < cstart)return 0;
    if (qstart <= cstart&&cend <= qend)return segment_tree[root].value;
    pushdown(root,cstart,cend);
    int cmid = (cstart + cend) / 2;
    return query(root * 2 + 1, cstart, cmid, qstart, qend) + query(root * 2 + 2, cmid + 1, cend, qstart, qend);
}
void update(int root, int cstart, int cend, int ustart, int uend, long long addvalue){
    if (cend < ustart || uend < cstart)return;
    if (ustart <= cstart&&cend <= uend){
        segment_tree[root].value += addvalue*(cend - cstart + 1);
        segment_tree[root].lazymark += addvalue;
        return;
    }
    pushdown(root,cstart,cend);
    int cmid = (cstart + cend) / 2;
    update(root * 2 + 1, cstart, cmid, ustart, uend, addvalue);
    update(root * 2 + 2, cmid + 1, cend, ustart, uend, addvalue);
    segment_tree[root].value = segment_tree[root * 2 + 1].value + segment_tree[root * 2 + 2].value;
}

using namespace std;
int n, m;
long long arr[100005];
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        cin >> arr[i];
    }
    build(1, arr, 1, n);
    while (m--){
        int op;
        cin >> op;
        if (op == 1){
            int x, y;
            long long z;
            cin >> x >> y >> z;
            update(1, 1, n, x, y, z);
        }
        else{//op==2
            int x, y;
            cin >> x >> y;
            cout << query(1, 1, n, x, y) << endl;
        }
    }
}

zcysky标程：

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
#include<bits/stdc++.h>
const int N=100005;
typedef long long ll;
using namespace std;
int a[N],n,m;
inline ll read(){
    ll f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f*x;
}
ll sumv[N<<2],addv[N<<2];
#define lson (o<<1)
#define rson (o<<1|1)
inline void pushup(int o){sumv[o]=sumv[lson]+sumv[rson];}
inline void pushdown(int o,int l,int r){
    if(!addv[o])return;
    ll tag=addv[o];addv[o]=0;int mid=(l+r)>>1;
    addv[lson]+=tag;addv[rson]+=tag;
    sumv[lson]+=tag*1LL*(mid-l+1);sumv[rson]+=tag*1LL*(r-mid);
}
inline void build(int o,int l,int r){
    if(l==r){sumv[o]=a[l];return;}
    int mid=(l+r)>>1;
    build(lson,l,mid);build(rson,mid+1,r);
    pushup(o);
}
inline void optadd(int o,int l,int r,int ql,int qr,ll v){
    if(ql<=l&&r<=qr){sumv[o]+=v*1LL*(r-l+1);addv[o]+=v;return;}
    int mid=(l+r)>>1;pushdown(o,l,r);
    if(ql<=mid)optadd(lson,l,mid,ql,qr,v);
    if(qr>mid)optadd(rson,mid+1,r,ql,qr,v);
    pushup(o);
}
inline ll querysum(int o,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr)return sumv[o];
    pushdown(o,l,r);
    int mid=(l+r)>>1;ll ans=0;
    if(ql<=mid)ans+=querysum(lson,l,mid,ql,qr);
    if(qr>mid)ans+=querysum(rson,mid+1,r,ql,qr);
    return ans;
}
int main(){
    n=read();m=read();
    for(int i=1;i<=n;i++)a[i]=read();
    build(1,1,n);
    while(m--){
        int opt=read(),l=read(),r=read();
        if(opt==1){
            ll k=read();optadd(1,1,n,l,r,k);
        }
        else printf("%lld\n",querysum(1,1,n,l,r));
    }
}

20180816更新：

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
#include<iostream>
using namespace std;

struct segmentTree{
    typedef long long ll;
    const static ll MAX=100000;
    ll v[4*MAX],m[4*MAX];
    inline static ll lson(ll r){return r*2+1;}
    inline static ll rson(ll r){return r*2+2;}
    void build(ll r,ll * a,ll s,ll e){
                m[r]=0;
                if(s==e){v[r]=a[s];return;}
                ll md=(s+e)>>1;
        build(lson(r),a,s,md);
        build(rson(r),a,md+1,e);
        v[r]=v[lson(r)]+v[rson(r)];
        }
    void pushDown(ll r,ll s,ll e){
        if(m[r]==0)return;
        ll md=(s+e)>>1;
        m[lson(r)]+=m[r];
        m[rson(r)]+=m[r];
        v[lson(r)]+=m[r]*(md-s+1);
        v[rson(r)]+=m[r]*(e-md);
        m[r]=0;
    }
    ll query(ll r,ll cs, ll ce,ll qs,ll qe){
        if(qe<cs||ce<qs)return 0;
        if(qs<=cs&&ce<=qe)return v[r];
        pushDown(r,cs,ce);
        ll cmd=(cs+ce)/2;
        return query(lson(r),cs,cmd,qs,qe)+query(rson(r),cmd+1,ce,qs,qe);
    }
    void update(ll r,ll cs,ll ce,ll us,ll ue,ll addv){
        if(ce<us||ue<cs)return;
        if(us<=cs&&ce<=ue){v[r]+=addv*(ce-cs+1);m[r]+=addv;return;}
        pushDown(r,cs,ce);
        ll cmd=(cs+ce)>>1;
        update(lson(r),cs,cmd,us,ue,addv);
        update(rson(r),cmd+1,ce,us,ue,addv);
        v[r]=v[lson(r)]+v[rson(r)];
    }
}ST;
typedef long long ll;
ll n,m;
ll a[100005];
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    ST.build(1,a,1,n);
    for(int i=1;i<=m;i++){
        int op,x,y,k;
        cin>>op;
        if(op==1){
            cin>>x>>y>>k;
            ST.update(1,1,n,x,y,k);
        }else{
            cin>>x>>y;
            cout<<ST.query(1,1,n,x,y)<<endl;
        }
    }
}