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;
}
时间复杂度：
�
(
�
�
)
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;
}
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;
}
时间复杂度：
�
(
�
�
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;
}
时间复杂度：
�
(
�
�
+
�
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;
}
时间复杂度：
�
(
�
�
)
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;
}
时间复杂度：
�
(
�
�
)
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;
}
