比较纯粹的分块线段树等 DS 趣题
Posted Updated Notes20 minutes read (About 2993 words)

比较纯粹的分块线段树等 DS 趣题

要你求一个区间的最大子段和。
那么，显然地，我们可以维护区间最大前缀和和后缀和。
即根据左区间后缀和加上右区间前缀和可以等于最大子段和这个性质。

那么如何维护最大前缀和和最大后缀和呢？

显然一段区间分成两块，最大前缀和有可能是左区间的最大前缀和，也有可能是左区间的 Sum 加上右区间的最大前缀和，那么这样想，右区间也就没有疑问了。
然后正常操作即可。

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
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 5e4 + 10;
int n, m, a[N];

struct seg {
  int Lmax, Rmax, all, sum;
} t[N<<2];

#define ls ((rt)<<1)
#define rs ((rt)<<1|1)

void pushup(int rt) {
  t[rt].sum = t[ls].sum + t[rs].sum;
  // deal with Maximum Lmax
  t[rt].Lmax = max(t[ls].Lmax, t[ls].sum + t[rs].Lmax);
  // deal with Maximum Rmax
  t[rt].Rmax = max(t[rs].Rmax, t[rs].sum + t[ls].Rmax);
  // deal with the all Max
  t[rt].all = t[ls].Rmax + t[rs].Lmax;
  t[rt].all = max(t[rt].all, max(t[ls].all, t[rs].all));
  return ;
}

seg pushup_ret(seg l, seg r) {
  seg Root; Root.sum = l.sum + r.sum;
  // deal with Maximum Lmax
  Root.Lmax = max(l.Lmax, l.sum + r.Lmax);
  // deal with Maximum Rmax
  Root.Rmax = max(r.Rmax, r.sum + l.Rmax);
  // deal with the all Max
  Root.all = l.Rmax + r.Lmax;
  Root.all = max(Root.all, max(l.all, r.all));
  return Root;
}

void build(int rt, int l, int r) {
  if (l==r) {
    t[rt].all = t[rt].sum = a[l];
    t[rt].Lmax = t[rt].Rmax = a[l];
    return ;
  }
  int mid = (l+r) >> 1;
  build(ls, l, mid), build(rs, mid+1, r);
  pushup(rt); return ;
}

void read(int &ret) {
  ret = 0; char ch = getchar(); int f = 1;
  while (!isdigit(ch) && ch^'-') ch = getchar();
  if (ch=='-') f = -1, ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } ret *= f; return ;
}

seg query(int rt, int l, int r, int L, int R) {
  if (L<=l && r<=R) return t[rt];
  int mid = (l+r) >> 1, tag = 0; seg ans1, ans2;
  if (L<=mid) ++tag, ans1 = query(ls, l, mid, L, R);
  if (R>mid) tag += 2, ans2 = query(rs, mid+1, r, L, R);
  if (tag==1) return ans1; if (tag==2) return ans2;
  return pushup_ret(ans1, ans2);
}

signed main() {
  read(n);
  for (int i=1; i<=n; ++i) read(a[i]);
  build(1, 1, n);
  read(m); while (m--) {
    int l, r; read(l), read(r);
    printf("%lld\n", query(1, 1, n, l, r).all);
  }
  return 0;
}

带修区间最大子段和。
。没什么好说的了。

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

const int N = 5e4 + 10;
int n, m, a[N];

#define ls ((rt)<<1)
#define rs ((rt)<<1|1)

void read(int &ret) {
  ret = 0; char ch = getchar(); int f = 1;
  while (!isdigit(ch) && ch^'-') ch = getchar();
  if (ch=='-') f = -1, ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } ret *= f; return ;
}

struct seg {
  int Lmax, Rmax, sum, all;
  seg(int Lmax, int Rmax, int sum, int all):
    Lmax(Lmax), Rmax(Rmax), sum(sum), all(all) {}
  seg() {}
} t[N<<2];

