对于需要使用线段树的题来说，最关键的是需要考虑值和值，标记和标记，标记和值之间的关系。

interval GCD

传送门：interval GCD

题意：给了一个长度为NN的序列，有两种操作，一个是区间内每个数加上dd，另一个是查询区间gcdgcd。

思路：gcdgcd有一个性质，gcd(a,b)=gcd(a−b,b)gcd(a,b)=gcd(a-b,b)，由此可以得出gcd(a[l],a[l+1],...,a[r])=gcd(a[l],a[l+1]−a[l],...,a[r]−a[r−1])gcd(a[l],a[l+1],...,a[r])=gcd(a[l],a[l+1]-a[l],...,a[r]-a[r-1])。因此我们需要维护一个关于aa的差分数组bb。对于区间修改我们只需要单点修改b[l]=b[l]+db[l]=b[l]+d，b[r+1]=b[r+1]−db[r+1]=b[r+1]-d。那么最终答案就是gcd(∑p=1lb[p],b[l+1],b[l+2],...,b[r])gcd(\sum_{p=1}^{l}b[p], b[l+1],b[l+2],...,b[r])，其中∑p=1lb[p]=a[l]\sum_{p=1}^{l}b[p]=a[l]。所以我们要维护两个数组，一个是差分数组bb的gcdgcd，另一个是数组aa的值。

代码：

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
#include <bits/stdc++.h>
#define ls k << 1
#define rs k << 1 | 1
#define lson k << 1, l, mid
#define rson k << 1 | 1, mid + 1, r
using namespace std;

const int MAX = 5e5 + 5;
struct Node {
  int l, r;
  long long dif, gcd;
} tree[MAX << 2];
long long a[MAX];
int N, M;

void pushup(int k) {
  tree[k].dif = tree[ls].dif + tree[rs].dif;
  tree[k].gcd = __gcd(tree[ls].gcd, tree[rs].gcd);
}

void build(int k, int l, int r) {
  tree[k].l = l; tree[k].r = r;
  if (l == r) {
    tree[k].dif = a[l] - a[l - 1];
    tree[k].gcd = a[l] - a[l - 1];
    return;
  }
  int mid = (l + r) >> 1;
  build(lson);
  build(rson);
  pushup(k);
}

void modify(int k, int x, long long y) {
  if (tree[k].l == tree[k].r) {
    tree[k].dif += y;
    tree[k].gcd += y;
    return;
  }
  int mid = (tree[k].l + tree[k].r) >> 1;
  if (x <= mid) modify(ls, x, y);
  else modify(rs, x, y);
  pushup(k);
}

long long queryA(int k, int l, int r) {
  if (l > r) return 0;
  if (tree[k].l == l && tree[k].r == r) {
    return tree[k].dif;
  }
  int mid = (tree[k].l + tree[k].r) >> 1;
  if (r <= mid) return queryA(ls, l, r);
  else if (l > mid) return queryA(rs, l, r);
  else return queryA(lson) + queryA(rson);
}

long long queryB(int k, int l, int r) {
  if (l > r) return 0;
  if (tree[k].l == l && tree[k].r == r) {
    return tree[k].gcd;
  }
  int mid = (tree[k].l + tree[k].r) >> 1;
  if (r <= mid) return queryB(ls, l, r);
  else if (l > mid) return queryB(rs, l, r);
  else return __gcd(queryB(lson), queryB(rson));
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> N >> M;
  for (int i = 1; i <= N; i++) {
    cin >> a[i];
  }
  build(1, 1, N);
  while (M--) {
    string opt;
    int l, r;
    cin >> opt >> l >> r;
    if (opt == "C") {
      long long d;
      cin >> d;
      modify(1, l, d);
      if (r < N) modify(1, r + 1, -d);
    } else {
      cout << abs(__gcd(queryA(1, 1, l), queryB(1, l + 1, r))) << "\n";
    }
  }
  return 0;
}

区间加区间sin和

传送门：区间加区间sin和

题意：给了一个序列，有两种操作，一个是区间内每个数加上一个值，另一个是询问区间sin(a[i])sin(a[i])的和。

