获取中...

-

Just a minute...

更新于 数据结构 线段树 热度 1 喜欢 0

线段树

拖了好久了呀，终于是把线段树写了，这个实在太好用了，经常能用

原理就先不写了，听了好多遍了，都大概懂了，一写代码还是很容易理解

就先放上来吧，当作模板看一下

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
/* ---------------------------------------------------------------------------------------------*/
struct Tree
{
    int l,r;
    ll sum,lazy;
}tree[4*MAX];
int a[MAX];
/* ---------------------------------------------------------------------------------------------*/

void bulid(int pos,int l,int r)
{
    tree[pos].l = l;
    tree[pos].r = r;
    if(l == r)
    {
        tree[pos].sum = a[l];
        return;
    }
    int mid = (l+r)>>1;
    bulid(pos<<1,l,mid);
    bulid(pos<<1|1,mid+1,r);
    tree[pos].sum = tree[pos<<1].sum + tree[pos<<1|1].sum;
}

void pushdown(int pos)
{
    if(tree[pos].lazy)
    {
        tree[pos<<1].sum += tree[pos].lazy*(tree[pos<<1].r - tree[pos<<1].l + 1);
        tree[pos<<1|1].sum += tree[pos].lazy*(tree[pos<<1|1].r - tree[pos<<1|1].l + 1);
        tree[pos<<1].lazy += tree[pos].lazy;
        tree[pos<<1|1].lazy += tree[pos].lazy;
        tree[pos].lazy = 0;

    }
}

void update(int pos,int l,int r,int x)
{
    if(l <= tree[pos].l && r >= tree[pos].r)
    {
        tree[pos].sum += (ll)x * (tree[pos].r - tree[pos].l + 1);
        tree[pos].lazy += x;
        return;
    }
    pushdown(pos);
    int mid = (tree[pos].l + tree[pos].r) >> 1;
    if(l <= mid) update(pos<<1,l,r,x);
    if(r > mid) update(pos<<1|1,l,r,x);
    tree[pos].sum = tree[pos<<1].sum + tree[pos<<1|1].sum;
}

ll query(int pos,int l,int r)
{
    if(l <= tree[pos].l && r >= tree[pos].r)
    {
        return tree[pos].sum;
    }
    pushdown(pos);
    int mid = (tree[pos].l + tree[pos].r) >> 1;
    ll ans = 0;
    if(l <= mid) ans += query(pos<<1,l,r);
    if(r > mid) ans += query(pos<<1|1,l,r);
    return ans;
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.in","r",stdin);
    //freopen("output.out","w",stdout);
/* -----------------------------------------------------------------------------------------*/
    cin >> N >> M;
    for(int i = 1;i <= N;i++)
    {
        cin >> a[i];
    }
    bulid(1,1,N);
    int x,y,z;
    while(M--)
    {
        cin >> x;
        if(x == 1)
        {
            cin >> x >> y >> z;
            update(1,x,y,z);
        }
        else
        {
            cin >> x >> y;
            cout << query(1,x,y) <<endl;
        }
    }
    return 0;
}

P3373

同样是区间修改，区间求和

但是修改方式分为加法，和乘法

lazy标记涉及到加法与乘法的优先问题

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
/*---------------------------------------------------------------------------------------------------*/
//线段树
struct Tree
{
    int l,r;
    ll sum;
    ll lazyadd,lazymul;
}tree[4*MAX];
int a[MAX];
int P;
/* --------------------------------------------------------------------------------------------------*/

void bulid(int pos,int l,int r)
{
    tree[pos].l = l;
    tree[pos].r = r;
    if(l == r)
    {
        tree[pos].sum = a[l];
        tree[pos].lazymul = 1;
        return;
    }
    int mid = (l+r)>>1;
    bulid(pos<<1,l,mid);
    bulid(pos<<1|1,mid+1,r);
    tree[pos].sum = tree[pos<<1].sum + tree[pos<<1|1].sum;
    tree[pos].lazymul = 1;
}