void pushup(int rt) {
  t[rt].sum = t[ls].sum + t[rs].sum;
  t[rt].Lmax = max(t[ls].Lmax, t[ls].sum+t[rs].Lmax);
  t[rt].Rmax = max(t[rs].Rmax, t[rs].sum+t[ls].Rmax);
  t[rt].all = max(t[ls].all, t[rs].all);
  t[rt].all = max(t[rt].all, t[ls].Rmax+t[rs].Lmax);
  return ;
}

seg pushup_ret(seg l, seg r) {
  seg ans; ans = seg(0, 0, 0, 0);
  ans.sum = l.sum + r.sum;
  ans.Lmax = max(l.Lmax, l.sum+r.Lmax);
  ans.Rmax = max(r.Rmax, r.sum+l.Rmax);
  ans.all = max(l.all, r.all);
  ans.all = max(ans.all, l.Rmax+r.Lmax);
  return ans;
}

void build(int rt, int l, int r) {
  if (l==r) { t[rt] = seg(a[l], a[l], a[l], a[l]); return ; }
  int mid = (l+r) >> 1;
  build(ls, l, mid), build(rs, mid+1, r);
  pushup(rt); return ;
}

void upd(int rt, int l, int r, int pos, int f) {
  if (l==r) { t[rt] = seg(f, f, f, f); return; }
  int mid = (l+r) >> 1;
  if (pos<=mid) upd(ls, l, mid, pos, f);
  else upd(rs, mid+1, r, pos, f);
  pushup(rt); return ;
}

seg query(int rt, int l, int r, int L, int R) {
  if (L<=l && r<=R) return t[rt];
  int mid = (l+r) >> 1, tag = 0; seg ans1, ans2;
  if (L<=mid) ++tag, ans1 = query(ls, l, mid, L, R);
  if (R>mid) tag += 2, ans2 = query(rs, mid+1, r, L, R);
  if (tag==1) return ans1; if (tag==2) return ans2;
  return pushup_ret(ans1, ans2);
}

int main() {
  read(n);
  for (int i=1; i<=n; ++i) read(a[i]);
  build(1, 1, n);
  read(m); while (m--) {
    int opt, l, r; read(opt);
    read(l), read(r);
    if (!opt) upd(1, 1, n, l, r);
    else printf("%d\n", query(1, 1, n, l, r).all);
  }
  return 0;
}

Update 区间开方，Query 区间和。
那么根据某上帝造题的套路，因为 $\sqrt{1}=1$，所以可以维护一个区间 Max。
如果当前区间 Max = 1，那么直接退出循环，停止修改。
然后 pushdown 的时候 lazytag 下传一下。
没别的了。

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
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 10;
int n, m, cnt, a[N];

struct seg {
  int sum, Max;
} t[N<<2];

#define ls ((rt)<<1)
#define rs ((rt)<<1|1)

void pushup(int rt) {
  t[rt].Max = max(t[ls].Max, t[rs].Max);
  t[rt].sum = t[ls].sum + t[rs].sum;
  return ;
}

void upd(int rt, int l, int r, int L, int R) {
  if (t[rt].Max<=1) return ;
  if (l==r) {
    t[rt].sum = sqrt(t[rt].sum);
    t[rt].Max = t[rt].sum; return ;
  }
  int mid = (l+r) >> 1;
  if (L<=mid) upd(ls, l, mid, L, R);
  if (R>mid) upd(rs, mid+1, r, L, R);
  pushup(rt); return ;
}

int query(int rt, int l, int r, int L, int R) {
  if (L<=l && r<=R) return t[rt].sum;
  int mid = (l+r) >> 1, ans = 0;
  if (L<=mid) ans += query(ls, l, mid, L, R);
  if (R>mid) ans += query(rs, mid+1, r, L, R);
  return ans;
}

void read(int &ret) {
  ret = 0; char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } return ;
}

