不删除双指针（栈模拟队列）

yukimianyan · 2026-01-14 20:15:25 · 算法·理论

队列

先给出一个问题描述，我们有一个二元函数 f:\mathbb N^2\to \{0,1\} 满足

在这样的定义下，对于一个 r，就会存在一个最小的 to_r 使得 f(to_r,r)=1。显然 to_r 是单调不降的，问题是求出所有的 to_r。

双指针维护两个指针 l, r，来求出 to_r 序列。算法流程是从小到大枚举 r，然后一直检查 f(l,r) 是否为 0，如果是，就将 l 加一，最后一直加到 f(l,r)=1，这个 l 就是 to_r。注意，这里 l 是所有 r 共同使用的一直增加的变量，因此 l 的移动量是 O(n) 的。

双指针一般是用来尝试解决关于区间的问题的，f(l,r) 和区间 [l,r] 的信息有关。每次 r 增加或者 l 增加，就对应将一个元素加入或删除。这就像一个队列，我们要维护一个队列，支持尾部加入，头部删除，查询队列中元素算出的 f 的值。我们进行 O(n) 次这三种操作就能完成双指针。

双栈模拟队列

如果信息不支持删除，但是有结合律且可以合并（例子：群，包括线性基），我们可以尝试双栈模拟队列。我们需要两个栈 A,B，它们的两个栈底是相连的，就像这样：（下标越小越靠近栈顶）

每次加入一个元素的时候，往 B 的栈顶压入元素。每次删除一个元素的时候，如果 A 栈非空，就弹出 A 栈栈顶；否则将 B 中元素全部倒出来，倒序压入 A 栈，再弹出 A 栈栈顶。信息在这个过程中的维护是简单的。

由于每个元素只会从 B 栈进入 A 栈恰好一次，因此时间复杂度为 O(n)。

template <class T>
struct queue1 {
  T a[410], b[410], suf;
  int topa, topb;
  void clear() {
    topa = topb = 0;
  }
  void push(const T& x) {
    if (topa) suf = suf + x, a[++topa] = x;
    else suf = a[++topa] = x;
  }
  void pop() {
    if (topb) return --topb, void();
    assert(topa);
    swap(topa, topb);
    b[1] = a[topb];
    for (int i = 2; i <= topb; i++) b[i] = a[topb - i + 1] + b[i - 1];
    --topb;
  }
  T sum() {
    if (!topa && !topb) return /*零*/;
    if (!topa) return b[topb];
    if (!topb) return suf;
    return b[topb] + suf;
  }
};

单栈模拟队列

【UR #23】地铁规划 - 题目 - Universal Online Judge

如果信息不支持删除，但是支持加入和撤销最近一次操作，同时信息之间有交换律（可能还需要结合律）（例子：可撤销并查集），那么可以花费一个额外的 O(\log n) 因子进行单栈模拟队列。思路是从双栈模拟队列出发，将两个栈合并成一个栈：

每次加入元素，就将其作为 B 栈元素压入栈；每次删除最先一次加入的元素（出队），如果 A 栈非空（有 A 元素），就弹出 A 栈栈顶，但是会有 B 元素压在 A_1 上面使其无法弹出，我们将 A_1 上的 B 元素连同 A_1 全部弹出，再将 B 元素按照原顺序放回去，就相当于是把 A_1 删了。如果 A 栈是空的（没有 A 元素），那就将所有 B 元素全部弹出再逆序放回去（为了改顺序让最先进队的元素靠近栈顶），然后再把 A_1 删了。

但是这样复杂度肯定是错的，B 元素下面可能压着很多 A 元素，如果反复出队就炸了。我们需要一个势能分析控制复杂度。提出一个理论，设有 cnt 个 A 元素，我们尝试出队的时候一口气弹出 \operatorname{lowbit}(cnt) 个 A 元素以及这些元素头上压着它们的 B 元素，再将 B 元素压回去，再将 \operatorname{lowbit}(cnt)-1 个 A 元素压回去，最后一个要弹掉的 A 元素就不放回去了。没有 A 元素的时候还是要把所有 B 元素弹出改成 A 元素的顺序。

为什么这样就对了呢？我们首先需要一个归纳假设，从栈底到栈顶，A 元素形成若干个连续段，每个连续段的长度都是 2^k，k 从栈底到栈顶单调减（可能有部分段是连在一起的，但是可以拆成这样）。这样我们弹出 \operatorname{lowbit}(cnt) 个 A 元素时，就实际上弹出的是最后一段 A 的连续段和它头上的 B 连续段，然后将这两段交换位置，将 A_1 弹出，\operatorname{lowbit}(cnt) 这个连续段立即拆为 2^k,2^{k-1},\cdots,2^0 这么多个连续段，连续段长度的总和是 \operatorname{lowbit}(cnt)-1（这些连续段是紧密相连的）。再证明完“所有 B 元素弹出改成 A 元素的顺序”的情况后，可以发现这个归纳就自动成立了。

现在设计势能函数以证明复杂度。一个 B 元素的势能是它前面 A 连续段的个数，每次拿出 B 元素时这个势能就会减一，而势能始终 \geq 0，因此这部分复杂度正确。一个 A 元素的势能是它所在 2^k 连续段的 k 的值，每次拿出 A 元素的时候 k 会往下减，而势能始终 \geq 0，因此这部分复杂度正确。还有很重要的“所有 B 元素弹出改成 A 元素的顺序”的情况，这个也显然对复杂度不影响。

因此复杂度就是每个元素加入或撤销 O(\log n) 次。

struct queue2 {
  stack<int, vector<int>> stk;
  int cnt = 0;
  void (*add)(int);
  void (*undo)();
  queue2() = default;
  queue2(decltype(add) _add, decltype(undo) _undo) : add(_add), undo(_undo) {}
  void push(int x) {
    stk.push(x), add(x);
  }
  void pop() {
    vector<int> tmp[2];
    int lb = cnt & -cnt;
    while (!stk.empty() && (int)tmp[0].size() < (lb ? lb : 1)) {
      int x = stk.top();
      stk.pop(), undo();
      tmp[x > 0].push_back(x);
    }
    if (!cnt) {
      swap(tmp[0], tmp[1]);
      reverse(tmp[0].begin(), tmp[0].end());
      for (int &x : tmp[0]) x = -x;
      cnt = (int)tmp[0].size();
    }
    reverse(tmp[1].begin(), tmp[1].end());
    for (int x : tmp[1]) add(x), stk.push(x);
    reverse(tmp[0].begin(), tmp[0].end());
    tmp[0].pop_back(), --cnt;
    for (int x : tmp[0]) add(-x), stk.push(x);
  }
};