思路：利用高中三角函数的和差化积公式，对于某一个a[i]a[i]来说，sin⁡(a[i]+v)=sin⁡(a[i])∗cos⁡(v)+cos⁡(a[i])∗sin(v)\sin(a[i]+v)=\sin(a[i])*\cos(v)+\cos(a[i])*sin(v)，对于区间[l,r][l, r]来说，∑i=lrsin⁡(a[i]+v)=∑i=lrsin⁡(a[i])∗cos⁡(v)+∑i=lrcos⁡(a[i])∗sin(v)=cos⁡(v)∗∑i=lrsin(a[i])+sin⁡(v)∗∑i=lrcos⁡(a[i])\sum_{i=l}^{r}\sin(a[i]+v)=\sum_{i=l}^{r}\sin(a[i])*\cos(v)+\sum_{i=l}^{r}\cos(a[i])*sin(v)=\cos(v)*\sum_{i=l}^{r}sin(a[i])+\sin(v)*\sum_{i=l}^{r}\cos(a[i])。也就是说我们只要维护区间sinsin和区间coscos的和就能得到新的区间sinsin和，同样的，我们还需要维护区间coscos和，∑i=lrcos⁡(a[i]+v)=∑i=lrcos⁡(a[i])∗cos⁡(v)−∑i=lrsin⁡(a[i])∗sin(v)=cos⁡(v)∗∑i=lrcos(a[i])−sin⁡(v)∗∑i=lrsin⁡(a[i])\sum_{i=l}^{r}\cos(a[i]+v)=\sum_{i=l}^{r}\cos(a[i])*\cos(v)-\sum_{i=l}^{r}\sin(a[i])*sin(v)=\cos(v)*\sum_{i=l}^{r}cos(a[i])-\sin(v)*\sum_{i=l}^{r}\sin(a[i])。

代码：

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>
#define ls k << 1
#define rs k << 1 | 1
#define lson k << 1, l, mid
#define rson k << 1 | 1, mid + 1, r
using namespace std;

const int MAX = 2e5 + 5;
struct Node {
  int l, r;
  double sinx, cosx;
  long long lazy;
} tree[MAX << 2];
int a[MAX], n, m;

void pushdown(int k) {
  if (!tree[k].lazy) return;
  long long v = tree[k].lazy;
  double sinx = tree[ls].sinx;
  double cosx = tree[ls].cosx;
  tree[ls].sinx = cos(v) * sinx + sin(v) * cosx;
  tree[ls].cosx = cos(v) * cosx - sin(v) * sinx;
  tree[ls].lazy += v;
  sinx = tree[rs].sinx;
  cosx = tree[rs].cosx;
  tree[rs].sinx = cos(v) * sinx + sin(v) * cosx;
  tree[rs].cosx = cos(v) * cosx - sin(v) * sinx;
  tree[rs].lazy += v;
  tree[k].lazy = 0;
}

void pushup(int k) {
  tree[k].sinx = tree[ls].sinx + tree[rs].sinx;
  tree[k].cosx = tree[ls].cosx + tree[rs].cosx;
}

void build(int k, int l, int r) {
  tree[k].l = l; tree[k].r = r;
  tree[k].lazy = 0;
  if (l == r) {
    tree[k].sinx = sin(a[l]);
    tree[k].cosx = cos(a[l]);
    return;
  }
  int mid = (l + r) >> 1;
  build(lson);
  build(rson);
  pushup(k);
}

void modify(int k, int l, int r, int v) {
  if (tree[k].l == l && tree[k].r == r) {
    double sinx = tree[k].sinx;
    double cosx = tree[k].cosx;
    tree[k].sinx = cos(v) * sinx + sin(v) * cosx;
    tree[k].cosx = cos(v) * cosx - sin(v) * sinx;
    tree[k].lazy += v;
    return;
  }
  pushdown(k);
  int mid = (tree[k].l + tree[k].r) >> 1;
  if (r <= mid) modify(ls, l, r, v);
  else if (l > mid) modify(rs, l, r, v);
  else modify(lson, v), modify(rson, v);
  pushup(k);
}

double query(int k, int l, int r) {
  if (tree[k].l == l && tree[k].r == r) {
    return tree[k].sinx;
  }
  pushdown(k);
  int mid = (tree[k].l + tree[k].r) >> 1;
  if (r <= mid) return query(ls, l, r);
  else if (l > mid) return query(rs, l, r);
  else return query(lson) + query(rson);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << fixed << setprecision(1);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  build(1, 1, n);
  cin >> m;
  while (m--) {
    int op, l, r;
    cin >> op >> l >> r;
    if (op == 1) {
      int v;
      cin >> v;
      modify(1, l, r, v);
    } else {
      cout << query(1, l, r) << "\n";
    }
  }
  return 0;
}

rgxsxrs

传送门：rgxsxrs

题意：有一个序列，以及两种操作，一个是给定区间将区间内所有大于xx的元素减去xx，另一个是询问区间内的和、最小值、最大值。

思路：先考虑一种暴力，将元素存到线段树，对于大于xx的节点暴力修改，如果区间最大值不超过xx，直接返回。对于这种方法，如果所有数都很大，但xx又很小，那么每次都得要暴力到叶子节点，这种暴力是肯定会超时的。

