根号算法

模拟赛竟然有。。。不是说noip不考吗。。。

数列分块¶

有些看似树套树的玩意儿可以拿这个简单 \(O(n\sqrt{n}\log n)\) 硬搞：

P2801 教主的魔法 - 洛谷 | 计算机科学教育新生态

关于 tag：一般进行标记永久化。但也有不便于维护的tag。这一般出现在边角上，因为边角块内只有局部会修改。因此直接暴力处理，先pushdown原来的懒标记，求得块内各元素值 , 并清空标记，然后暴力修改局部的值。

注意 ：只能对边角进行下放。否则是假的复杂度。

块状链表¶

1. 每个块使用vector存储，暴力insert，每插入 \(\sqrt{n}\) 次整体重构。
2. 也可以块状链表（即不是整体重构，而是只重构一个vector）
3. using __gnu_cxx::rope; 可持久化平衡树（可以随机访问的set）

普通莫队¶

鞭尸一下，这俩用离线询问+树状数组吊打莫队。

按序列长度分块（当询问次数与长度不同阶，另算），把所有询问按：左端点所在块编号、右端点，从小到大排序。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

void move(int pos, int sign) {
  // update 比如说给桶中某个颜色+/-
}

void solve() {
  unit = int(ceil(sqrt(n)));
  sort(querys, querys + m);
  for (int i = 0; i < m; ++i) {
    const query &q = querys[i];
    while (l > q.l) move(--l, 1);
    while (r < q.r) move(++r, 1);
    while (l < q.l) move(l++, -1);
    while (r > q.r) move(r--, -1);
    ans[q.id] = nowAns;
  }
}

奇偶化排序优化：对于属于奇数块的询问，r 按从小到大排序，这样当前块查询完，r 更靠近 n。而在下一个偶数块的询问中，r 从大到小排序，这样我们的 r 指针将在返回的途中顺便处理偶数块的问题。回到更靠近 l 的地方后，再向 n 移动处理下一个奇数块的问题，优化了 r 指针的移动次数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

struct node {
  int l, r, id;

  bool operator<(const node &x) const {
    if (l / unit != x.l / unit) return l < x.l;
    if ((l / unit) & 1)
      return r < x.r;
    return r > x.r;
  }
};

P1494 [国家集训队] 小 Z 的袜子 - 洛谷 | 计算机科学教育新生态

带修、回滚和树上¶

咕咕咕