线段树维护前缀最值问题

(Updated: )
(10 mins to read)

楼房重建

有n栋房屋,问从1号楼往后看,最多能看到几栋楼,要求支持单点修改例:(1, 3, 2, 5, 4) 答案为3:(1, 3, 5)答案就是从1开始的严格前缀最大值的长度,考虑线段树维护,但是在pushup的时候,如果简单的将左右子树的答案相加,是不对的,因为左边的楼房高度会影响到右边.不妨考虑递归的进行pushup(也是某种启发,因为pushup一般都是O(1)合并的,但$O(\log n)$合并未尝不可?)线段树每个节点维护mx,len分别表示区间最大值(用于剪枝),只考虑该区间时的答案添加函数merge(v, p) 表示线段树上编号p节点管辖的区间在左边最大值为v的影响下产生的答案以下考虑几种情况:

  • t[p]的最大值是小于v 此时没有贡献, return 0即可
  • p是叶子节点return t[p].mx>v返回该节点代表的值与v的大小关系即可
  • 考虑左右儿子为ls, rs 若t[ls].mx<=v此时左区间无贡献,递归右区间即可,return merge(v,rs).否则递归左区间,那么右区间的贡献是t[p].len−t[ls].len(注意不是t[rs].len)在pushup的时候,维护好mx,并让t[p].len = t[ls].len + merge(t[ls].mx, rs)即可

最简单的一道题

西邮新生赛的一题,没人过我看到的时候就发现是跟楼房重建一样的trick,然而调bug调了半天,wa了无数发给定n个数,询问从第x个数往后的非严格前缀最小值的长度,要求支持区间加做法跟上题类似,注意在merge里面也要加上pushdown,在每次要访问一个点的左右儿子的时候,就应该下放该点的lazytag上一题的询问都是从1开始的,所以答案就是t[1].len,但本题是从x开始的,我的做法是把[x,n]在线段树上的区间提取出来,然后从左往右合并,区间数是log段,合并也是log的,复杂度是$n(\log^2 n)$

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
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define fi first
#define se second
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 2e5 + 5;
const ll LINF = 1e18 + 5;
constexpr int mod = 1e9 + 7;
int a[N];
int n, m, pos[N];
vector<int> vec;
namespace SegTree
{
  #define ls (p<<1)
  #define rs (p<<1|1)
  struct seg
  {
    int l, r, len;
    ll mn, tag;
  }t[N<<2];
  void setval(int p, ll v)
  {
    t[p].mn += v;
    t[p].tag += v;
  }
  void pushdown(int p)
  {
    setval(ls, t[p].tag); setval(rs, t[p].tag);
    t[p].tag = 0;
  }
  int merge(int v, int p) //重点
  {
    int l = t[p].l, r = t[p].r;
    if(t[p].mn>v) return 0;
    if(l==r) return t[p].mn<=v;
    if(t[p].tag) pushdown(p);
    if(t[ls].mn>v) return merge(v, rs);
    else return merge(v, ls) + t[p].len - t[ls].len;
  }
  void pushup(int p)
  {
    t[p].mn = min(t[ls].mn, t[rs].mn);
    t[p].len = t[ls].len + merge(t[ls].mn, rs);
  }
  void build(int p, int l, int r)
  {
    t[p].l = l, t[p].r = r;
    if(l==r)
    {
      t[p].mn = a[l];
      t[p].len = 1;
      pos[l] = p;
      return;
    }
    int mid = (l+r)>>1;
    build(ls, l, mid); build(rs, mid+1, r);
    pushup(p);
  }
  void upd(int p, int x, int y, int v)
  {
    int l = t[p].l, r = t[p].r;
    if(l>=x && r<=y)
    {
      setval(p, v);
      return;
    }
    if(t[p].tag) pushdown(p);
    int mid = (l+r)>>1;
    if(x<=mid) upd(ls, x, y, v);
    if(y>mid) upd(rs, x, y, v);
    pushup(p);
  }
  void ask(int p, int x, int y)
  {
    int l = t[p].l, r = t[p].r;
    if(l>=x && r<=y)
    {
      vec.pb(p);
      return;
    }
    if(t[p].tag) pushdown(p);
    int mid = (l+r)>>1;
    if(x<=mid) ask(ls, x, y);
    if(y>mid) ask(rs, x, y);
  }
  #undef ls
  #undef rs
}
using namespace SegTree;
char op[2];
int main()
{
  scanf("%d%d", &n, &m);
  for(int i=1; i<=n; i++) scanf("%d", a+i);
  build(1, 1, n);
  for(int i=1; i<=m; i++)
  {
    scanf("%s", op);
    if(op[0]=='c')
    {
      int l, r, k;
      scanf("%d%d%d", &l, &r, &k);
      upd(1, l, r, k);
    }
    else
    {
      int x;
      scanf("%d", &x);
      vec.clear();
      ask(1, x, n);
      int ans = t[vec[0]].len;
      ll mn = t[vec[0]].mn;
      for(int i=1; i<sz(vec); i++)
      {
        ans += merge(mn, vec[i]);
        mn = min(mn, t[vec[i]].mn);
      }
      printf("%d\n", ans-1);
    }
  }
  return 0;
}

copy自小粉兔:

但是，我们注意到一个很关键的性质：当v小于左子树的最大值时，右子树对当前节点的贡献，是通过减法计算的也就是说这个信息要满足一定程度上的可减性但是有很多信息是不满足可减性的，比如max,min、按位与、按位或等为了能让这种线段树适应更一般的情况，我们修改维护的信息的意义：仍然维护这个区间中的最大值。

此时并不是维护区间的答案，而是仅考虑该区间的影响后，却又只统计右子树的答案仅考虑该区间的影响后，却又只统计右子树的答案仅考虑该区间的影响后，却又只统计右子树的答案。也就是说令当前节点对应的区间为[l,r]，区间中点为 mid，则：维护的答案是，只考虑[l,r]时，在区间[mid+1,r]中的答案。

线段树每个节点仍然维护mx[i], len[i],但对于叶节点len[i]无意义,再考虑merge(v, p)函数

1
2
3
4
5
6
7
8
9
10
11
12
13
void pushup(int p)
{
  t[p].mx = max(t[ls].mx, t[rs].mx);
  t[p].len = merge(t[ls].mx, rs);
}
int merge(int v, int p)
{
  int l = t[p].l, r = t[p].r;
  if(t[p].mx<=v) return 0;
  if(l==r) return t[p].mn>v;
  if(t[ls].mx<=v) return merge(v, rs);
  else return merge(v, ls) + t[p].len; //避免了区间维护信息不可减的问题
}