AT_codefestival_2015_qualB_d Squares, Pieces and Coloring 题解

题目链接：AT_codefestival_2015_qualB_d Squares, Pieces and Coloring

题意：

有 $10^{100}$ 个方块排成一行。这些方块从左到右编号为 $1$ 到 $10^{100}$。

我们有 $N$ 个编号为 $1$ 到 $N$ 的棋子，以及一个计数器，可以存储介于 $0$ 和 $10^{100}$ 之间（包括边界值）的整数。

我们将使用这些工具执行 $N$ 个过程。初始时，方块为白色。第 $i$ 个过程（$1 \leq i \leq N$）如下：

1. 将棋子 $i$ 放在方块 $S_i$ 上，并将计数器设置为 $0$。

2. 查看棋子 $i$ 所在方块的颜色。若方块为白色，则将其涂为黑色，并将计数器增加 1。

   否则（若方块为黑色），将棋子 $i$ 向右移动一个方块。因此，一个方块可能包含多个棋子。

3. 如果计数器的值等于 $C_i$，则终止该过程。否则，返回到步骤 2。

找出所有 $N$ 个棋子在执行完所有 $N$ 个过程后的最终位置。

输入格式：

第一行输入 $N$ 。接下来 $N$ 行，每行两个数 $S_i,C_i$ 。

输出格式：

$N$ 行，表示每个棋子的最终位置。

数据范围：

$1\le N \le 10^5,~ 1\le S_i,C_i \le 10^9$

又是一道摇出来的冷门题，不得不说这个题目的名字是真的长

注意到每次染色其实就是添加黑块区间，或者把黑块区间合并。

考虑用 $\mathtt{set}$ 维护黑块的区间，然后就没啥好说的了，难点主要在代码。

时间复杂度 $\mathcal{O}(n\log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

set<pair<int,int>> st;
void solve()
{
    int s,c; cin >> s >> c;
    auto it = st.lower_bound({s + 1, 0});
    if(it != st.begin() && (*prev(it)).second >= s) --it;
    else { it = st.emplace(s,s).first; --c; }
    for(set<pair<int,int>>::iterator nxt; c > 0; )
    {
        nxt = next(it); auto [l,r] = *it; // C++17
        if(nxt == st.end()) { r = r + c, c = 0;}
        else {
            int gap = (*nxt).first - r - 1; // 间隔
            if(gap < c) { 
                c -= gap; r = (*nxt).second; st.erase(nxt);
            } else { r = r + c; c = 0; }
        }
        st.erase(it); it = st.emplace(l,r).first;
    }
    cout << (*it).second << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q; cin >> Q; while(Q--) solve();
    return 0;
}

---

参考文献：

[1] https://img.atcoder.jp/code-festival-2015-qualb/editorial.pdf