void build(int rt, int l, int r) {
  if (l==r) {
    t[rt].sum = a[l];
    t[rt].Max = t[rt].sum; return ;
  }
  int mid = (l+r) >> 1;
  build(ls, l, mid), build(rs, mid+1, r);
  pushup(rt); return ;
}

signed main() {
  while (cin >> n) {
    for (int i=1; i<=n; ++i) read(a[i]);
    build(1, 1, n); read(m);
    printf("Case #%lld:\n", ++cnt);
    while (m--) {
      int opt, l, r; read(opt);
      read(l), read(r); if (l>r) swap(l, r);
      if (!opt) upd(1, 1, n, l, r);
      else printf("%lld\n", query(1, 1, n, l, r));
    } puts("");
  }
  return 0;
}

区修单查。
直接维护一个块内加法的 tag 和零散块的 tag 即可。
零散块为了方便可以直接加在原数组里面。

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

const int N = 5e4 + 10;
int n, a[N], tag[N], bel[N];
int Len, beg[N], End[N];

void read(int &ret) {
  ret = 0; char ch = getchar(); int f = 1;
  while (!isdigit(ch) && ch^'-') ch = getchar();
  if (ch=='-') f = -1, ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } ret *= f; return ;
}

void upd(int l, int r, int f) {
  if (bel[l] == bel[r]) {
    for (int i=l; i<=r; ++i) a[i] += f;
    return ;
  }
  for (int i=bel[l]+1; i<bel[r]; ++i) tag[i] += f;
  for (int i=l; i<=End[bel[l]]; ++i) a[i] += f;
  for (int i=beg[bel[r]]; i<=r; ++i) a[i] += f;
  return ;
}

void init() {
  read(n); Len = sqrt(n);
  for (int i=1; i<=n; ++i) read(a[i]);
  for (int i=1; i<=Len; ++i) {
    beg[i] = (i-1) * Len + 1;
    End[i] = i * Len;
    for (int j=beg[i]; j<=End[i]; ++j)
      bel[j] = i;
  }
  if (Len*Len == n) return ;
  beg[Len+1] = Len * Len + 1, End[Len+1] = n;
  for (int i=beg[Len+1]; i<=n; ++i) bel[i] = Len + 1;
  return ;
}

int query(int pos) {
  return a[pos] + tag[bel[pos]];
}

int main() {
  init();
  while (n--) {
    int opt, l, r, c;
    read(opt), read(l), read(r), read(c);
    if (!opt) upd(l, r, c);
    else printf("%d\n", query(r));
  }
}

区间修改，区间查询 $<k$ 的数的个数。

不难想到直接块内排个序就没了。
这个时候就要考虑零散块了。
因为排了序，所以原来的下标都换了位置。
那么我们可以暴力一点，直接在输入的数组里面进行修改，在这之后把零散块所在的区间全部重新赋值一遍，然后再块内排个序即可。可以保证这个是正确的，因为区间 tag 是区间统一加上，所以原来的相对关系都没有变，所以是对的！

那么要注意的是，query 的时候查询零散块要查询输入数组而非块内已排序的数组。
为什么？还是那个 id 变化的问题，下标不一样嘛。

我才不会告诉你就是这个问题卡了我好久

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

const int N = 5e4 + 10;
const int M = 233;

int n, a[N], tag[M], bel[N];
int Num, Len, beg[M], End[M];

struct seg { int val[M]; } t[M];

void read(int &ret) {
  ret = 0; char ch = getchar(); int f = 1;
  while (!isdigit(ch) && ch^'-') ch = getchar();
  if (ch=='-') f = -1, ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } ret *= f; return ;
}

