序列 - 题解
SAMSHAWCRAFT · · 题解
要求维护一个数据结构，支持：
-
区间加
-
单点查询历史不小于某个值的时间
常见的分治数据结构很难做这个（也许有能做的分治数据结构但是没有引入 OI 实战，又或者是我无知），因为区间加的数据结构很难维护历史版本，而能维护历史版本的数据结构往往也只能单点修改，如果把区间加拆成单点加，无论是时间复杂度还是内存开支都会很大。
因此我们需要考虑分块，发现如果只维护一个数字的话可以时间分块解决时间区间加、单点查询历史不小于某个值的时间的问题。具体做法就是把每一个时间当作序列的下标，整个时间轴放在序列上做分块，这样可以规约到区间加、区间查询不小于某个值的数字个数的问题，也就是 LibreOJ::#6278. 数列分块入门 2。
我们尝试把上面这个东西从维护一个数字变成维护
我们把所有操作离线下来，用扫描线一个一个地把序列上每个数字的答案维护出来即可。所以这题是扫描线套分块的思路，解题步骤就是：
-
把所有操作离线。把区间加拆成
[l,n] 和[r+1,n] 方便扫描线。 -
把所有的修改和查询都排序。按序列中的下标排序方便按顺序处理。
-
在分块上进行操作，完成单个数字答案的维护。
-
把所有的查询的答案输出。
代码的话就是在数列分块入门 2 上加一个离线、加一个扫描线即可，可以
//qpp 是查询总数，quop 是查询操作的数组
//upp 是修改总数，upop 是修改操作的数组
//c 是题目输入的原数列
struct cmp1{
bool operator()(const op_t &a,const op_t &b){ return a.id<b.id; }
};
struct cmp2{
bool operator()(const op_t &a,const op_t &b){ return a.t<b.t; }
};
std::sort(upop+1,upop+upp+1,cmp1());
std::sort(quop+1,quop+qpp+1,cmp1());
for(int cx=1,cut=1;cx<=qpp;++cx){
while(cut<=upp&&upop[cut].id<=quop[cx].id){
add(upop[cut].t,q+1,upop[cut].val);
cut++;
}
quop[cx].ans=query(1,quop[cx].t-1,quop[cx].val-c[quop[cx].id]);
}
std::sort(quop+1,quop+qpp+1,cmp2());这里重点写一写复杂度分析。
设块长为