联考「联测缺尾(memory)」题解

考虑用线段树维护，线段树的每个节点都是一个堆，堆中维护的是插入在当前节点的值（相当于一个永久懒标记）。同时维护当前节点对应的区间的最大值。

对于操作1，直接按照模板线段树插入即可，注意懒标记插入在节点对应的堆里面。
对于操作3，直接按照模板线段树查询即可。
对于操作2分成三种情况：
- 当前节点对应的区间最大值小于删除的值：直接跳过
- 当前节点对应的堆没有删除的值，但是字节点有：对于这种情况直接将修改操作递归到子节点即可。
- 当前节点对应的堆有删除的值：这种情况需要从堆中删除查询的值，但是如果有这种情况：
  即待删除区间两边或一边还有多余的空间，则需要把量变的区间通过操作1把误删除的数值插入回去。

Info

每次操作过后需要重新获取最大值，获取最大值的代码一般如下

1
2
arr[u].mx = max(arr[arr[u].lc].mx,arr[arr[u].rc].mx);
if(!arr[u].tg.empty()) arr[u].mx = max(arr[u].mx,arr[u].tg.top());

其中 $u$ 为当前节点

Tip

因为对于操作2，查询区间为空集就不操作；对于操作3，查询区间为空集则输出 $-1$，考虑到每个节点的子节点默认为 $0$（在动态开点情况下），所以建议把 $0$ 号节点的最大值设成 $-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
#include <bits/stdc++.h>
#include <cstdio>
using namespace std;
class SegmentTree {
private:
  struct TreeNode {
    int l,r,lc,rc,mx;
    priority_queue<int> tg;
  };
  vector<TreeNode> arr;
  int siz = 0;
  void __del(int u,int l,int r,int k) {
    if(arr[u].mx < k) return;
    if(!arr[u].tg.empty() && arr[u].tg.top() == k) {
      arr[u].tg.pop();
      if(arr[u].l < l)
        insert(1,arr[u].l,l - 1,k);
      if(r < arr[u].r)
        insert(1,r + 1,arr[u].r,k);
      arr[u].mx = max(arr[arr[u].lc].mx,arr[arr[u].rc].mx);
      if(!arr[u].tg.empty()) arr[u].mx = max(arr[u].mx,arr[u].tg.top());
    } else {
      int mid = (arr[u].l + arr[u].r) / 2;
      if(l <= mid) __del(arr[u].lc,l,r,k);
      if(mid < r) __del(arr[u].rc,l,r,k);
      arr[u].mx = max(arr[arr[u].lc].mx,arr[arr[u].rc].mx);
      if(!arr[u].tg.empty()) arr[u].mx = max(arr[u].mx,arr[u].tg.top());
    }
  }
  int init(int l,int r) {
    int u = ++siz;
    arr[u].l = l;
    arr[u].r = r;
    arr[u].mx = -1;
    arr[u].tg.push(-1);
    if(l == r) {
      return u;
    }
    int mid = (l + r) / 2;
    arr[u].lc = init(l,mid);
    arr[u].rc = init(mid + 1,r);
    return u;
  }
public:
  void build(int n) {
    arr.resize(2 * n + 5);
    init(1,n);
    arr[0] = {0,0,0,0,-1,{}};
  }
  void insert(int u,int l,int r,int k) {
    if(l <= arr[u].l && arr[u].r <= r) {
      arr[u].tg.push(k);
      arr[u].mx = max(arr[u].mx,arr[u].tg.top());
      return;
    }
    int mid = (arr[u].l + arr[u].r) / 2;
    if(l <= mid) insert(arr[u].lc,l,r,k);
    if(mid < r) insert(arr[u].rc,l,r,k);
    arr[u].mx = max(arr[arr[u].lc].mx,arr[arr[u].rc].mx);
    if(!arr[u].tg.empty())
      arr[u].mx = max(arr[u].mx,arr[u].tg.top());
  }
  int query(int u,int l,int r) {
    if(l <= arr[u].l && arr[u].r <= r) {
      return arr[u].mx;
    }
    int mid = (arr[u].l + arr[u].r) / 2;
    int ans = (arr[u].tg.empty() ? -1 : arr[u].tg.top());
    if(l <= mid) ans = max(ans,query(arr[u].lc,l,r));
    if(mid < r) ans = max(ans,query(arr[u].rc,l,r));
    return ans;
  }
  void del(int u,int l,int r) {
    int qq = query(u,l,r);
    if(qq != -1) __del(u,l,r,qq);
  }
} sg;
int main() {
  ios::sync_with_stdio(0);cin.tie(0);
  int n,m;
  cin >> n >> m;
  sg.build(200000);
  int op,l,r,k;
  while(m--) {
    cin >> op;
    if(op == 1) {
      cin >> l >> r >> k;
      sg.insert(1, l, r, k);
    } else if(op == 2) {
      cin >> l >> r;
      sg.del(1, l, r);
    } else {
      cin >> l >> r;
      int qq = sg.query(1, l, r);
      cout << qq << '\n';
    }
  }
  return 0;
}