void upd(int l, int r, int f) {
  if (bel[l] == bel[r]) {
    for (int i=l; i<=r; ++i) a[i] += f;
    for (int i=beg[bel[l]]; i<=End[bel[l]]; ++i) {
      int y = (i-1) % Len + 1;
      t[bel[l]].val[y] = a[i];
    }
    int segm = End[bel[l]] - beg[bel[l]] + 1;
    sort(t[bel[l]].val+1, t[bel[l]].val+1+segm);
    return ;
  }
  for (int i=bel[l]+1; i<bel[r]; ++i) tag[i] += f;
  for (int i=l; i<=End[bel[l]]; ++i) a[i] += f;
  for (int i=beg[bel[r]]; i<=r; ++i) a[i] += f;
  for (int i=beg[bel[l]]; i<=End[bel[l]]; ++i) {
    int y = (i-1) % Len + 1;
    t[bel[l]].val[y] = a[i];
  }
  for (int i=beg[bel[r]]; i<=End[bel[r]]; ++i) {
    int y = (i-1) % Len + 1;
    t[bel[r]].val[y] = a[i];
  }
  int segml = End[bel[l]] - beg[bel[l]] + 1;
  sort(t[bel[l]].val+1, t[bel[l]].val+1+segml);
  int segmr = End[bel[r]] - beg[bel[r]] + 1;
  sort(t[bel[r]].val+1, t[bel[r]].val+1+segmr);
  return ;
}

void init() {
  read(n); Len = sqrt(n); Num = n/Len;
  for (int i=1; i<=n; ++i) {
    int x = (i-1) / Len + 1, y = (i-1) % Len + 1;
    read(t[x].val[y]); a[i] = t[x].val[y];
  }
  for (int i=1; i<=Num; ++i) {
    beg[i] = (i-1) * Len + 1;
    End[i] = i * Len;
    for (int j=beg[i]; j<=End[i]; ++j) bel[j] = i;
  }
  if (End[Num]==n) return ; else ++Num;
  beg[Num] = End[Num-1] + 1, End[Num] = n;
  for (int i=beg[Num]; i<=n; ++i) bel[i] = Num;
  return ;
}

int query(int l, int r, int Lim) {
  // checking for updates
  if (bel[l] == bel[r]) {
    int cnt = 0;
    for (int i=l; i<=r; ++i)
      if (a[i] + tag[bel[l]] < Lim) ++cnt;
    return cnt;
  }
  int ans = 0;
  for (int i=bel[l]+1; i<bel[r]; ++i)
    ans += ((lower_bound(t[i].val+1, t[i].val+1+Len, Lim-tag[i])-t[i].val)-1);
  for (int i=l; i<=End[bel[l]]; ++i)
    if (a[i] + tag[bel[l]] < Lim) ++ans;
  for (int i=beg[bel[r]]; i<=r; ++i)
    if (a[i] + tag[bel[r]] < Lim) ++ans;
  return ans;
}

int main() {
  // freopen("fk2.in", "r", stdin);
  // freopen("fk2.out", "w", stdout);
  init();
  for (int i=1; i<=Num; ++i) {
    int segm = End[i] - beg[i] + 1;
    sort(t[i].val+1, t[i].val+segm+1);
  }
  while (n--) {
    int opt, l, r, c;
    read(opt), read(l), read(r), read(c);
    if (!opt) upd(l, r, c);
    else printf("%d\n", query(l, r, c*c));
  }
  return 0;
}

区间加法，区间前驱。

简单题。每一次区间加法直接加到 tag 里面去。
然后区间前驱对于每一个块都扫一遍 lower_bound。
接着零散块暴力扫。取一个 Max 即可。

注意零散块扫的是原来的数组，update 完之后要重新更新左右两个块。
以及不要忘记在求前驱的时候加上 tag。

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
#include <bits/stdc++.h>
#define int long long
using namespace std;

void read(int &ret) {
  ret = 0; char ch = getchar(); int f = 1;
  while (!isdigit(ch) && ch^'-') ch = getchar();
  if (ch=='-') f = -1, ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } ret *= f; return ;
}

const int N = 1e5 + 10;
const int M = 350;

int n, Len, Num, beg[M], End[M];
int a[N], tag[M], bel[N];
int Length[M], seg[M][M];

