不知道怎么讲，我直接把实际应用贴出来，具体怎么实现自己品：

CF45C Dancing Lessons

题意

给你一个长度为 $n$ 的字符串，以及长度为 $n$ 的数组，让你每次删除字符串中相邻字符不同，且对应数组元素差值最小的那一对。如果有多对，选最左边那一对。让你模拟并输出第几次删了哪一对元素。

大概思路

题目让我们模拟，我们就直接模拟。

首先得解决，一共有多少对输出。显然，只要字符串中同时存在 “B” 和 “G”，那么必然会出现二者相邻的情况，所以输出对数应该是 $\min(cnt_G,~cnt_B) $，即输出对数取决于数量较少的那个字符。

然后接下来考虑怎么模拟这个过程：

我们知道，std::map 是有序的，通过 .find() 成员函数，我们可以获得对应键值的迭代器，那么自然地我们就能通过这个迭代器访问该键值的“前驱”和“后继”，从而实现模拟链表的需求。

我们可以先将信息全部丢到 map 里面：

std::map<int, std::pair<char, int>> treap;
for (int i = 1; i <= n; i++) {
   int x;
   std::cin >> x;
   treap[i] = {s[i], x};
}

为了维护哪一对相邻字符的对应权值相差最小，我们可以先暴力 $O(n)$ 扫一遍字符串，统计所有相邻字符不同的情况，把权值差、左边的下标、右边的下标收集到优先队列里。

这里我选用 set 代替了 priority_queue，具体为什么，后面再讲：

std::set<std::array<int, 3>> q;
for (int i = 2; i <= n; i++) {
   if (s[i] != s[i - 1]) {
       q.insert({std::abs(treap[i].second - treap[i - 1].second), i - 1, i});
   }
}

然后就可以开始一个个用 .begin() 从集合里弹出权值差最小的那对相邻下标 $l$ 和 $r$ 并输出了。

但是要注意，输出后，我们还得考虑三种特殊情况：

• 这对下标删除前，左边是否有其它的相邻字符与这对下标产生了贡献？
• 这对下标删除前，右边是否有其它的相邻字符与这对下标产生了贡献？
• 这对下标删除后，两边的字符串拼接到一起，是否会产生新的贡献对？

对于前两种情况，我们可以结合 map 的迭代器来查询前驱后继，然后把多余的贡献用 .erase() 从优先队列中剔除（这就是为什么要用 set 代替 priority_queue 的原因，pq 是不支持删除中间的元素的）

对于后一种情况，把贡献用 .insert() 补回来就行。

最后更新完，记得把 $l$ 和 $r$ 从 map 中 erase 掉，保证 map 能够继续行使链表的功能。

参考代码

void solve() {
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;
    s = " " + s;

    std::map<int, std::pair<char, int>> treap;
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        std::cin >> x;
        treap[i] = {s[i], x};
        if (s[i] == 'B') cnt++;
    }

    std::cout << std::min(cnt, n - cnt) << "\n";

    std::set<std::array<int, 3>> q;
    for (int i = 2; i <= n; i++) {//暴力统计当前所有不相等的相邻对
        if (s[i] != s[i - 1]) {
            q.insert({std::abs(treap[i].second - treap[i - 1].second), i - 1, i});
        }
    }

    while (q.size()) {
        auto [_, l, r] = *q.begin();
        q.erase(q.begin());
        std::cout << l << " " << r << "\n";

        if (treap.find(l) != treap.begin()) {//排除左边的额外贡献
            if (s[(--treap.find(l)) -> first] != s[l]) {
                q.erase({std::abs((--treap.find(l)) -> second . second - treap[l].second), (--treap.find(l)) -> first, l});
            }
        }
        if (treap.find(r) != --treap.end()) {//排除右边的额外贡献
            if (s[(++treap.find(r)) -> first] != s[r]) {
                q.erase({std::abs((++treap.find(r)) -> second . second - treap[r].second), r, (++treap.find(r)) -> first});
            }
        }
        if (treap.find(l) != treap.begin() && treap.find(r) != --treap.end() && s[(--treap.find(l)) -> first] != s[(++treap.find(r)) -> first]) {
            q.insert({//补上新的贡献
                std::abs((--treap.find(l)) -> second . second - (++treap.find(r)) -> second . second),
                (--treap.find(l)) -> first,
                (++treap.find(r)) -> first
            });
        }
        //map返回的迭代器是个pair，first是键，second是值

        treap.erase(l);//记得删多余的贡献
        treap.erase(r);
    }
}