带修莫队

介绍

在普通莫队的基础上加入时间轴和指针，允许单点修改

原理

q 次查询，t 次修改

序列分块

每块大小为 $L$，块数 $N = \lceil \dfrac{n}{L} \rceil$ 一般取 $L = n^{\frac{2}{3}}$，后续证明。

排序规则

• 先按照区间左端所属块排序
• 左端在同一块的，按右端所属块排序
• 左端和右端在同一块的，按时间排序

双指针移动

• 左右指针
  • 在一个二维块里来回移动，每次 $O(L)$，最多 $q$ 次
  • 需要换块时 $O(n)$，二维块 $N^2$ 块
  • 总共移动 $O(qL + nN^2)$
• 时间指针
  • 块内时间单调递增，最多 $O(t)$
  • 换块时 $O(t)$，二维块 $N^2$ 块
  • 总共移动 $O(t + tN^2) = O(tN^2)$

复杂度

• 总共 $O(qL + (n + t)N^2)$
• $t,q$ 视为近似 $n$，$O(n(L + N^2))$
• 取 $L = n^{\frac{2}{3}}$，复杂度取最小值 $O(n^{\frac{5}{3}})$

$f = n(L + N^2) = n(\frac{n}{N} + N^2)$ $\frac{\delta f}{\delta N} = n(- \frac{n}{N^2} + 2N)$ 令 $\frac{\delta f}{\delta N} = 0$，则 $2N^3 = n$ $N = n^{\frac{1}{3}}, L = \frac{n}{N} = n^{\frac{2}{3}}$

实现

查询区间和、单点加为例

数据结构

• 查询结构

struct Query{
    // 闭区间 [l, r]
    int id, l, r, t;
};
vector<Query> qry;

• 块结构

struct Block{
    int l, r;
}
vector<Block> blo;
vector<int> in;

• 修改结构

struct Modify{
    int pos, add;
}
vector<Modify> mod;

• 原始序列和查询结果

vector<int> org, ans;
int sum = 0;

功能函数

• 排序

bool cmp(Query &a, Query &b){
    // 按照 l 所属块排序
    if(in[a.l] != in[b.l]) return in[a.l] < in[b.l];
    // l 在同一块的，按 r 所属块排序
    if(in[a.r] != in[b.r]) return in[a.r] < in[b.r];
    // l 和 r 在同一块的，按 t 排序
    return a.t < b.t;
}

• 指针移动

// 纳入
void include(int x){
    sum += org[x];
}
// 排除
void exclude(int x){
    sum -= org[x];
}

• 修改

// 实施
void apply(int l, int r, int t){
    auto [p, add] = mod[t];
    // 修改点在监控中，先排除，改后再纳入
    if(p >= l && p <= r) exclude(p), org[p] += add, include(p);
    // 修改点不在监控中，直接修改
    else org[p] += add;
}
// 撤销
void revoke(int l, int r, int t){
    auto [p, add] = mod[t];
    if(p >= l && p <= r) exclude(p), org[p] -= add, include(p);
    else org[p] -= add;
}

主函数

void mo(){
    sort(query.begin(), query.end(), cmp);
    // 空区间 [1, 0]
    int l = 1, r = 0, t = 0;
    for(auto &q: query){
        // 移动左右指针
        while(l > q.l) include(--l);
        while(r < q.r) include(++r);
        while(l < q.l) exclude(l++);
        while(r > q.r) exclude(r--);
        // 移动时间指针
        while(t < q.t) apply(l, r, ++t);
        while(t > q.t) revoke(l, r, t--);
        // 记录结果
        ans[q.id] = sum;
    }
}

奇偶排序

问题

• 左端换块时，右端猛回头走到最左
• 右端换块时，时间指针猛回头走到最早

优化

• 根据左端块奇偶，决定右端升序或降序
• 根据右端块奇偶，决定时间指针升序或降序

实现

bool cmp(Query &a, Query &b){
    // 按照 l 所属块排序
    if(in[a.l] != in[b.l]) return in[a.l] < in[b.l];
    // 根据 l 所属块奇偶，按 r 所属块奇偶排序
    if(in[a.r] != in[b.r]) return (in[a.l] & 1) ? in[a.r] < in[b.r] : in[a.r] > in[b.r];
    // 根据 r 所属块奇偶，按时间奇偶排序
    return (in[a.r] & 1) ? a.t < b.t : a.t > b.t;
}