void init() {
  read(n); Len = sqrt(n), Num = n / Len;
  for (int i=1; i<=n; ++i) read(a[i]);
  for (int i=1; i<=Num; ++i) {
    beg[i] = Len*(i-1)+1, End[i] = Len*i;
    for (int j=beg[i]; j<=End[i]; ++j)
      bel[j] = i, seg[i][(j-1)%Len+1] = a[j];
    Length[i] = Len;
  }
  if (End[Num]==n) return ; ++Num;
  beg[Num] = End[Num-1] + 1, End[Num] = n;
  for (int i=beg[Num]; i<=End[Num]; ++i)
    bel[i] = Num, seg[Num][(i-1)%Len+1] = a[i];
  Length[Num] = End[Num] - beg[Num] + 1;
  return ;
}

void upd(int l, int r, int f) {
  if (bel[l]==bel[r]) {
    for (int i=l; i<=r; ++i) a[i] += f;
    for (int i=beg[bel[l]]; i<=End[bel[r]]; ++i)
      seg[bel[l]][(i-1)%Len+1] = a[i];
    sort(seg[bel[l]]+1, seg[bel[l]]+1+Length[bel[l]]);
    return ;
  }
  for (int i=bel[l]+1; i<bel[r]; ++i) tag[i] += f;
  for (int i=l; i<=End[bel[l]]; ++i) a[i] += f;
  for (int i=beg[bel[r]]; i<=r; ++i) a[i] += f;
  for (int i=beg[bel[l]]; i<=End[bel[l]]; ++i)
    seg[bel[l]][(i-1)%Len+1] = a[i];
  for (int i=beg[bel[r]]; i<=End[bel[r]]; ++i)
    seg[bel[r]][(i-1)%Len+1] = a[i];
  sort(seg[bel[l]]+1, seg[bel[l]]+1+Length[bel[l]]);
  sort(seg[bel[r]]+1, seg[bel[r]]+1+Length[bel[r]]);
  return ;
}

int query(int l, int r, int x) {
  if (bel[l]==bel[r]) {
    int Max = -1e18;
    for (int i=l; i<=r; ++i)
      if (a[i]+tag[bel[i]]<x) Max = max(Max, a[i]+tag[bel[i]]);
    return (Max==-1e18)? -1:Max;
  }
  int Max = -1e18;
  for (int i=bel[l]+1; i<bel[r]; ++i) {
    int cur = lower_bound(seg[i]+1, seg[i]+1+Length[i], x-tag[i])-seg[i]-1;
    if (!cur) continue; Max = max(Max, seg[i][cur]+tag[i]);
  }
  for (int i=l; i<=End[bel[l]]; ++i)
    if (a[i]+tag[bel[i]]<x) Max = max(Max, a[i]+tag[bel[i]]);
  for (int i=beg[bel[r]]; i<=r; ++i)
    if (a[i]+tag[bel[i]]<x) Max = max(Max, a[i]+tag[bel[i]]);
  return (Max==-1e18)? -1:Max;
}

signed main() {
  // freopen("fk3.in", "r", stdin);
  // freopen("fk3.out", "w", stdout);
  init();
  for (int i=1; i<=Num; ++i)
    sort(seg[i]+1, seg[i]+1+Length[i]);
  while (n--) {
    int opt, L, R, c; read(opt);
    read(L), read(R), read(c);
    if (!opt) upd(L, R, c);
    else printf("%lld\n", query(L, R, c));
  }
  return 0;
}

区间加法，区间求和。
直接记录一下块内的和 Sum 即可。
然后维护一个 tag，和原数组 a，查询暴力查询即可。

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
#include <bits/stdc++.h>
#define int long long
using namespace std;

void read(int &ret) {
  ret = 0; char ch = getchar(); int f = 1;
  while (!isdigit(ch) && ch^'-') ch = getchar();
  if (ch=='-') f = -1, ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } ret *= f; return ;
}

const int N = 5e4 + 10;
const int M = 233;

