势能线段树【2021东北四省D（HDU7116）Lowbit】【2021杭电多校8/HDU7059 Counting Stars】

发表于 更新于 分类于

势能线段树

  简言之，有的区间修改不支持lazy标记（如区间开根号、取模、加减lowbit），但是这些修改存在一些奇妙的性质，即每个元素的修改次数有一个上限。我们在每个节点上记录一个值，表示区间内元素是否达到修改上限。在修改时，若没有达到上限，则暴力递归到叶子节点。反之，使用lazy标记或者直接return。

  具体来说，势能线段树是指在懒标记无法正常使用的情况下（如区间开根号），暴力到叶子将线段树当成数组一样用进行修改。这个时候的复杂度计算就不是很直观了，所以引入势能的概念。每一个节点都有一个关于开根号操作的“势能”，然后开根号的时候势能一定是递减的。注意引入势能分析是忽略过程，只考虑所有过程的总和。即我们不管在一次暴力中到底一个树节点被访问了几次（单次操作的时间复杂度可能很大，可能是O(n)）但是这些暴力的总量是势能上限。

一.2021东北四省D（HDU7116）Lowbit

题意：
  两种操作，一是对某个区间上的数每个数和加上他的lowbit，二是查询区间和
分析：
  首先，很容易想到这题估计得用树状数组，线段树之类的数据结构解决，但问题是修改有点麻烦，对一个区间上加的数不统一，难以快速维护。解决问题需要对lowbit比较熟悉，很容易发现，在加lowbit的情况下，所有数在加了一定次之后都会变成10000….000（2）这样的数，那之后在加lowbit实际是对它乘2了。所以，这道题，如果一个区间上的数都是100000（2）形式的就乘2，并且lazy标记即可，否则暴力维护。
  实际上写起来蛮麻烦的，有些地方对线段树理解不深，一直写不对一开始
AC代码：

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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll mod = 998244353;
const int N = (int)1e5 + 5;
int n, q, t;
int op, l, r;
struct node
{
    int l, r;
    ll sum;
    int lazy;
    bool flag;
}tree[N << 2];
ll ar[N];

ll pow_mod(ll a, ll n)
{
    ll ans = 1;
    a %= mod;
    while(n)
    {
        if(n & 1)
        {
            ans = (ans * a) % mod;
        }
        a = (a * a) % mod;
        n >>= 1;
    }
    return ans;
}

ll lowbit(ll x)
{
    return (-x) & x;
}

void pushup(int p)
{
    tree[p].sum = (tree[p << 1].sum + tree[p << 1 | 1].sum) % mod;
    tree[p].flag = (tree[p << 1].flag & tree[p << 1 | 1].flag);
}

void pushdown(int p)
{
    tree[p << 1].lazy += tree[p].lazy;
    tree[p << 1 | 1].lazy += tree[p].lazy;
    tree[p << 1].sum = (tree[p << 1].sum * pow_mod(2, tree[p].lazy)) % mod;
    tree[p << 1 | 1].sum = (tree[p << 1 | 1].sum * pow_mod(2, tree[p].lazy)) % mod;
    tree[p].lazy = 0;
}

void build(int p, int l, int r)
{
    tree[p].l = l, tree[p].r = r;
    tree[p].lazy = 0, tree[p].flag = false;

    if(l == r)
    {
        tree[p].sum = ar[l];
        if(lowbit(tree[p].sum) == tree[p].sum) tree[p].flag = true;
        return ;//****
    }

    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    pushup(p);
}

void update(int p, int l, int r)
{
    if(l <= tree[p].l && tree[p].r <= r && tree[p].flag)
    {
        tree[p].sum = (tree[p].sum * 2) % mod;
        ++tree[p].lazy;
        return ;//****
    }
    if(tree[p].l == tree[p].r)
    {
        tree[p].sum += lowbit(tree[p].sum);
        if(lowbit(tree[p].sum) == tree[p].sum) tree[p].flag = true;
        return ;//****
    }

    if(tree[p].lazy) pushdown(p);
    int mid = (tree[p].l + tree[p].r) >> 1;
    if(l <= mid) update(p << 1, l, r);
    if(mid < r) update(p << 1 | 1, l, r);
    pushup(p);
}

ll query(int p, int l, int r)
{
    if(l <= tree[p].l && tree[p].r <= r) return tree[p].sum;

    ll res = 0;
    if(tree[p].lazy) pushdown(p);
    int mid = (tree[p].l + tree[p].r) >> 1;
    if(l <= mid) res = (res + query(p << 1, l, r)) % mod;
    if(mid < r) res = (res + query(p << 1 | 1, l, r)) % mod;
    return res;
}

