洛谷数列分块入门全家桶题解
2026-02-03 20:39:48
发布于：上海
T1
题意解析：给定一个长度为
�
n 的数组
�
A，你需要进行
�
n 次操作。每次操作给定四个数
�
�
�
,
�
,
�
,
�
opt,l,r,c。
�
�
�
0
opt=0：请将
�
�
,
.
.
.
,
�
�
A
l
,...,A
r
的值加上
�
c。
�
�
�
1
opt=1：查询
�
�
A
r
的值。
考虑分块。
考虑转化成差分数组，
�
�
B
i
记录
�
�
−
�
�
−
1
A
i
−A
i−1
的值。这样操作
0
0 转化成将
�
�
B
l
加
�
c，
�
�
+
1
B
r+1
减
�
c；操作
1
1 转化成
∑
�
1
�
�
�
∑
j=1
r
B
j
。
我们将数组分成
�
(
�
)
O(
n
) 块，查询时我们可以分成两边的散块和中间的整块查询。
我们修改时
�
(
�
)
O(
n
) 暴力维护每一块的和（可以
�
(
1
)
O(1) 但是没必要），这样查询时中间每一个整块就可以
�
(
1
)
O(1) 了，又因为整块数量不超过
�
(
�
)
O(
n
)，所以查询整块就是
�
(
�
)
O(
n
) 的；散块直接
�
(
�
)
O(
n
) 暴力查即可。
namespace cjdst{
template <typename T>
class Block{
stdvector <T> a;
stdvector <T> block;
std::vector <int> belong, left, right;
int n, len;
public:
Block(){}
Block(int n, std::vector <T> &a){
this -> n = n;
len = sqrtl(n) + 1;
this -> a.resize(n + 5);
block.resize(n / len + 5);
belong.resize(n + 5);
left.resize(n / len + 5);
right.resize(n / len + 5);
for(int i = 1; i <= n; i++){
this -> a[i] = a[i];
belong[i] = (i - 1) / len + 1;
block[belong[i]] += a[i];
right[belong[i]] = i;
if(!left[belong[i]]) left[belong[i]] = i;
}
}
void modify(int idx, T val){
if(idx > n) return;
a[idx] += val;
int cur = belong[idx];
block[cur] = 0;
for(int i = left[cur]; i <= right[cur]; i++){
block[cur] += a[i];
}
}
T query(int l, int r){
T ans = 0;
if(belong[l] == belong[r]){
for(int i = l; i <= r; i++) ans += a[i];
return ans;
}
int curl = belong[l], curr = belong[r];
for(int i = l; i <= right[curl]; i++){
ans += a[i];
}
for(int i = curl + 1; i < curr; i++){
ans += block[i];
}
for(int i = left[curr]; i <= r; i++){
ans += a[i];
}
return ans;
}
};
}
时间复杂度：
�
(
�
�
)
O(n
n
)。
T4
题意解析：给定一个长度为
�
n 的数组
�
A，你需要进行
�
n 次操作。每次操作给定四个数
�
�
�
,
�
,
�
,
�
opt,l,r,c。
�
�
�
0
opt=0：请将
�
�
,
.
.
.
,
�
�
A
l
,...,A
r
的值加上
�
c。
�
�
�
1
opt=1：查询
(
∑
�
�
�
�
�
)
m
o
d
(
�
+
1
)
(∑
j=l
r
A
j
)mod(c+1) 的值。此时保证
�
≥
0
c≥0。
T1 加强版。
考虑分块。
我们修改的时候也可以分成整块和散块。
对于整块，我们可以直接修改该块的和并打上 lazytag，等到它要分成散块时再下放；对于散块，先下放 lazytag，然后暴力修改。
查询的时候整块依旧查和就行，散块就要先下放 lazytag 然后再暴力找
�
�
A
i
。
namespace cjdst{
template <typename T>
class Block{
stdvector <T> a;
stdvector <T> block;
stdvector <T> lazytag;
stdvector <int> belong, left, right;
int n, len;
void push_down(int idx){
for(int i = left[idx]; i <= right[idx]; i++){
a[i] += lazytag[idx];
}
lazytag[idx] = 0;
}
void push_up(int idx){
block[idx] = 0;
for(int i = left[idx]; i <= right[idx]; i++){
block[idx] += a[i];
}
}
public:
Block(){}
Block(int n, std::vector <T> &a){
this -> n = n;
len = sqrtl(n) + 1;
this -> a.resize(n + 5);
block.resize(n / len + 5);
lazytag.resize(n / len + 5);
belong.resize(n + 5);
left.resize(n / len + 5);
right.resize(n / len + 5);
for(int i = 1; i <= n; i++){
this -> a[i] = a[i];
belong[i] = (i - 1) / len + 1;
block[belong[i]] += a[i];
right[belong[i]] = i;
if(!left[belong[i]]) left[belong[i]] = i;
}
}
void modify(int l, int r, T val){
if(belong[l] == belong[r]){
push_down(belong[l]);
for(int i = l; i <= r; i++){
a[i] += val;
}
push_up(belong[l]);
return;
}
int curl = belong[l], curr = belong[r];
push_down(curl), push_down(curr);
for(int i = l; i <= right[curl]; i++){
a[i] += val;
}
for(int i = curl + 1; i < curr; i++){
block[i] += len * val;
lazytag[i] += val;
}
for(int i = left[curr]; i <= r; i++){
a[i] += val;
}
push_up(curl), push_up(curr);
}
T query(int l, int r){
T ans = 0;
if(belong[l] == belong[r]){
push_down(belong[l]);
for(int i = l; i <= r; i++) ans += a[i];
return ans;
}
int curl = belong[l], curr = belong[r];
push_down(curl), push_down(curr);
for(int i = l; i <= right[curl]; i++){
ans += a[i];
}
for(int i = curl + 1; i < curr; i++){
ans += block[i];
}
for(int i = left[curr]; i <= r; i++){
ans += a[i];
}
return ans;
}
};
}
T2
题意解析：给定一个长度为
�
n 的数组
�
A，你需要进行
�
n 次操作。每次操作给定四个数
�
�
�
,
�
,
�
,
�
opt,l,r,c。
�
�
�
0
opt=0：请将
�
�
,
.
.
.
,
�
�
A
l
,...,A
r
的值加上
�
c。
�
�
�
1
opt=1：查询在
�
�
,
.
.
.
,
�
�
A
l
,...,A
r
中，有多少个数小于
�
2
c
2
。
考虑分块。
先思考不带修改怎么做。
我们把
�
A 数组分为
�
(
�
)
O(
n
) 个块，我们将每个块内的元素从小到大排序。查询时我们对整块进行 lower_bound，两边的小块暴力查找即可。
�
(
�
�
log
�
)
O(n
n
logn)。
注意到修改整块对整块的顺序不影响，不需要重新排序，直接打 lazytag 即可，查询带 lazytag 查就行。散块先下放 lazytag（其实不下放也行），然后暴力修改
�
�
A
i
，最后 sort 排序即可。
注意查询的常数比修改的常数大很多，所以需要调整块长。经测试在块长为
250
250 时可以跑进
3.57
�
3.57s。
namespace cjdst{
template <typename T>
class Block{
stdvector <T> a;
stdvector <T> b;
stdvector <T> lazytag;
stdvector <int> belong, left, right;
int n, len;
void push_down(int idx){
for(int i = left[idx]; i <= right[idx]; i++){
a[i] += lazytag[idx];
}
lazytag[idx] = 0;
}
void push_up(int idx){
for(int i = left[idx]; i <= right[idx]; i++){
b[i] = a[i];
}
std::sort(b.begin() + left[idx], b.begin() + right[idx] + 1);
}
public:
Block(){}
Block(int n, std::vector <T> &a){
this -> n = n;
len = 250;
this -> a.resize(n + 5);
b.resize(n + 5);
lazytag.resize(n / len + 5);
belong.resize(n + 5);
left.resize(n / len + 5);
right.resize(n / len + 5);
for(int i = 1; i <= n; i++){
this -> a[i] = a[i];
b[i] = a[i];
belong[i] = (i - 1) / len + 1;
right[belong[i]] = i;
if(!left[belong[i]]) left[belong[i]] = i;
}
for(int i = 1; left[i]; i++){
std::sort(b.begin() + left[i], b.begin() + right[i] + 1);
}
}
void modify(int l, int r, T val){
if(belong[l] == belong[r]){
push_down(belong[l]);
for(int i = l; i <= r; i++){
a[i] += val;
}
push_up(belong[l]);
return;
}
int curl = belong[l], curr = belong[r];
push_down(curl), push_down(curr);
for(int i = l; i <= right[curl]; i++){
a[i] += val;
}
for(int i = curl + 1; i < curr; i++){
lazytag[i] += val;
}
for(int i = left[curr]; i <= r; i++){
a[i] += val;
}
push_up(curl), push_up(curr);
}
T query(int l, int r, T val){
T ans = 0;
if(belong[l] == belong[r]){
push_down(belong[l]);
push_up(belong[l]);
for(int i = l; i <= r; i++){
if(a[i] < val) ans++;
}
return ans;
}
int curl = belong[l], curr = belong[r];
push_down(curl), push_down(curr);
push_up(curl), push_up(curr);
for(int i = l; i <= right[curl]; i++){
if(a[i] < val) ans++;
}
for(int i = curl + 1; i < curr; i++){
int idx = lower_bound(b.begin() + left[i], b.begin() + right[i] + 1, val - lazytag[i]) - b.begin() - 1;
ans += idx - left[i] + 1;
}
for(int i = left[curr]; i <= r; i++){
if(a[i] < val) ans++;
}
return ans;
}
};
}
时间复杂度：
�
(
�
�
log
�
)
O(n
n
logn)。
Bonus：尝试以
�
(
�
�
log
�
)
O(n
nlogn
) 的时间复杂度通过该题。
T3
和 T2 差不多，不讲。代码见我的板子。
T5
题意解析：给定一个长度为
�
n 的数组
�
A，你需要进行
�
n 次操作。每次操作给定三个数
�
�
�
,
�
,
�
opt,l,r。
�
�
�
0
opt=0：请将
�
�
,
.
.
.
,
�
�
A
l
,...,A
r
的值都变为原先的值的根号。
�
�
�
1
opt=1：查询
(
∑
�
�
�
�
�
)
(∑
j=l
r
A
j
) 的值。
考虑分块。
首先我们注意到每个
�
�
A
i
被开
log
log
�
�
loglogA
i
次根就变为
1
1 了，所以其实能影响答案的单点改也就那么几次，后面的修改就相当于木棍木棍的中间两个字了。
思考如何判断某些修改是无效的。
显然对于一个块，
�
�
A
i
均小于等于
1
1，即
∑
�
�
�
�
�
≤
�
�
�
∑
j=l
r
A
i
≤len，那这个块的所有修改就都是无效的。我们遇到无效的修改就跳过，有效的就直接暴力修。显然，根据刚才的结论，每个块最多只会被修改
�
(
log
log
�
)
O(loglogV) 次。对于散块，那还说啥了，直接暴力即可。
查询时和 T1 一样查就行。
namespace cjdst{
template <typename T>
class Block{
stdvector <T> a;
stdvector <T> block;
std::vector <int> belong, left, right;
int n, len;
void push_up(int idx){
block[idx] = 0;
for(int i = left[idx]; i <= right[idx]; i++){
block[idx] += a[i];
}
}
public:
Block(){}
Block(int n, std::vector <T> &a){
this -> n = n;
len = sqrtl(n) + 1;
this -> a.resize(n + 5);
block.resize(n / len + 5);
belong.resize(n + 5);
left.resize(n / len + 5);
right.resize(n / len + 5);
for(int i = 1; i <= n; i++){
this -> a[i] = a[i];
belong[i] = (i - 1) / len + 1;
block[belong[i]] += a[i];
right[belong[i]] = i;
if(!left[belong[i]]) left[belong[i]] = i;
}
}
void modify(int l, int r){
if(belong[l] == belong[r]){
for(int i = l; i <= r; i++){
a[i] = sqrtl(a[i]);
}
push_up(belong[l]);
return;
}
int curl = belong[l], curr = belong[r];
for(int i = l; i <= right[curl]; i++){
a[i] = sqrtl(a[i]);
}
for(int i = curl + 1; i < curr; i++){
if(block[i] <= len) continue;// 何意味
for(int j = left[i]; j <= right[i]; j++){
a[j] = sqrtl(a[j]);
}
push_up(i);
}
for(int i = left[curr]; i <= r; i++){
a[i] = sqrtl(a[i]);
}
push_up(curl), push_up(curr);
}
T query(int l, int r){
T ans = 0;
if(belong[l] == belong[r]){
for(int i = l; i <= r; i++){
ans += a[i];
}
return ans;
}
int curl = belong[l], curr = belong[r];
for(int i = l; i <= right[curl]; i++){
ans += a[i];
}
for(int i = curl + 1; i < curr; i++){
ans += block[i];
}
for(int i = left[curr]; i <= r; i++){
ans += a[i];
}
return ans;
}
};
}
时间复杂度：
�
(
�
�
+
�
log
log
�
)
O(n
n
+nloglogV)。
T6
题意解析：给定一个初始长度为
�
n 的数组
�
A，你需要进行
�
n 次操作。每次操作给定？个数
�
�
�
,
.
.
.
opt,...。
�
�
�
0
opt=0：给定三个数
�
�
�
,
�
,
�
opt,l,r，请在
�
�
A
l
前面插入一个数
�
r。
�
�
�
1
opt=1：给定两个数
�
�
�
,
�
opt,c，查询
�
�
A
c
的值。
数据随机生成。
考虑分块。
我们把
�
A 数组分成
�
(
�
)
O(
n
) 块，每块是一个 vector，记录块内的元素。修改先找大块，如果
�
�
A
l
位于这个块，就直接 insert；不在的话继续往下找。查询和插入同理。由于数据随机生成，所以这种做法每个块期望长度依然是
�
(
�
)
O(
n
)，时间复杂度也是
�
(
�
�
)
O(n
n
)。
但是，注意到如果块长占比过大，那么随机选点落到它的概率就更大，这样它的块长也更大……所以，为了减少这种恶性循环的危害，建议将块长调小一点。
namespace cjdst{
template <typename T>
class Block{
stdvector <stdvector <T>> a;
stdvector <T> lazytag;
stdvector <int> belong, left, right;
int n, len;
public:
Block(){}
Block(int n, std::vector <T> a){
this -> n = n;
len = 0.3 * sqrtl(n) + 1;
this -> a.resize(n / len + 5);
belong.resize(n + 5);
left.resize(n / len + 5);
right.resize(n / len + 5);
for(int i = 1; i <= n; i++){
belong[i] = (i - 1) / len + 1;
right[belong[i]] = i;
if(!left[belong[i]]) left[belong[i]] = i;
}
for(int i = 1; left[i]; i++){
for(int j = left[i]; j <= right[i]; j++){
this -> a[i].push_back(a[j]);
}
}
}
void insert(int idx, T val){
int cur = 0;
for(int i = 1; left[i]; i++){
if(int(cur + a[i].size()) < idx){
cur += a[i].size();
continue;
}
a[i].insert(a[i].begin() + idx - cur - 1, val);
return;
}
}
T query(int idx){
int cur = 0;
for(int i = 1; left[i]; i++){
if(int(cur + a[i].size()) < idx){
cur += a[i].size();
continue;
}
return a[i][idx - cur - 1];
}
return -1;
}
};
}
时间复杂度：
�
(
�
�
)
O(n
n
)。
T7
和 T4 一样，不写。
T8
题意解析：给定一个长度为
�
n 的数组
�
A，你需要进行
�
n 次操作。每次操作给定三个数
�
,
�
,
�
l,r,c。
请查询
�
�
,
.
.
.
,
�
�
A
l
,...,A
r
内一个数内元素为
�
c 的个数，并将区间所有元素改为
�
c。
考虑分块。
我们把
�
A 数组分成
�
n
个块，设置 lazytag 为当前块内所有元素为一个相同的值
�
k（如果不同则
�
−
1
k=−1），这样如果遇到
�
≠
−
1
k
=−1 的块就可以直接改 lazytag 了，否则就暴力。显然这样如果不算一开始的元素的话，单次操作是
�
(
�
)
O(
n
) 的。而一开始的元素也只会查询
�
(
�
)
O(n) 次，所以总时间复杂度还是
�
(
�
�
)
O(n
n
)。
namespace cjdst{
template <typename T>
class Block{
stdvector <T> a;
stdvector <T> lazytag;
std::vector <int> belong, left, right;
int n, len;
void push_down(int idx){
if(lazytag[idx] == -1) return;
for(int i = left[idx]; i <= right[idx]; i++){
a[i] = lazytag[idx];
}
lazytag[idx] = -1;
}
public:
Block(){}
Block(int n, std::vector <T> a){
this -> n = n;
len = sqrtl(n) + 1;
this -> a.resize(n + 5);
lazytag.resize(n / len + 5, -1);
belong.resize(n + 5);
left.resize(n / len + 5);
right.resize(n / len + 5);
for(int i = 1; i <= n; i++){
this -> a[i] = a[i];
belong[i] = (i - 1) / len + 1;
right[belong[i]] = i;
if(!left[belong[i]]) left[belong[i]] = i;
}
}
int query(int l, int r, T val){
int ans = 0;
if(belong[l] == belong[r]){
push_down(belong[l]);
for(int i = l; i <= r; i++){
if(a[i] == val) ans++;
a[i] = val;
}
return ans;
}
int curl = belong[l], curr = belong[r];
push_down(curl), push_down(curr);
for(int i = l; i <= right[curl]; i++){
if(a[i] == val) ans++;
a[i] = val;
}
for(int i = curl + 1; i < curr; i++){
if(lazytag[i] != -1){
if(lazytag[i] == val) ans += len;
lazytag[i] = val;
continue;
}
for(int j = left[i]; j <= right[i]; j++){
if(a[j] == val) ans++;
a[j] = val;
}
lazytag[i] = val;
}
for(int i = left[curr]; i <= r; i++){
if(a[i] == val) ans++;
a[i] = val;
}
return ans;
}
};
}
时间复杂度：
�
(
�
�
)
O(n
n
)。
T9
题意解析：给定一个长度为
�
n 的数组
�
A，你需要进行
�
n 次操作。每次操作给定两个数
�
,
�
l,r。
请查询
�
�
,
.
.
.
,
�
�
A
l
,...,A
r
中的最小众数。
考虑分块。
首先我们可以
�
(
�
)
O(n) 递推求出
[
�
,
�
]
,
[
�
,
�
+
1
]
,
[
�
,
�
+
2
]
,
.
.
.
,
[
�
,
�
]
[i,i],[i,i+1],[i,i+2],...,[i,n] 的最小众数。所以我们可以
�
(
�
�
)
O(n
n
) 求出
[
�
,
�
]
[
n
,
n
]，
[
�
,
2
�
]
,
[
�
,
3
�
]
,
.
.
.
,
[
�
,
�
]
,
[
2
�
,
2
�
]
,
[
2
�
,
3
�
]
,
.
.
.
,
[
�
,
�
]
[
n
,2
n
],[
n
,3
n
],...,[
n
,n],[2
n
,2
n
],[2
n
,3
n
],...,[n,n] 的最小众数。记录下来。
然后我们
�
(
�
�
)
O(n
n
) 预处理每个块每个元素的个数，然后做前缀和。
每一个查询还是分成整块和散块。整块的话直接查表。
我们枚举散块的每一个元素，显然不超过
2
�
2
n
个。我们可以通过查表找到整块内它们出现的个数，然后暴力统计散块内出现的个数，更新答案。
namespace cjdst{
template <typename T>
class Block{
stdvector <T> a;
stdvector <stdvector <T>> bucket;
stdvector <T> tmpbucket;
stdvector <stdvector <T>> block;
std::vector <int> belong, left, right;
int n, len;
public:
Block(){}
Block(int n, std::vector <T> a){
this -> n = n;
len = 1500;
this -> a.resize(n + 5);
block.resize(n / len + 5, std::vector <T>(n / len + 5));
bucket.resize(n / len + 5, std::vector <T>(n + 5));
tmpbucket.resize(n + 5);
belong.resize(n + 5);
left.resize(n / len + 5);
right.resize(n / len + 5);
for(int i = 1; i <= n; i++){
this -> a[i] = a[i];
belong[i] = (i - 1) / len + 1;
bucket[belong[i]][a[i]]++;
right[belong[i]] = i;
if(!left[belong[i]]){
for(int j = 1; j <= n; j++){
bucket[belong[i]][j] += bucket[belong[i - 1]][j];
}
left[belong[i]] = i;
}
}
for(int i = 1; left[i]; i++){
std::vector <int> b(n + 5, 0);
T cur = -1;
for(int j = i; left[j]; j++){
for(int k = left[j]; k <= right[j]; k++){
b[a[k]]++;
if(cur == -1 || b[a[k]] > b[cur] || (b[a[k]] == b[cur] && a[k] < cur)) cur = a[k];
}
block[i][j] = cur;
}
}
}
T query(int l, int r){
T ans = -1;
if(belong[r] - belong[l] <= 1){
for(int i = l; i <= r; i++){
tmpbucket[a[i]]++;
if(ans == -1 || tmpbucket[ans] < tmpbucket[a[i]] || (tmpbucket[ans] == tmpbucket[a[i]] && ans > a[i])) ans = a[i];
}
for(int i = l; i <= r; i++){
tmpbucket[a[i]]--;
}
return ans;
}
int curl = belong[l], curr = belong[r];
ans = block[curl + 1][curr - 1];
for(int i = l; i <= right[curl]; i++){
tmpbucket[a[i]]++;
}
for(int i = left[curr]; i <= r; i++){
tmpbucket[a[i]]++;
}
for(int i = l; i <= right[curl]; i++){
int times1 = tmpbucket[a[i]] + bucket[curr - 1][a[i]] - bucket[curl][a[i]];
int times2 = tmpbucket[ans] + bucket[curr - 1][ans] - bucket[curl][ans];
if(times1 > times2 || (times1 == times2 && ans > a[i])){
ans = a[i];
}
}
for(int i = left[curr]; i <= r; i++){
int times1 = tmpbucket[a[i]] + bucket[curr - 1][a[i]] - bucket[curl][a[i]];
int times2 = tmpbucket[ans] + bucket[curr - 1][ans] - bucket[curl][ans];
if(times1 > times2 || (times1 == times2 && ans > a[i])){
ans = a[i];
}
}
for(int i = l; i <= right[curl]; i++){
tmpbucket[a[i]]--;
}
for(int i = left[curr]; i <= r; i++){
tmpbucket[a[i]]--;
}
return ans;
}
void test(std::vector <T> &b){
for(int i = 1; left[i]; i++){
for(int j = 1; left[j]; j++){
std::cout << i << ' ' << j << ' ' << b[block[i][j]] << '\n';
}
}
std::cout.flush();
}
};
}
这里空空如也
有帮助，赞一个