int n, Len, Num, a[N], tag[M], add[M];
int beg[M], End[M], Length[M], bel[N];

void init() {
  read(n); Len = sqrt(n); Num = n / Len;
  for (int i=1; i<=n; ++i) read(a[i]);
  for (int i=1; i<=Num; ++i) {
    beg[i] = (i-1)*Len+1, End[i] = i*Len, Length[i] = Len;
    for (int j=beg[i]; j<=End[i]; ++j)
      bel[j] = i, add[i] += a[j];
  }
  if (Len*Num==n) return; ++Num;
  beg[Num] = End[Num-1]+1, End[Num] = n;
  for (int i=beg[Num]; i<=End[Num]; ++i)
    bel[i] = Num, add[Num] += a[i];
  return ;
}

void upd(int l, int r, int x) {
  if (bel[l]==bel[r]) {
    for (int i=l; i<=r; ++i) a[i] += x;
    add[bel[l]] += x*(r-l+1); return ;
  }
  for (int i=bel[l]+1; i<bel[r]; ++i)
    tag[i] += x, add[i] += x*Len;
  for (int i=l; i<=End[bel[l]]; ++i) a[i] += x;
  for (int i=beg[bel[r]]; i<=r; ++i) a[i] += x;
  add[bel[l]] += x*(End[bel[l]]-l+1);
  add[bel[r]] += x*(r-beg[bel[r]]+1);
  /* cout << "TAG: "; for (int i=1; i<=Num; ++i) cout << tag[i] << ' ';
  cout << endl << "ADD: "; for (int i=1; i<=Num; ++i) cout << add[i] << ' ';
  cout << endl; */
  return ;
}

int query(int l, int r, int Mod) {
  if (bel[l]==bel[r]) {
    int sum = 0;
    for (int i=l; i<=r; ++i) sum += (a[i] + tag[bel[l]]);
    return (sum%Mod + Mod) % Mod;
  }
  int sum = 0;
  for (int i=bel[l]+1; i<bel[r]; ++i)
    sum = (sum+add[i]) % Mod;
  for (int i=l; i<=End[bel[l]]; ++i)
    sum = (sum+tag[bel[l]]+a[i]) % Mod;
  for (int i=beg[bel[r]]; i<=r; ++i)
    sum = (sum+tag[bel[r]]+a[i]) % Mod;
  return (sum%Mod + Mod) % Mod;
}

signed main() {
  init();
  while (n--) {
    int opt, L, R, x; read(opt);
    read(L), read(R), read(x);
    if (!opt) upd(L, R, x);
    else printf("%lld\n", query(L, R, x+1));
  }
  return 0;
}

区间开方，区间求和。
因为一个数最多被开方多少多少次（懒得算），所以直接类比线段树做法。
对于每一个块如果 Max $\le 1$ 了直接跳过，根本不需要开方。
否则直接暴力修改整个块，更新 Sum 数组即可。

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
#include <bits/stdc++.h>
#define int long long
using namespace std;

void read(int &ret) {
  ret = 0; char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } return ;
}

const int N = 5e4 + 10;
const int M = 233;

int n, Len, Num, beg[M], End[N], Max[M];
int Length[M], a[N], add[M], bel[N];

void init() {
  read(n); Len = sqrt(n), Num = n / Len;
  for (int i=1; i<=n; ++i) read(a[i]);
  for (int i=1; i<=Num; ++i) {
    beg[i] = (i-1)*Len+1, End[i] = i*Len;
    for (int j=beg[i]; j<=End[i]; ++j)
      bel[j] = i, add[i] += a[j], Max[i] = max(Max[i], a[j]);
  }
  if (End[Num]==n) return ; ++Num;
  beg[Num] = End[Num-1] + 1, End[Num] = n;
  for (int i=beg[Num]; i<=End[Num]; ++i)
    bel[i] = Num, add[Num] += a[i], Max[Num] = max(Max[Num], a[i]);
  return ;
}

