抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

【模板】线段树

算法

发布于：2024年7月24日

线段树是一个处理区间问题常用的数据结构。但是码线段树的时候总是会有很多很多小错误导致RE……

线段树模板题：区间查询、区间修改

仅涉及线段树的代码：

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
int a[N];
struct node
{
    int l,r,v,tag;
}tr[4*N];
void build(int l,int r,int i)
{
    tr[i].l=l;
    tr[i].r=r;
    tr[i].tag=0;
    if(l==r)
    {
        tr[i].v=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,2*i);
    build(mid+1,r,2*i+1);
    tr[i].v=tr[2*i].v+tr[2*i+1].v;
}

int getsum(int l,int r,int i)
{
    if(tr[i].l==l&&tr[i].r==r)return tr[i].v;
    if(tr[i].tag)
    {
        tr[2*i].tag+=tr[i].tag;
        tr[2*i].v+=tr[i].tag*(tr[2*i].r-tr[2*i].l+1);
        tr[2*i+1].tag+=tr[i].tag;
        tr[2*i+1].v+=tr[i].tag*(tr[2*i+1].r-tr[2*i+1].l+1);
        tr[i].tag=0;
    }
    int mid=(tr[i].l+tr[i].r)>>1;
    if(mid>=r)return getsum(l,r,2*i);
    else if(mid<l)return getsum(l,r,2*i+1);
    else return getsum(l,mid,2*i)+getsum(mid+1,r,2*i+1);
}

void update(int l,int r,int x,int i)
{
    if(tr[i].l==l&&r==tr[i].r)
    {
        tr[i].tag+=x;
        tr[i].v+=x*(tr[i].r-tr[i].l+1);
        return;
    }
    if(tr[i].tag)
    {
        tr[2*i].tag+=tr[i].tag;
        tr[2*i].v+=tr[i].tag*(tr[2*i].r-tr[2*i].l+1);
        tr[2*i+1].tag+=tr[i].tag;
        tr[2*i+1].v+=tr[i].tag*(tr[2*i+1].r-tr[2*i+1].l+1);
        tr[i].tag=0;
    }
    int mid=(tr[i].l+tr[i].r)>>1;
    if(mid>=r)update(l,r,x,2*i);
    else if(mid<l)update(l,r,x,2*i+1);
    else
    {
        update(l,mid,x,2*i);
        update(mid+1,r,x,2*i+1);
    }
    tr[i].v=tr[2*i].v+tr[2*i+1].v;
}

打线段树板子常犯的问题：

  • build函数调用的时候是（1，n，1）这样的顺序。然而在函数内部递归时，不要把变量 l 打成 数字1 ！
  • update函数中，求mid是 tr[i].l+tr[i].r>>1 ，而不是l+r>>1
  • update和get函数中，mid大于等于r时调用左区间，mid小于l时调用右区间。一定要注意大小关系和开闭关系！
  • 涉及到lazy-tag的操作时，一定要想好自己的tag是否传递下去，区间的值是等tag标记传递下去时在更新还是在tag传到这个区间的同时对值进行更新。
  • update函数，一定别忘了递归完左右区间的时候，更新父节点的值。

这些问题其实真不是大问题，但是有的时候脑子抽了就容易忽略，然后调试半天高血压了……

CF139E Mushroom Gnomes - 2

题目链接： CF139E

解题思路：就是求加权期望值。首先把树（以及他倒下的左右区间的断点）和蘑菇的坐标离散化一下，方便线段树的操作。之后就是计算每个区间蘑菇存活的概率，是区间乘法。注意树木可能不会倒下。

代码：

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
#ifndef VLSMB_VS
#include <bits/stdc++.h>
#else
#include <iostream>
#include <iomanip>
#include <set>
#include <algorithm>
#include <map>
#include <vector>
#include <stack>
#endif

#define int long long
#define pii pair<int,int>
#define endl '\n'
#define veci vector<int>
#define vecpi vector<pii >
#define mpi map<int,int>
#define mpc map<char,int>
#define inf 0x7fffffffffffffff
#define eps 1e-8
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define seti set<int>
#define mulseti multiset<int>
#define setpi set<pii >
#define priqli priority_queue<int,veci,less<int> >
#define priqgi priority_queue<int,veci,greater<int> >
using namespace std;
const int N = 6e5;
void solve();
void init();

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    init();
    //cin>>t;
    while(t--)solve();
    cout.flush();
    return 0;
}

int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
struct node
{
    int l,r;
    double v;
}tr[4*N];
//int a[N];
//int leaf[N];
void build(int l,int r,int i)
{
    tr[i].l=l;
    tr[i].r=r;
    if(l==r)
    {
        tr[i].v=1.0;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,2*i);
    build(mid+1,r,2*i+1);
    tr[i].v=1.0;
}
double query(int l,int r,int i)
{
    if(tr[i].l==tr[i].r)
    {
        return tr[i].v;
    }
    if(fabs(tr[i].v-1)>eps)
    {
        tr[2*i].v*=tr[i].v;
        tr[2*i+1].v*=tr[i].v;
        tr[i].v=1.0;
    }
    int mid=(tr[i].l+tr[i].r)>>1;
    if(mid>=l)return query(l,r,2*i);
    else if(mid<r)return query(l,r,2*i+1);
    else return inf;    // 根本不会跑到这
}
void update(int l,int r,int i,double x)
{
    if(tr[i].l==l&&tr[i].r==r)
    {
        tr[i].v*=x;
        return;
    }
    if(fabs(tr[i].v-1)>eps)
    {
        tr[2*i].v*=tr[i].v;
        tr[2*i+1].v*=tr[i].v;
        tr[i].v=1.0;
    }
    int mid=(tr[i].l+tr[i].r)>>1;
    if(mid>=r)update(l,r,2*i,x);
    else if(mid<l)update(l,r,2*i+1,x);
    else
    {
        update(l,mid,2*i,x);
        update(mid+1,r,2*i+1,x);
    }
}

