线段树模板 | vegeone

vegeone
0%

线段树模板

发表于 更新于 分类于 Valine：

以下是我的线段树模板

参考了dls的线段树模板，封装+减少了许多的码量

单点修改

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
/*http://oj.daimayuan.top/course/15/problem/658*/
#include<bits/stdc++.h>
#define int long long
#define endl '\n' 
using namespace std;
int n,q;
const int N=2e5+10;
int a[N];
struct info{
	int ans,s,ps,bs;
}; 
struct Node{
	info val;
}node[N*4];
info operator +(const info &a,const info &b){
	info res;
	res.ans=max({a.ans,b.ans,a.bs+b.ps});
	res.ps=max(a.ps,a.s+b.ps);
	res.bs=max(b.bs,a.bs+b.s);
	res.s=a.s+b.s;
	return res;
}
void update(int id){
	node[id].val=node[id*2].val+node[id*2+1].val;
}
void build(int id,int l,int r){
	if(l==r){
		node[id]={a[l],a[l],a[l],a[l]};
	}else {
		int mid=(l+r)>>1;
		build(id*2,l,mid);
		build(id*2+1,mid+1,r);
		update(id);
	}
}
void change(int id,int l,int r,int pos,int d){
	if(l==r){
		node[id].val={d,d,d,d};
	}else {
		int mid=(l+r)>>1;
		if(pos<=mid)change(id*2,l,mid,pos,d);
		else change(id*2+1,mid+1,r,pos,d);
		update(id);
	}
}
info query(int id,int l,int r,int ql,int qr){
	if(l==ql&&r==qr){
		return node[id].val;
	}
	int mid=(l+r)>>1;
	if(qr<=mid)return query(id*2,l,mid,ql,qr);
	else if(ql>mid)return query(id*2+1,mid+1,r,ql,qr);
	else return query(id*2,l,mid,ql,mid)+query(id*2+1,mid+1,r,mid+1,qr);
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>q;
	for(int i=1;i<=n;++i)cin>>a[i];
	build(1,1,n);
	while(q--){
		int opt;
		cin>>opt;
		if(opt==1){
			int x,d;
			cin>>x>>d;
			change(1,1,n,x,d);
		}else {
			int l,r;
			cin>>l>>r;
			auto res=query(1,1,n,l,r);
			cout<<res.ans<<endl;
		}
	}
	
	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
/*http://oj.daimayuan.top/course/15/problem/660*/
#include<bits/stdc++.h>
#define int long long
#define endl '\n' 
using namespace std;
int n,q;
const int N=2e5+10,mod=1e9+7;
int a[N];
struct info{
	int sum;
};
struct tag{
	int mul,add;
};
struct Node{
	info val;
    int sz;
	tag t;
}node[N*4];
info operator+(const info &a,const info &b){
	return {(a.sum+b.sum)%mod};
}
tag operator+(const tag &a,const tag &b){
	return {a.mul*b.mul%mod,(a.add*b.mul+b.add)%mod};	
}
void settag(int id,tag t){
	node[id].t=node[id].t+t;
	node[id].val.sum=(node[id].val.sum*t.mul+node[id].sz*t.add)%mod;
}
void update(int id){
	node[id].val=node[id*2].val+node[id*2+1].val;
}
void pushdown(int id){
	if(node[id].t.mul!=1||node[id].t.add!=0){
		settag(id*2,node[id].t);
		settag(id*2+1,node[id].t);
		node[id].t={1,0};
	}
}
void build(int id,int l,int r){
	node[id].sz=r-l+1;
	node[id].t={1,0};
	if(l==r)node[id].val.sum=a[l];
	else {
		int mid=(l+r)>>1;
		build(id*2,l,mid);
		build(id*2+1,mid+1,r);
		update(id);
	}
}
void modify(int id,int l,int r,int ql,int qr,tag t){
	if(l==ql&&r==qr){
		settag(id,t);
		return;
	}
	pushdown(id);
	int mid=(l+r)>>1;
	if(qr<=mid)modify(id*2,l,mid,ql,qr,t);
	else if(ql>mid)modify(id*2+1,mid+1,r,ql,qr,t);
	else {
		modify(id*2,l,mid,ql,mid,t);
		modify(id*2+1,mid+1,r,mid+1,qr,t);
	}
	update(id);
}
info query(int id,int l,int r,int ql,int qr){
	if(ql==l&&qr==r){
		return node[id].val;
	}
	pushdown(id);
	int mid=(l+r)>>1;
	if(qr<=mid)return query(id*2,l,mid,ql,qr);
	else if(ql>mid)return query(id*2+1,mid+1,r,ql,qr);
	else {
		return query(id*2,l,mid,ql,mid)+query(id*2+1,mid+1,r,mid+1,qr);
	}
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>q;
	for(int i=1;i<=n;++i){
		cin>>a[i];
	}
	build(1,1,n);
	while(q--){
		int opt;
		cin>>opt;
		if(opt==1){
			int l,r,d;
			cin>>l>>r>>d;
			modify(1,1,n,l,r,tag{1,d});
		}else if(opt==2){
			int l,r,d;
			cin>>l>>r>>d;
			modify(1,1,n,l,r,tag{d,0}); 
		}else if(opt==3){
			int l,r,d;
			cin>>l>>r>>d;
			modify(1,1,n,l,r,tag{0,d});
		}else {
			int l,r;
			cin>>l>>r;
			auto res=query(1,1,n,l,r);
			cout<<res.sum<<endl;
		}
	}
	
	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
/*https://codeforces.com/problemset/problem/213/E*/
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef unsigned long long int64;
const int N=2e5+10,D=200003;
typedef pair<int,int>pp;
int a[N],b[N],pos[N];
int64 d[N];
struct info{
	int res;
    int64 num;
}; 
struct Node{
	info val;
}node[N*4];
info operator +(const info &a,const info &b){
	info temp;
    temp.res=a.res+b.res;
    temp.num=a.num*d[b.res]+b.num;
    return temp;
}
void update(int id){
	node[id].val=node[id*2].val+node[id*2+1].val;
}
void change(int id,int l,int r,int pos,int dd){
	if(l==r){
		node[id].val={dd?node[id].val.res+1:node[id].val.res-1,(int64)dd};
	}else {
		int mid=(l+r)>>1;
		if(pos<=mid)change(id*2,l,mid,pos,dd);
		else change(id*2+1,mid+1,r,pos,dd);
		update(id);
	}
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    int64 sum=0,aa=0;
    d[0]=1;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        sum=sum*D+a[i];
        d[i]=d[i-1]*D;
        aa+=d[i-1];
    }
    for(int i=1;i<=m;++i){
        cin>>b[i];
        pos[b[i]]=i;
    }
    int cnt=0;
    for(int i=1;i<=m;++i){
        if(i>n)change(1,1,m,pos[i-n],0);
        change(1,1,m,pos[i],i);
        if(i>=n&&node[1].val.num==(i-n)*aa+sum)
            ++cnt;
    }
    cout<<cnt<<endl;
    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
/*https://codeforces.com/problemset/problem/213/E*/
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef unsigned long long int64;
const int N=2e5+10,D=200003;
typedef pair<int,int>pp;
int a[N],b[N],pos[N];
int64 d[N];
struct info{
	int res;
    int64 num;
}; 
struct Node{
	info val;
}node[N*4];
info operator +(const info &a,const info &b){
	info temp;
    temp.res=a.res+b.res;
    temp.num=a.num*d[b.res]+b.num;
    return temp;
}
void update(int id){
	node[id].val=node[id*2].val+node[id*2+1].val;
}
void change(int id,int l,int r,int pos,int dd){
	if(l==r){
		node[id].val={dd?node[id].val.res+1:node[id].val.res-1,(int64)dd};
	}else {
		int mid=(l+r)>>1;
		if(pos<=mid)change(id*2,l,mid,pos,dd);
		else change(id*2+1,mid+1,r,pos,dd);
		update(id);
	}
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    int64 sum=0,aa=0;
    d[0]=1;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        sum=sum*D+a[i];
        d[i]=d[i-1]*D;
        aa+=d[i-1];
    }
    for(int i=1;i<=m;++i){
        cin>>b[i];
        pos[b[i]]=i;
    }
    int cnt=0;
    for(int i=1;i<=m;++i){
        if(i>n)change(1,1,m,pos[i-n],0);
        change(1,1,m,pos[i],i);
        if(i>=n&&node[1].val.num==(i-n)*aa+sum)
            ++cnt;
    }
    cout<<cnt<<endl;
    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
/*https://codeforces.com/problemset/problem/213/E*/
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef unsigned long long int64;
const int N=2e5+10,D=200003;
typedef pair<int,int>pp;
int a[N],b[N],pos[N];
int64 d[N];
struct info{
	int res;
    int64 num;
}; 
struct Node{
	info val;
}node[N*4];
info operator +(const info &a,const info &b){
	info temp;
    temp.res=a.res+b.res;
    temp.num=a.num*d[b.res]+b.num;
    return temp;
}
void update(int id){
	node[id].val=node[id*2].val+node[id*2+1].val;
}
void change(int id,int l,int r,int pos,int dd){
	if(l==r){
		node[id].val={dd?node[id].val.res+1:node[id].val.res-1,(int64)dd};
	}else {
		int mid=(l+r)>>1;
		if(pos<=mid)change(id*2,l,mid,pos,dd);
		else change(id*2+1,mid+1,r,pos,dd);
		update(id);
	}
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    int64 sum=0,aa=0;
    d[0]=1;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        sum=sum*D+a[i];
        d[i]=d[i-1]*D;
        aa+=d[i-1];
    }
    for(int i=1;i<=m;++i){
        cin>>b[i];
        pos[b[i]]=i;
    }
    int cnt=0;
    for(int i=1;i<=m;++i){
        if(i>n)change(1,1,m,pos[i-n],0);
        change(1,1,m,pos[i],i);
        if(i>=n&&node[1].val.num==(i-n)*aa+sum)
            ++cnt;
    }
    cout<<cnt<<endl;
    return 0;
}