优化一：值域分块。我们考虑对值域进行分块，每块用线段树维护权值在[Bi,Bi+1)[B^i, B^{i+1})区间内的值，对于修改操作，跟上面的暴力差不多，只不过这次需要注意将区间内减去xx后，比该块的值域要小的值需要将他重新插入到其他块中。对于一个数，它在每个权值块中只会被暴力（删除和插入操作）一次，他最多被暴力log⁡Bai\log_{B}{a_i}次，每次需要log⁡2n\log_{2}{n}的复杂度，所以这里的复杂度是O(nlog⁡Bailog⁡2n)O(n\log_{B}{a_i}\log_{2}{n})。

优化二：线段树底层分块。因为这题的空间给的很小，如果只用上面这种值域分块会MLE。我们可以对线段树底层进行优化，也就是说，如果线段树的节点表示的区间大小小于某个值的时候，我们直接进行暴力，在aa数组上修改，这样能大大减少线段树的节点个数，通过时间换取空间。

对于这两个优化的阈值都需要取得比较恰当才能过通过。

代码：

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
#include <bits/stdc++.h>
#define ls k << 1
#define rs k << 1 | 1
#define lson k << 1, l, mid
#define rson k << 1 | 1, mid + 1, r
using namespace std;

const int MOD = 1 << 20;
const int MAXN = 5e5 + 5;
const int MAXM = 1e5 + 5;
const int B1 = 16;  // 值域分块[16^0, 16^1), [16^1, 16^2), [16^2, 16^3) ...
const int B2 = 20;  // 线段树底层分块大小
struct Node {
  bool flag;
  int l, r, minv, maxv, cnt, lazy;
  long long sum;
} tree[9][MAXM];
int L[10], R[10];
int a[MAXN], belong[MAXN], n, m;

void pushup(int rt, int k) {
  tree[rt][k].minv = min(tree[rt][ls].minv, tree[rt][rs].minv);
  tree[rt][k].maxv = max(tree[rt][ls].maxv, tree[rt][rs].maxv);
  tree[rt][k].sum = tree[rt][ls].sum + tree[rt][rs].sum;
  tree[rt][k].cnt = tree[rt][ls].cnt + tree[rt][rs].cnt;
}

void pushdown(int rt, int k) {
  if (!tree[rt][k].lazy) return;
  if (tree[rt][k].flag) {
    for (int i = tree[rt][k].l; i <= tree[rt][k].r; i++) {
      if (belong[i] == rt) {
        a[i] -= tree[rt][k].lazy;
      }
    }
  } else {
    if (tree[rt][ls].cnt) {
      tree[rt][ls].minv -= tree[rt][k].lazy;
      tree[rt][ls].maxv -= tree[rt][k].lazy;
      tree[rt][ls].sum -= (long long) tree[rt][k].lazy * tree[rt][ls].cnt;
      tree[rt][ls].lazy += tree[rt][k].lazy;
    }
    if (tree[rt][rs].cnt) {
      tree[rt][rs].minv -= tree[rt][k].lazy;
      tree[rt][rs].maxv -= tree[rt][k].lazy;
      tree[rt][rs].sum -= (long long) tree[rt][k].lazy * tree[rt][rs].cnt;
      tree[rt][rs].lazy += tree[rt][k].lazy;
    }
  }
  tree[rt][k].lazy = 0;
}

void build(int rt, int k, int l, int r) {
  tree[rt][k].l = l;
  tree[rt][k].r = r;
  tree[rt][k].minv = INT_MAX;
  tree[rt][k].maxv = INT_MIN;
  tree[rt][k].sum = 0;
  tree[rt][k].cnt = 0;
  tree[rt][k].lazy = 0;
  tree[rt][k].flag = false;
  if (r - l + 1 <= B2) {
    tree[rt][k].flag = true;  // 是否是的底层标记
    for (int i = l; i <= r; i++) {
      if (L[rt] <= a[i] && a[i] <= R[rt]) {
        belong[i] = rt;  // 该点属于哪一块值域
        tree[rt][k].minv = min(tree[rt][k].minv, a[i]);
        tree[rt][k].maxv = max(tree[rt][k].maxv, a[i]);
        tree[rt][k].sum += a[i];
        tree[rt][k].cnt++;
      }
    }
    return;
  }
  int mid = (l + r) >> 1;
  build(rt, lson);
  build(rt, rson);
  pushup(rt, k);
}

void insert(int rt, int k, int x) {
  pushdown(rt, k);
  if (tree[rt][k].flag) {
    belong[x] = rt;
    tree[rt][k].minv = min(tree[rt][k].minv, a[x]);
    tree[rt][k].maxv = max(tree[rt][k].maxv, a[x]);
    tree[rt][k].sum += a[x];
    tree[rt][k].cnt++;
    return;
  }
  int mid = (tree[rt][k].l + tree[rt][k].r) >> 1;
  if (x <= mid) insert(rt, ls, x);
  else insert(rt, rs, x);
  pushup(rt, k);
}