void pushdown(int pos)
{
    tree[pos<<1].sum = (tree[pos<<1].sum * tree[pos].lazymul) % P;
    tree[pos<<1|1].sum = (tree[pos<<1|1].sum * tree[pos].lazymul) % P;
    tree[pos<<1].sum = (tree[pos<<1].sum + tree[pos].lazyadd*(tree[pos<<1].r - tree[pos<<1].l + 1)) % P;
    tree[pos<<1|1].sum = (tree[pos<<1|1].sum + tree[pos].lazyadd*(tree[pos<<1|1].r - tree[pos<<1|1].l + 1)) % P;

    tree[pos<<1].lazyadd = (tree[pos<<1].lazyadd*tree[pos].lazymul) % P;
    tree[pos<<1|1].lazyadd = (tree[pos<<1|1].lazyadd*tree[pos].lazymul) % P;
    tree[pos<<1].lazymul = (tree[pos<<1].lazymul*tree[pos].lazymul) % P;
    tree[pos<<1|1].lazymul = (tree[pos<<1|1].lazymul*tree[pos].lazymul) % P;
    tree[pos<<1].lazyadd = (tree[pos<<1].lazyadd + tree[pos].lazyadd ) % P;
    tree[pos<<1|1].lazyadd = (tree[pos<<1|1].lazyadd + tree[pos].lazyadd ) % P;

    tree[pos].lazyadd = 0;
    tree[pos].lazymul = 1;
}

void updateadd(int pos,int l,int r,int x)
{
    if(l <= tree[pos].l && r >= tree[pos].r)
    {
        tree[pos].sum = (tree[pos].sum + (ll)x * (tree[pos].r - tree[pos].l + 1)) % P;
        tree[pos].lazyadd = (tree[pos].lazyadd + x) % P;
        return;
    }
    if(tree[pos].lazyadd || tree[pos].lazymul != 1) pushdown(pos);
    int mid = (tree[pos].l + tree[pos].r) >> 1;
    if(l <= mid) updateadd(pos<<1,l,r,x);
    if(r > mid) updateadd(pos<<1|1,l,r,x);
    tree[pos].sum = (tree[pos<<1].sum + tree[pos<<1|1].sum) % P;
}

void updatemult(int pos,int l,int r,int x)
{
    if(l <= tree[pos].l && r >= tree[pos].r)
    {
        tree[pos].sum = ((ll)x * tree[pos].sum) % P;
        tree[pos].lazymul = (tree[pos].lazymul*x) % P;
        tree[pos].lazyadd = (tree[pos].lazyadd*x) % P;
        return;
    }
    if(tree[pos].lazyadd || tree[pos].lazymul != 1) pushdown(pos);
    int mid = (tree[pos].l + tree[pos].r) >> 1;
    if(l <= mid) updatemult(pos<<1,l,r,x);
    if(r > mid) updatemult(pos<<1|1,l,r,x);
    tree[pos].sum = (tree[pos<<1].sum + tree[pos<<1|1].sum) % P;
}

ll query(int pos,int l,int r)
{
    if(l <= tree[pos].l && r >= tree[pos].r)
    {
        return tree[pos].sum;
    }
    if(tree[pos].lazyadd || tree[pos].lazymul != 1) pushdown(pos);
    int mid = (tree[pos].l + tree[pos].r) >> 1;
    ll ans = 0;
    if(l <= mid) ans += query(pos<<1,l,r);
    ans %= P;
    if(r > mid) ans += query(pos<<1|1,l,r);
    ans %= P;
    return ans;
}


int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.in","r",stdin);
    //freopen("output.out","w",stdout);
/* -----------------------------------------------------------------------------------------*/
    cin >> N >> M >> P;
    for(int i = 1;i <= N;i++)
    {
        cin >> a[i];
    }
    bulid(1,1,N);
    int x,y,z;
    while(M--)
    {
        cin >> x;
        if(x == 1)
        {
            cin >> x >> y >> z;
            updatemult(1,x,y,z);
        }
        else if(x == 2)
        {
            cin >> x >> y >> z;
            updateadd(1,x,y,z);
        }
        else if(x == 3)
        {
            cin >> x >> y;
            cout << query(1,x,y) <<endl;
        }
    }
    return 0;
}