void upd(int l, int r) {
  if (bel[l]==bel[r]) {
    for (int i=l; i<=r; ++i) {
      int to = sqrt(a[i]);
      add[bel[l]] += to - a[i], a[i] = to;
    }
    Max[bel[l]] = 0;
    for (int i=beg[bel[l]]; i<=End[bel[l]]; ++i)
      Max[bel[l]] = max(Max[bel[l]], a[i]);
    return ;
  }
  for (int i=l; i<=End[bel[l]]; ++i) {
    int to = sqrt(a[i]);
    add[bel[l]] += to - a[i], a[i] = to;
  }
  for (int i=beg[bel[l]]; i<=End[bel[l]]; ++i)
    Max[bel[l]] = max(Max[bel[l]], a[i]);
  for (int i=beg[bel[r]]; i<=r; ++i) {
    int to = sqrt(a[i]);
    add[bel[r]] += to - a[i], a[i] = to;
    Max[bel[r]] = max(Max[bel[r]], to);
  }
  for (int i=beg[bel[r]]; i<=End[bel[r]]; ++i)
    Max[bel[r]] = max(Max[bel[r]], a[i]);
  for (int i=bel[l]+1; i<bel[r]; ++i) {
    if (Max[i]<=1) continue; Max[i] = 0;
    for (int j=beg[i]; j<=End[i]; ++j) {
      int to = sqrt(a[j]);
      add[i] += to - a[j], a[j] = to;
      Max[i] = max(Max[i], to);
    }
  } return ;
}

int query(int l, int r) {
  if (bel[l]==bel[r]) {
    int sum = 0;
    for (int i=l; i<=r; ++i) sum += a[i];
    return sum;
  }
  int sum = 0;
  for (int i=bel[l]+1; i<bel[r]; ++i) sum += add[i];
  for (int i=l; i<=End[bel[l]]; ++i) sum += a[i];
  for (int i=beg[bel[r]]; i<=r; ++i) sum += a[i];
  return sum;
}

signed main() {
  init();
  while (n--) {
    int opt, L, R, x; read(opt);
    read(L), read(R), read(x);
    if (!opt) upd(L, R);
    else printf("%lld\n", query(L, R));
  }
  return 0;
}

单点插入，单点查询。

对于每一个块维护一个 vector 和 siz。
然后对于每一个插入操作，直接插入 vector 即可，siz 更新。
单点查询只要将查询的 id 遍历一遍减掉 siz 看什么时候满足当前 siz 即可。
插入操作也是一样。

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

void read(int &ret) {
  ret = 0; char ch = getchar(); int f = 1;
  while (!isdigit(ch) && ch^'-') ch = getchar();
  if (ch=='-') f = -1, ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } ret *= f; return ;
}

const int N = 1e5 + 10;
const int M = 350;

vector <int> seg[M];
int n, Len, Num, bel[N], beg[M];
int End[M], Length[M];

#define pb push_back
#define ins insert

void init() {
  read(n); Len = sqrt(n), Num = n / Len;
  for (int i=1; i<=Num; ++i) {
    beg[i] = (i-1)*Len + 1, End[i] = i*Len;
    for (int j=beg[i]; j<=End[i]; ++j) {
      int x; read(x); seg[i].pb(x);
      bel[j] = i;
    } Length[i] = Len;
  }
  if (End[Num]==n) return ; ++Num;
  beg[Num] = End[Num-1] + 1, End[Num] = n;
  for (int i=beg[Num]; i<=End[Num]; ++i) {
    int x; read(x); seg[Num].pb(x);
    bel[i] = Num;
  } Length[Num] = n - beg[Num] + 1;
  return ;
}

void upd(int pos, int x) {
  for (int i=1; i<=Num; ++i) {
    if (pos<=Length[i]) {
      seg[i].ins(seg[i].begin()+pos-1, x);
      ++Length[i]; return ;
    }
    pos -= Length[i];
  } return ;
}