void solve()
{
    int n,m;
    cin>>n>>m;
    vecpi prob(n);
    vecpi trinfo(n);
    mpi h;
    veci points;
    for(int i=0;i<n;i++)
    {
        // ai, hi, li, ri
        cin>>trinfo[i].first>>trinfo[i].second>>prob[i].first>>prob[i].second;
        points.push_back(trinfo[i].first);
        points.push_back(trinfo[i].first-trinfo[i].second);
        points.push_back(trinfo[i].first+trinfo[i].second);
    }
    vecpi mush(m);
    for(int i=0;i<m;i++)
    {
        // bj, zj
        cin>>mush[i].first>>mush[i].second;
        points.push_back(mush[i].first);
    }
    sort(points.begin(),points.end());
    int idx=1;
    points.erase(unique(points.begin(),points.end()),points.end());
    for(const auto&x:points)h[x]=idx++;
    idx--;

    build(1,idx,1);
    for(int i=0;i<n;i++)
    {
        update(h[trinfo[i].first-trinfo[i].second],h[trinfo[i].first]-1,1,1.0-prob[i].first*1.0/100.0);
        update(h[trinfo[i].first]+1,h[trinfo[i].first+trinfo[i].second],1,1.0-prob[i].second*1.0/100.0);
    }
    double ans=0.0;
    for(int i=0;i<m;i++)
    {
        ans+=query(h[mush[i].first],h[mush[i].first],1)*mush[i].second;
    }
    cout<<ans<<endl;
}
void init()
{

}

CF914D Bash and a Tough Math Puzzle

题目链接：CF914D

题目思路：首先要想到，区间gcd如果是x的倍数，则这个区间随便的一个数字改为x就可以满足题意；如果不是，则需要改变一个数字，这个只能向下区间去寻找。对于单个不是x的倍数的数字，如果不修改它则区间gcd一定不为x。可以记录这样需要修改的数字，当这个区间必须修改的数字超过1个了，则直接返回递归函数。

代码：

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
#ifndef VLSMB_VS
#include <bits/stdc++.h>
#else
#include <iostream>
#include <iomanip>
#include <set>
#include <algorithm>
#include <map>
#include <vector>
#include <stack>
#endif

#define int long long
#define pii pair<int,int>
#define endl '\n'
#define veci vector<int>
#define vecpi vector<pii >
#define mpi map<int,int>
#define mpc map<char,int>
#define inf 0x7fffffffffffffff
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define seti set<int>
#define mulseti multiset<int>
#define setpi set<pii >
#define priqli priority_queue<int,veci,less<int> >
#define priqgi priority_queue<int,veci,greater<int> >
using namespace std;
const int N = 6e5;
void solve();
void init();

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    init();
    //cin>>t;
    while(t--)solve();
    cout.flush();
    return 0;
}

int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
struct node
{
    int l,r,v;
}tr[4*N];
int a[N];
void build(int l,int r,int i)
{
    tr[i].l=l;
    tr[i].r=r;
    if(l==r)
    {
        tr[i].v=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,2*i);
    build(mid+1,r,2*i+1);
    tr[i].v=gcd(tr[2*i].v,tr[2*i+1].v);
}
bool query(int l,int r,int i,int x,int&ans)
{
    if(ans>1)return false;
    if(tr[i].l==l&&tr[i].r==r)
    {
        if(tr[i].v%x==0)return true;
        if(l==r)
        {
            ans++;
            if(ans>1)return false;
            else return true;
        }
    }
    int mid=(tr[i].l+tr[i].r)>>1;
    if(mid>=r)return query(l,r,2*i,x,ans);
    else if(mid<l)return query(l,r,2*i+1,x,ans);
    else return query(l,mid,2*i,x,ans) && query(mid+1,r,2*i+1,x,ans);
}
void update(int l,int r,int i,int x)
{
    if(tr[i].l==l&&tr[i].r==r)
    {
        tr[i].v=x;
        return;
    }
    int mid=(tr[i].l+tr[i].r)>>1;
    if(mid>=r)update(l,r,2*i,x);
    else if(mid<l)update(l,r,2*i+1,x);
    else
    {
        update(l,mid,2*i,x);
        update(mid+1,r,2*i+1,x);
    }
    tr[i].v=gcd(tr[2*i].v,tr[2*i+1].v);
}

void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    int op,l,r,x,y,ans;
    build(1,n,1);
    int q;
    cin>>q;
    while(q--)
    {
        cin>>op;
        if(op==1)
        {
            cin>>l>>r>>x;
            ans=0;
            cout<<(query(l,r,1,x,ans)?"YES":"NO")<<endl;
        }
        else if(op==2)
        {
            cin>>x>>y;
            update(x,x,1,y);
        }
    }
}
void init()
{

}

更新于：2024年7月29日

算法

线段树