线段树

Posted on Edited on In

the easy xds code is follow: 

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
#include <cstdio>
#include <iostream>
#define int long long int
using namespace std;

const int N = 1e5+10;

int n, m;
int a[N], b[N<<2], d[N<<2];

inline void build (int s, int t, int p) {
   if (s == t) {d[p] = a[s]; return;}
   int m = (s+t)>>1;
   build (s, m, p<<1), build (m+1, t, (p<<1)|1);
   d[p] = d[p<<1] + d[(p<<1)|1];
}

inline void update (int l, int r, int c, int s, int t, int p) {
   if (l <= s && t <= r) {
      d[p] += (t-s+1)*c;
      b[p] += c;
      return;
   }
   int m = (s+t)>>1;
   if (b[p]) {
      d[p<<1] += (m-s+1)*b[p], d[(p<<1)|1] += (t-m)*b[p];
      b[p<<1] += b[p], b[(p<<1)|1] += b[p];
      b[p] = 0;
   }
   if (l <= m) update (l, r, c, s, m, p<<1);
   if (r > m) update (l, r, c, m+1, t, (p<<1)|1);
   d[p] = d[p<<1] + d[(p<<1)|1];
   return;
}

inline int getsum (int l, int r, int s, int t, int p) {
   if (l <= s && t <= r) return d[p];
   int m = (s+t)>>1, sum = 0;
   if (b[p]) {
      d[p<<1] += (m-s+1)*b[p], d[(p<<1)|1] += (t-m)*b[p];
      b[p<<1] += b[p], b[(p<<1)|1] += b[p];
      b[p] = 0;
   }
   if (l <= m) sum += getsum (l, r, s, m, p<<1);
   if (r > m) sum += getsum (l, r, m+1, t, (p<<1)|1);
   return sum;
}

main () {
   cin >> n >> m;
   for (int i =1 ; i <= n; ++i) cin >> a[i];
   build (1, n, 1);
   for (int i = 1; i <= m; ++ i) {
      int opt, x, y, k;
      cin >> opt >> x >> y;
      if (opt == 1) cin >> k, update (x, y, k, 1, n, 1);
      else cout << getsum (x, y, 1, n, 1) << '\n';
   }
   return 0;
}

and the code with the 'mul' is follow: 

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
#include <cstdio>
#include <iostream>
#define int long long int
using namespace std;

const int N = 1e5+10;

int n, m, mod;
int a[N], b[N<<2], d[N<<2], y[N<<2];

inline void pd (int p, int s, int t) {
   int l = p<<1, r = (p<<1)|1, m = (s+t)>>1;
   if (y[p] != 1) {
      y[l] *= y[p], y[r] *= y[p];
      b[l] *= y[p], b[r] *= y[p];
      d[l] *= y[p], d[r] *= y[p];
      y[l] %= mod, y[r] %= mod;
      b[l] %= mod, b[r] %= mod;
      d[l] %= mod, d[r] %= mod;
      y[p] = 1;
   }
   if (b[p] != 0) {
      d[l] += (m-s+1)*b[p], d[r] += (t-m)*b[p];
      b[l] += b[p], b[r] += b[p];
      d[l] %= mod, d[r] %= mod;
      b[l] %= mod, b[r] %= mod;
      b[p] = 0;
   }
   return;
}

inline void build (int s, int t, int p) {
   y[p] = 1;
   if (s == t) {d[p] = a[s]%mod; return;}
   int m = (s+t)>>1;
   build (s, m, p<<1), build (m+1, t, (p<<1)|1);
   d[p] = (d[p<<1] + d[(p<<1)|1])%mod;
}

inline void chenge (int l, int r, int c, int s, int t, int p) {
   if (l <= s && t <= r) {
      d[p] *= c, d[p] %= mod; 
      b[p] *= c, b[p] %= mod;
      y[p] *= c, y[p] %= mod;
      return;
   }
   int m = (s+t)>>1;
   pd (p, s, t);
   if (l <= m) chenge (l, r, c, s, m, p<<1);
   if (r > m) chenge (l, r, c, m+1, t, (p<<1)|1);
   d[p] = (d[p<<1] + d[(p<<1)|1])%mod;
}

inline void add (int l, int r, int c, int s, int t, int p) {
   if (l <= s && t <= r) {
      d[p] += (t-s+1)*c, d[p] %= mod;
      b[p] += c, b[p] %= mod;
      return;
   }
   int m = (s+t)>>1;
   pd (p, s, t);
   if (l <= m) add (l, r, c, s, m, p<<1);
   if (r > m) add (l, r, c, m+1, t, (p<<1)|1);
   d[p] = (d[p<<1] + d[(p<<1)|1])%mod;	
}

inline int getsum (int l, int r, int s, int t, int p) {
   if (l <= s && t <= r) return d[p]%mod;
   int m = (s+t)>>1, sum = 0;
   pd (p, s, t);
   if (l <= m) sum += getsum (l, r, s, m, p<<1)%mod;
   if (r > m) sum += getsum (l, r, m+1, t, (p<<1)|1)%mod;
   return sum;
}

main () {
   cin >> n >> m >> mod;
   for (int i = 1; i <= n; ++ i) cin >> a[i];
   build (1, n, 1);
   for (int i = 1; i <= m; ++ i) {
      int opt, x, y, k;
      cin >> opt >> x >> y;
      if (opt == 1) cin >> k, chenge (x, y, k, 1, n, 1);
      if (opt == 2) cin >> k, add (x, y, k, 1, n, 1);
      if (opt == 3) cout << getsum (x, y, 1, n, 1)%mod << '\n';
   }
   return 0;
}

the thought is easy

but there is some details

PS:

1.if must with the '\(return\)'

2.'<<' and '>>'

3.'update' and 'add' and 'chenge' need \(d[p] = d[p<<1] + d[(p<<1)|1]\)

4.\(y[p]\) need put on the first of the \(build\)

5.\(int\) && \(long long\)