int query(int pos) {
  for (int i=1; i<=Num; ++i) {
    if (pos<=Length[i]) return seg[i][pos-1];
    pos -= Length[i];
  }
}

int main() {
  init();
  while (n--) {
    int opt, L, R, x; read(opt);
    read(L), read(R), read(x);
    if (!opt) upd(L, R);
    else printf("%d\n", query(R));
  }
  return 0;
}

区间加，区间乘，单点查询。
直接参考线段树加法乘法操作即可。
首先优先级肯定乘法大于加法，所以考虑维护两个 tag。
即 addtag 和 multag。
然后区间加和区间乘最重要的就是类似于 pushdown 之类的东西。
就是根据优先级直接将当前区间标记下放乱搞即可。

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
#include <bits/stdc++.h>
#define int long long
using namespace std;

void read(int &ret) {
  ret = 0; char ch = getchar(); int f = 1;
  while (!isdigit(ch) && ch^'-') ch = getchar();
  if (ch=='-') f = -1, ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } ret *= f; return ;
}

const int N = 1e5 + 10;
const int M = 350;
const int Mod = 1e4 + 7;

int n, Len, Num, a[N], bel[N];
int addtag[M], multag[M];
int beg[M], End[M], Length[M];

void init() {
  read(n); Len = sqrt(n), Num = n / Len;
  for (int i=1; i<=Num+1; ++i) multag[i] = 1;
  for (int i=1; i<=Num; ++i) {
    beg[i] = (i-1)*Len+1, End[i] = i*Len;
    Length[i] = End[i] - beg[i] + 1;
    for (int j=beg[i]; j<=End[i]; ++j)
      read(a[j]), bel[j] = i;
  }
  if (End[Num]==n) return ; ++Num;
  beg[Num] = End[Num-1] + 1, End[Num] = n;
  for (int i=beg[Num]; i<=End[Num]; ++i)
    read(a[i]), bel[i] = Num;
  return ;  
}

void reset(int x) {
  for (int i=beg[x]; i<=End[x]; ++i)
    a[i] = (a[i] * multag[x] + addtag[x]) % Mod;
  multag[x] = 1, addtag[x] = 0;
  return ;
}

void upd(int l, int r, int x, bool opt) {
  if (bel[l]==bel[r]) {
    reset(bel[l]);
    for (int i=l; i<=r; ++i)
      if (!opt) a[i] = (a[i] + x) % Mod;
      else a[i] = (a[i] * x) % Mod;
    return ;
  }
  reset(bel[l]), reset(bel[r]);
  for (int i=bel[l]+1; i<bel[r]; ++i)
    if (!opt) addtag[i] = (addtag[i] + x) % Mod;
    else addtag[i] = (addtag[i] * x) % Mod,
        multag[i] = (multag[i] * x) % Mod;
  for (int i=l; i<=End[bel[l]]; ++i)
    if (!opt) a[i] = (a[i] + x) % Mod;
    else a[i] = (a[i] * x) % Mod;
  for (int i=beg[bel[r]]; i<=r; ++i)
    if (!opt) a[i] = (a[i] + x) % Mod;
    else a[i] = (a[i] * x) % Mod;
  return ;
}

int query(int x) {
  return (a[x] * multag[bel[x]] + addtag[bel[x]]) % Mod;
}

signed main() {
  init();
  while (n--) {
    int opt, L, R, x; read(opt);
    read(L), read(R), read(x);
    if (opt==2) printf("%lld\n", query(R));
    else upd(L, R, x, opt);
  }
  return 0;
}

比较纯粹的分块线段树等 DS 趣题

https://lbn233.github.io/2021/08/09/About-Duliu-DS/

Author

Xcel

Posted on

2021-08-09

Updated on

2021-09-04

Licensed under

#
Follow

Links

Categories

Recents

Archives

Tags

DS5
Graph1
Math1
Network Flows1
Number Theory2
Others2
State Compression1

Subscribe for updates

follow.it

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×

×