HUD1752

单点更新

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
/*---------------------------------------------------------------------------------------------------*/
//线段树
struct Tree
{
    int l,r;
    ll sum,lazy;
    int mx;
}tree[4*MAX];
int a[MAX];
/* --------------------------------------------------------------------------------------------------*/

void bulid(int pos,int l,int r)//建树
{
    tree[pos].l = l;
    tree[pos].r = r;
    if(l == r)
    {
        tree[pos].mx = a[l];
        return;
    }
    int mid = (l+r)>>1;
    bulid(pos<<1,l,mid);
    bulid(pos<<1|1,mid+1,r);
    tree[pos].mx = max(tree[pos<<1].mx,tree[pos<<1|1].mx);
}

void update(int pos,int v,int x)
{
    if(tree[pos].l == v && tree[pos].r == v)
    {
        tree[pos].mx = max(tree[pos].mx,x);
        return;
    }
    int mid = (tree[pos].l + tree[pos].r) >> 1;
    if(v <= mid) update(pos<<1,v,x);
    if(v > mid) update(pos<<1|1,v,x);
    tree[pos].mx = max(tree[pos<<1].mx,tree[pos<<1|1].mx);
}

int query(int pos,int l,int r)
{
    if(tree[pos].l >= l && tree[pos].r <= r)
    {
        return tree[pos].mx;
    }
    int ans = 0;
    int mid = (tree[pos].l + tree[pos].r) >> 1;
    if(l <= mid) ans =max(query(pos<<1,l,r),ans);
    if(r > mid) ans =max(query(pos<<1|1,l,r),ans);
    return ans;
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.in","r",stdin);
    //freopen("output.out","w",stdout);
/* -----------------------------------------------------------------------------------------*/
    while(cin >> N >> M)
    {
        for(int i = 1;i <= N;i++)
        {
            cin >> a[i];
        }
        bulid(1,1,N);
        int x,y;
        char c;
        while(M--)
        {
            cin >> c;
            if(c == 'U')
            {
                cin >> x >> y;
                update(1,x,y);
            }
            else
            {
                cin >> x >> y;
                cout << query(1,x,y) <<endl;
            }
        }
    }

    return 0;
}
相关文章
评论
分享
返回顶部
  • 我是树-主席树

    七月 30日, 2019

    我是树-主席树
  • 我不是树-树状数组

    七月 30日, 2019

    树状数组我是一个无情的博客搬运工 1.树 or 数组？​ 名曰树状数组，那么究竟它是树还是数组呢？数组在物理空间上是连续的，而树是通过父子关系关联起来的，而树状数组正是这两种关系的结合，首先在存储空间上它是以数组的形式存储的，即...

    我不是树-树状数组
  • 专题-搜索

    九月 8日, 2020

    专题-搜索
  • vim

    十一月 3日, 2019

    vim
  • 专题-Dancing Links X

    十月 25日, 2019

    122123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616...

    专题-Dancing Links X
  • ubuntu18.04双硬盘（ssd+机械）+双系统（win10+linux）

    十月 14日, 2019

    安装最先一定要分清楚一件事情你的系统启动方式是什么 UEFI or BCD？看清楚再安装（百度怎么看） 安装参考链接： https://www.cnblogs.com/ERFishing/p/10050867.html 注意事项1....

    ubuntu18.04双硬盘（ssd+机械）+双系统（win10+linux）
  • NC-10

    九月 1日, 2019

    NC-10
  • NC-9

    九月 1日, 2019

    NC-9
  • NC-8

    九月 1日, 2019

    NC-8
  • ECF-70-2

    八月 9日, 2019

    Educational Codeforces Round 70 (Rated for Div. 2)A.You Are Given Two Binary Strings乘2^k次，其实就是把二进制左移了k位 加法就是对应位加就好了，然...

    ECF-70-2
Please check the parameter of comment in config.yml of hexo-theme-Annie!
ESC