专栏文章

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

yyukimianyan
算法·理论参与者 6已保存评论 7

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
7 条
当前快照
2 份
快照标识符
@mlia9upn
此快照首次捕获于
2026/02/12 01:08
上周
此快照最后确认于
2026/02/19 01:17
13 小时前
查看原文

队列

先给出一个问题描述，我们有一个二元函数 f:N2→{0,1}f:\mathbb N^2\to \{0,1\} 满足
∀l1≤l2≤r2≤r1  ⟹  f(l1,r1)≤f(l2,r2)(区间包含单调性)\forall l_1\leq l_2\leq r_2\leq r_1\implies f(l_1,r_1)\leq f(l_2,r_2)\quad (\text{区间包含单调性})
在这样的定义下，对于一个 rr，就会存在一个最小的 torto_r 使得 f(tor,r)=1f(to_r,r)=1。显然 torto_r 是单调不降的，问题是求出所有的 torto_r。
双指针维护两个指针 l,rl, r，来求出 torto_r 序列。算法流程是从小到大枚举 rr，然后一直检查 f(l,r)f(l,r) 是否为 00，如果是，就将 ll 加一，最后一直加到 f(l,r)=1f(l,r)=1，这个 ll 就是 torto_r。注意，这里 ll 是所有 rr 共同使用的一直增加的变量，因此 ll 的移动量是 O(n)O(n) 的。
双指针一般是用来尝试解决关于区间的问题的，f(l,r)f(l,r) 和区间 [l,r][l,r] 的信息有关。每次 rr 增加或者 ll 增加，就对应将一个元素加入或删除。这就像一个队列，我们要维护一个队列，支持尾部加入，头部删除，查询队列中元素算出的 ff 的值。我们进行 O(n)O(n) 次这三种操作就能完成双指针。

双栈模拟队列

如果信息不支持删除，但是有结合律且可以合并（例子：群，包括线性基），我们可以尝试双栈模拟队列。我们需要两个栈 A,BA,B，它们的两个栈底是相连的，就像这样：（下标越小越靠近栈顶）
A1,A2,A3∣B4,B3,B2,B1A_1,A_2,A_3\mid B_4,B_3,B_2,B_1
每次加入一个元素的时候，往 BB 的栈顶压入元素。每次删除一个元素的时候，如果 AA 栈非空，就弹出 AA 栈栈顶；否则将 BB 中元素全部倒出来，倒序压入 AA 栈，再弹出 AA 栈栈顶。信息在这个过程中的维护是简单的。
由于每个元素只会从 BB 栈进入 AA 栈恰好一次，因此时间复杂度为 O(n)O(n)。
CPP
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)O(\log n) 因子进行单栈模拟队列。思路是从双栈模拟队列出发，将两个栈合并成一个栈：
∣B4,A3,A2,B3,A1,B2,B1\mid B_4,A_3,A_2,B_3,A_1,B_2,B_1
每次加入元素，就将其作为 BB 栈元素压入栈；每次删除最先一次加入的元素（出队），如果 AA 栈非空（有 AA 元素），就弹出 AA 栈栈顶，但是会有 BB 元素压在 A1A_1 上面使其无法弹出，我们将 A1A_1 上的 BB 元素连同 A1A_1 全部弹出，再将 BB 元素按照原顺序放回去，就相当于是把 A1A_1 删了。如果 AA 栈是空的（没有 AA 元素），那就将所有 BB 元素全部弹出再逆序放回去（为了改顺序让最先进队的元素靠近栈顶），然后再把 A1A_1 删了。
但是这样复杂度肯定是错的，BB 元素下面可能压着很多 AA 元素，如果反复出队就炸了。我们需要一个势能分析控制复杂度。提出一个理论，设有 cntcnt 个 AA 元素，我们尝试出队的时候一口气弹出 lowbit⁡(cnt)\operatorname{lowbit}(cnt) 个 AA 元素以及这些元素头上压着它们的 BB 元素，再将 BB 元素压回去，再将 lowbit⁡(cnt)−1\operatorname{lowbit}(cnt)-1 个 AA 元素压回去，最后一个要弹掉的 AA 元素就不放回去了。没有 AA 元素的时候还是要把所有 BB 元素弹出改成 AA 元素的顺序。
为什么这样就对了呢？我们首先需要一个归纳假设，从栈底到栈顶，AA 元素形成若干个连续段，每个连续段的长度都是 2k2^k，kk 从栈底到栈顶单调减（可能有部分段是连在一起的，但是可以拆成这样）。这样我们弹出 lowbit⁡(cnt)\operatorname{lowbit}(cnt) 个 AA 元素时，就实际上弹出的是最后一段 AA 的连续段和它头上的 BB 连续段，然后将这两段交换位置，将 A1A_1 弹出，lowbit⁡(cnt)\operatorname{lowbit}(cnt) 这个连续段立即拆为 2k,2k−1,⋯ ,202^k,2^{k-1},\cdots,2^0 这么多个连续段，连续段长度的总和是 lowbit⁡(cnt)−1\operatorname{lowbit}(cnt)-1（这些连续段是紧密相连的）。再证明完“所有 BB 元素弹出改成 AA 元素的顺序”的情况后，可以发现这个归纳就自动成立了。
现在设计势能函数以证明复杂度。一个 BB 元素的势能是它前面 AA 连续段的个数，每次拿出 BB 元素时这个势能就会减一，而势能始终 ≥0\geq 0，因此这部分复杂度正确。一个 AA 元素的势能是它所在 2k2^k 连续段的 kk 的值，每次拿出 AA 元素的时候 kk 会往下减，而势能始终 ≥0\geq 0，因此这部分复杂度正确。还有很重要的“所有 BB 元素弹出改成 AA 元素的顺序”的情况，这个也显然对复杂度不影响。
因此复杂度就是每个元素加入或撤销 O(log⁡n)O(\log n) 次。
CPP
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);
  }
};

评论

共 7 条评论，欢迎与作者交流。

正在加载评论...