给定一个序列,要求兹滋: 区间加数、区间除以数、区间求和、区间求最小值。

其他都很简单,关键在于怎么解决区间除法。

一开始很容易想到之前的 “花神游历各国” ,但是这题并不能这样做(有区间加数),感觉线段树不可做想分块然而分块照样没法解决除法的问题。

正解则是将除法转换为减法,如果当前区间的最大值和最小值与除以除数的数的差值相同,那么把除数变成减数。

复杂度为 $O(n \log^2 n)$ 据称可以用势能分析,但是本蒟蒻太菜了不会,因此略过 QAQ。

代码:

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
// ==============================
// author: memset0
// website: https://memset0.cn
// ==============================
#include <bits/stdc++.h>
#define ll long long

int read() {
int x = 0; bool m = 0; char c = getchar();
while (!isdigit(c) && c != '-') c = getchar();
if (c == '-') m = 1, c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
if (m) return -x; else return x;
}

const int maxn = 100010;

int n, m, l, r, x, opt;
int a[maxn];

struct seg_node {
int l, r, mid;
ll sum, min, max, tag;
} p[maxn << 2];

inline ll divide(ll a, ll b) {
if (a >= 0) return a / b;
return (a - b + 1) / b;
}

inline void update(int u) {
p[u].sum = p[u << 1].sum + p[u << 1 | 1].sum;
p[u].max = std::max(p[u << 1].max, p[u << 1 | 1].max);
p[u].min = std::min(p[u << 1].min, p[u << 1 | 1].min);
}

inline void pushup(int u, ll x) {
p[u].tag += x, p[u].min += x, p[u].max += x;
p[u].sum += x * (p[u].r - p[u].l + 1);
}

inline void pushdown(int u) {
if (p[u].tag) {
if (p[u].l ^ p[u].r) {
pushup(u << 1, p[u].tag);
pushup(u << 1 | 1, p[u].tag);
}
p[u].tag = 0;
}
}

void build(int u, int l, int r) {
p[u].l = l, p[u].r = r, p[u].mid = (l + r) >> 1;
if (l == r) { p[u].sum = p[u].min = p[u].max = a[l]; return; }
build(u << 1, l, p[u].mid);
build(u << 1 | 1, p[u].mid + 1, r);
update(u);
}

void modify_sum(int u, int l, int r, ll x) {
pushdown(u);
if (p[u].l == l && p[u].r == r) { pushup(u, x); return; }
if (r <= p[u].mid) modify_sum(u << 1, l, r, x);
else if (l > p[u].mid) modify_sum(u << 1 | 1, l, r, x);
else modify_sum(u << 1, l, p[u].mid, x), modify_sum(u << 1 | 1, p[u].mid + 1, r, x);
update(u);
}

void modify_div(int u, int l, int r, ll x) {
pushdown(u);
if ((!p[u].min || !~p[u].min) && (!p[u].max || !~p[u].max)) return;
if (p[u].l == l && p[u].r == r) {
int new_min = divide(p[u].min, x), new_max = divide(p[u].max, x);
if (p[u].min - new_min == p[u].max - new_max) {
pushup(u, new_min - p[u].min);
return;
}
}
if (r <= p[u].mid) modify_div(u << 1, l, r, x);
else if (l > p[u].mid) modify_div(u << 1 | 1, l, r, x);
else modify_div(u << 1, l, p[u].mid, x), modify_div(u << 1 | 1, p[u].mid + 1, r, x);
update(u);
}

ll query_sum(int u, int l, int r) {
pushdown(u);
if (p[u].l == l && p[u].r == r) return p[u].sum;
if (r <= p[u].mid) return query_sum(u << 1, l, r);
else if (l > p[u].mid) return query_sum(u << 1 | 1, l, r);
else return query_sum(u << 1, l, p[u].mid) + query_sum(u << 1 | 1, p[u].mid + 1, r);
}

ll query_min(int u, int l, int r) {
pushdown(u);
if (p[u].l == l && p[u].r == r) return p[u].min;
if (r <= p[u].mid) return query_min(u << 1, l, r);
else if (l > p[u].mid) return query_min(u << 1 | 1, l, r);
else return std::min(query_min(u << 1, l, p[u].mid), query_min(u << 1 | 1, p[u].mid + 1, r));
}

int main() {
n = read(), m = read();
for (int i = 1; i <= n; i++)
a[i] = read();
build(1, 1, n);
for (int i = 1; i <= m; i++) {
opt = read();
if (opt == 1) {
l = read() + 1, r = read() + 1, x = read();
modify_sum(1, l, r, x);
} else if (opt == 2) {
l = read() + 1, r = read() + 1, x = read();
modify_div(1, l, r, x);
} else if (opt == 3) {
l = read() + 1, r = read() + 1;
printf("%lld\n", query_min(1, l, r));
} else {
l = read() + 1, r = read() + 1;
printf("%lld\n", query_sum(1, l, r));
}
}
return 0;
}