莫队

适用范围

[l,r]→O⁡(1)[l,r+1],[l,r−1],[l+1,r],[l−1,r][l, r] \rightarrow_{\operatorname O(1)} [l, r+1], [l, r-1], [l+1, r], [l-1, r]

代码

1
2
3
4
5
6
7
8
9
10
11
12
sort(operations, (x, y) -> {
    key1 = left_block(x), left_block(y);
    key2 = right(x), right(y);
})

l = 1, r = 0;
for (o <- operations) {
    while (l < o.l) del(l++);
    while (l > o.l) add(--l);
    while (r < o.r) add(++r);
    while (r > o.r) del(r--);
}

复杂度

O⁡(nn)\operatorname O (n \sqrt n)

最极端的情况

每次 rr 右移一位，ll 在一个块中，至多移动 n\sqrt n