数据结构（二）#

1
struct my_tree
2
{
3
  #define kl (k<<1)
4
  #define kr (k<<1|1)
5

6
  struct node
7
  {
8
    int l, r, sum;
9
    int lz;
10
  };
11
  vector<node> tree;
12

13

14
  my_tree(int x,ve<int>&a)
15
  {
16
    tree = vector<node>(x*4+10);
17
    build(1,1,x,a);
18
  }
19

20
  void pushup(node& kk, const node& kkl, const node& kkr)
21
  {
22
    kk.sum = max(kkl.sum, kkr.sum);
23
  }
24
  void pushup(int k)
25
  {
26
    pushup(tree[k], tree[kl], tree[kr]);
27
  }
28

29

30
  void pushdown(int k)
31
  {
32
    if(tree[k].lz==0) return ;
33
    tree[kl].sum=tree[kr].sum=tree[k].lz;
34
    tree[kl].lz=tree[kr].lz=tree[k].lz;
35
    tree[k].lz=0;
36
  }
37

38
  void build(int k, int l, int r, ve<int>& a)
39
  {
40
    tree[k].l = l;
41
    tree[k].r = r;
42
    if (l == r)
43
    {
44
      tree[k].sum = a[l];
45
      return;
46
    }
47
    int mid = (l + r) >> 1;
48
    build(kl, l, mid, a);
49
    build(kr, mid + 1, r, a);
50
    pushup(k);
51
  }
52

53
  // 区间修改   区间修改 [l,r] 全复制成val
54
  void update(int k, int l, int r, int val)
55
  {
56
    if (tree[k].l >= l && tree[k].r <= r)
57
    {
58
      tree[k].sum = val;
59
      tree[k].lz=val;
60
      return;
61
    }
62
    pushdown(k);
63
    int mid = (tree[k].l + tree[k].r) >> 1;
64
    if (l <= mid) update(kl, l, r, val);
65
    if (r > mid) update(kr, l, r, val);
66
    pushup(k);
67
  }
68

69
  node query(int k, int l, int r)
70
  {
71
    if (l <= tree[k].l && tree[k].r <= r) return tree[k];
72
    pusgdown(k);
73

74
    int mid = (tree[k].l + tree[k].r) >> 1;
75

76
    node kkl = {tree[k].l, mid};
77
    node kkr = {mid + 1, tree[k].r};
78
    node kk = {tree[k].l, tree[k].r};
79

80
    int opl=0,opr=0;
81
    if (l <= mid) kkl = query(kl, l, r),opl=1;
82
    if (r > mid) kkr = query(kr, l, r),opr=1;
83
    if(opl&&opr)
84
    {
85
      pushup(kk, kkl, kkr);
86
      return kk;
87
    }
88
    if(opl) return kkl;
89
    return kkr;
90
  }
91

92

93
  void dug(int k=1)
94
  {
95
    auto [l,r,sum,lz]=tree[k];
96
    cout<<"k: "<<k<<"\n";
97
    cout<<"[ "<<l<<" "<<r<<" "<<sum<<" "<<lz<<" ]"<<'\n';
98
    if(l<r)
99
    {
100
      dug(kl);
101
      dug(kr);
102
    }
103
  }
104
};

1
#define kl (k<<1)
2
#define kr (k<<1|1)
3

4
struct node
5
{
6
    int l,r;
7
    int sum;
8
}tre[N*4+10];
9

10
void build(int k,int l,int r)
11
{
12
    tre[k]={l,r};
13
    if(l==r) return ;
14
    int mid=(l+r)>>1;
15
    build(kl,l,mid);
16
    build(kr,mid+1,r);
17
}
18

19
void insert(int k,int val,int id)
20
{
21
    tre[k].sum+=id;
22
    if(tre[k].l==tre[k].r) return ;
23
    int mid=(tre[k].l+tre[k].r)>>1;
24
    if(val<=mid) insert(kl,val,id);
25
    else insert(kr,val,id);
26
}
27

28
int query(int k,int l,int r)
29
{
30
    if(l<=tre[k].l&&tre[k].r<=r) return tre[k].sum;
31
    int mid=(tre[k].l+tre[k].r)>>1;
32
    int ans=0;
33
    if(l<=mid) ans+=query(kl,l,r);
34
    if(r>mid) ans+=query(kr,l,r);
35
    return ans;
36
}