void del(int rt, int k) {
  if (tree[rt][k].minv >= L[rt]) return;
  pushdown(rt, k);
  if (tree[rt][k].flag) {
    for (int i = tree[rt][k].l; i <= tree[rt][k].r; i++) {
      if (belong[i] == rt && a[i] < L[rt]) {
        tree[rt][k].sum -= a[i];
        tree[rt][k].cnt--;
        // 计算新的值域下标
        int newRt = upper_bound(L, L + 9, a[i]) - L - 1;
        insert(newRt, 1, i);
      }
    }
    // 重新计算区间最大最小值
    tree[rt][k].minv = INT_MAX;
    tree[rt][k].maxv = INT_MIN;
    for (int i = tree[rt][k].l; i <= tree[rt][k].r; i++) {
      if (belong[i] == rt) {
        tree[rt][k].minv = min(tree[rt][k].minv, a[i]);
        tree[rt][k].maxv = max(tree[rt][k].maxv, a[i]);
      }
    }
    return;
  }
  int mid = (tree[rt][k].l + tree[rt][k].r) >> 1;
  del(rt, ls);
  del(rt, rs);
  pushup(rt, k);
}

void modify(int rt, int k, int l, int r, int x) {
  if (tree[rt][k].maxv <= x) return;
  if (tree[rt][k].l > r || tree[rt][k].r < l) return;
  if (l <= tree[rt][k].l && tree[rt][k].r <= r && tree[rt][k].minv > x) {
    // 区间内最小值 > x,直接打上标记
    tree[rt][k].minv -= x;
    tree[rt][k].maxv -= x;
    tree[rt][k].sum -= (long long) x * tree[rt][k].cnt;
    tree[rt][k].lazy += x;
    return;
  }
  pushdown(rt, k);
  if (tree[rt][k].flag) {
    // 对底层的暴力修改
    for (int i = max(tree[rt][k].l, l); i <= min(tree[rt][k].r, r); i++) {
      if (belong[i] == rt && a[i] > x) {
        a[i] -= x;
        tree[rt][k].sum -= x;
      }
    }
    tree[rt][k].minv = INT_MAX;
    tree[rt][k].maxv = INT_MIN;
    for (int i = tree[rt][k].l; i <= tree[rt][k].r; i++) {
      if (belong[i] == rt) {
        tree[rt][k].minv = min(tree[rt][k].minv, a[i]);
        tree[rt][k].maxv = max(tree[rt][k].maxv, a[i]);
      }
    }
    return;
  }
  int mid = (tree[rt][k].l + tree[rt][k].r) >> 1;
  modify(rt, ls, l, r, x);
  modify(rt, rs, l, r, x);
  pushup(rt, k);
}

void query(int rt, int k, int l, int r, int& minv, int& maxv, long long& sum) {
  if (tree[rt][k].l > r || tree[rt][k].r < l) return;
  if (l <= tree[rt][k].l && tree[rt][k].r <= r) {
    minv = min(minv, tree[rt][k].minv);
    maxv = max(maxv, tree[rt][k].maxv);
    sum += tree[rt][k].sum;
    return;
  }
  pushdown(rt, k);
  if (tree[rt][k].flag) {
    for (int i = max(tree[rt][k].l, l); i <= min(tree[rt][k].r, r); i++) {
      if (belong[i] == rt) {
        minv = min(minv, a[i]);
        maxv = max(maxv, a[i]);
        sum += a[i];
      }
    }
    return;
  }
  int mid = (tree[rt][k].l + tree[rt][k].r) >> 1;
  query(rt, ls, l, r, minv, maxv, sum);
  query(rt, rs, l, r, minv, maxv, sum);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  // 预处理每一块的值域
  for (int i = 1; i <= 8; i++) {
    L[i] = R[i - 1] + 1;
    if (i < 8) {
      R[i] = L[i] * B1 - 1;
    } else {
      R[i] = INT_MAX;
    }
  }
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  // 初始化所有值域的线段树
  for (int i = 1; i <= 8; i++) {
    build(i, 1, 1, n);
  }
  int lastans = 0;
  while (m--) {
    int op, l, r;
    cin >> op >> l >> r;
    l ^= lastans;
    r ^= lastans;
    if (op == 1) {
      int x;
      cin >> x;
      x ^= lastans;
      for (int i = 1; i <= 8; i++) {
        // 每次修改完后就去删点
        modify(i, 1, l, r, x);
        del(i, 1);
      }
    } else {
      int minv = INT_MAX, maxv = 0;
      long long sum = 0;
      for (int i = 1; i <= 8; i++) {
        query(i, 1, l, r, minv, maxv, sum);
      }
      cout << sum << " " << minv << " " << maxv << "\n";
      lastans = int(sum % MOD);
    }
  }
  return 0;
}