int main()
{
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i) scanf("%d", &ar[i]);
        build(1, 1, n);
        scanf("%d", &q);
        while(q--)
        {
            scanf("%d%d%d", &op, &l, &r);
            if(op == 1) update(1, l, r);
            else printf("%lld\n", query(1, l, r));
        }
    }
    return 0;
}

  1.对于节点p，如果其父节点lazy标记为0，但是p节点lazy标记不是0，那tree[p].sum的值仍然是区间（tree[p].l, tree[p].r）的和，p节点的lazy是它的子节点的待办。
  2.一些奇怪地方需要return.
  （1）建树时，建到叶子节点需要return，因为不需要继续往下build了，叶子节点也没办法pushup（pushup（p）是将p的儿子信息更新给父亲，叶子节点无父亲）
  （2）修改时，对这个区间进行了整体的修改后也不需要继续向下，需要return
  （3）查询时，查到一整个区间，直接return， 没有的话分别查两个儿子的结束后，也要return（感觉相当于pushup）

二.2021杭电多校8/HDU7059 Counting Stars

题意：
  三种操作，区间减lowbit，区间每个数加上2^k（满足 2^k ≤ai <2^(k+1）),区间和查询
分析：
  同上一个题，减lowbit会让他变成0，加的那个数相当于把一个数化成2进制,取它的最高位，其他位都置0，那么对于每一个数，我们这样存储它：
  例如，数字1001010011100，我们用两部分存，第一部分叫high，存1000000000000，另一部分叫low，存1010011100
除此之外还需要bool变量标记区间是否全置0，以及lazy标记。
  之后就是线段树常规的操作
AC代码：

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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const ll mod = 998244353;
#define ls(x) (x) << 1
#define rs(x) (x) << 1 | 1

int t, n, q;
int op, l, r;
struct node
{
    int l, r;
    ll mul;//lazy标记
    ll high, low;
    bool flag;
    int mid()
    {
        return (l + r) >> 1;
    }
}tree[maxn << 2];
ll ar[maxn], br[maxn];
ll tmp;

ll lowbit(ll x)
{
    return x & (-x);
}

ll findmx(ll x)
{
    ll res = 1;
    while(res <= x) res <<= 1;
    return res >> 1;
}

void pushup(int p)
{
    tree[p].high = (tree[ls(p)].high + tree[rs(p)].high) % mod;
    tree[p].low = (tree[ls(p)].low + tree[rs(p)].low) % mod;
    tree[p].flag = tree[ls(p)].flag & tree[rs(p)].flag;
}

void build(int p, int l, int r)
{
    tree[p].l = l, tree[p].r = r;
    tree[p].mul = 1;

    if(l == r)
    {
        tree[p].high = ar[l];
        tree[p].low = br[l];
        tree[p].flag = false;
        return ;
    }

    int mid = tree[p].mid();
    build(ls(p), l, mid);
    build(rs(p), mid + 1, r);
    pushup(p);
}

void pushdown(int p)
{
    if(tree[p].mul != 1)
    {
        tree[ls(p)].high = (tree[ls(p)].high * tree[p].mul) % mod;
        tree[rs(p)].high = (tree[rs(p)].high * tree[p].mul) % mod;
        tree[ls(p)].mul = (tree[ls(p)].mul * tree[p].mul) % mod;
        tree[rs(p)].mul = (tree[rs(p)].mul * tree[p].mul) % mod;
        tree[p].mul = 1;
    }
}

void update1(int p, int l, int r)
{
    if(tree[p].flag) return ;
    if(tree[p].l == tree[p].r)
    {
        if(tree[p].low) tree[p].low -= lowbit(tree[p].low);
        else
        {
            tree[p].high = 0;
            tree[p].flag = true;
        }
        return ;
    }

    pushdown(p);
    int mid = tree[p].mid();
    if(l <= mid) update1(ls(p), l, r);
    if(r > mid) update1(rs(p), l, r);
    pushup(p);
}

void update2(int p, int l, int r)
{
    if(tree[p].flag) return ;
    if(l <= tree[p].l && tree[p].r <= r)
    {
        tree[p].high = (tree[p].high * 2) % mod;
        tree[p].mul = (tree[p].mul * 2) % mod;
        return ;
    }

    pushdown(p);
    int mid = tree[p].mid();
    if(l <= mid) update2(ls(p), l, r);
    if(r > mid) update2(rs(p), l, r);
    pushup(p);
}

ll query(int p, int l, int r)
{
    if(l <= tree[p].l && tree[p].r <= r)
    {
        return (tree[p].high + tree[p].low) % mod;
    }

    pushdown(p);
    int mid = tree[p].mid();
    ll res = 0;
    if(l <= mid) res = (res + query(ls(p), l, r)) % mod;
    if(r > mid) res = (res + query(rs(p), l, r)) % mod;
    return res;
}

int main()
{
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i)
        {
            scanf("%lld", &ar[i]);
            ll tmp = findmx(ar[i]);
            br[i] = ar[i] - tmp;
            ar[i] = tmp;
        }
        build(1, 1, n);
        scanf("%d", &q);
        while(q--)
        {
            scanf("%d%d%d", &op, &l, &r);
            if(l > r) swap(l, r);
            if(op == 1) printf("%lld\n", query(1, l, r));
            else if(op == 2) update1(1, l, r);
            else update2(1, l, r);
        }
    }
    return 0;
}

  对于像这种数值快速递降至稳定的函数（再例如区间开根号，区间求欧拉函数之类的），我们可以考虑进行暴力修改。之后再进行区间整体修改