2025-2026 ICPC NERC, Kyrgyzstan Regional Contest 吉尔吉斯斯坦——J. Laser Balancing（ 使用 dsu on next 实现未涂色点的快速查找）（同一个值的一起操作，避免 TLE）

题目大意

题目总结

实验室里悬挂着 $n$ 个激光器，每个激光器的位置坐标为 $x_i = i$，初始距离天花板的高度为 $a_i$。所有激光器朝向屏幕发射光线。

规则如下：

1. 如果多个激光器处于同一高度（$a_i$ 相同），则坐标较小的激光器发出的光线会被阻挡，只有该高度下坐标最大的那个激光器能被屏幕接收。

2. 你可以进行操作：选定任意一个激光器，将其高度增加 1（即 $a_i \leftarrow a_i + 1$）。

3. 最多可以进行 $k$ 次操作。

4. 高度只能增加，不能减少。

你的目标是确定在不超过 $k$ 次操作的情况下，屏幕上最多能接收到多少个激光器的光线。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^4$)，表示测试用例的数量。
每个测试用例的第一行包含两个整数 $n$ 和 $k$ ($1 \le n \le 2 \cdot 10^5, 1 \le k \le 10^9$)，分别表示激光器的总数和最大操作次数。
第二行包含 $n$ 个整数 $a_i$ ($1 \le a_i \le 10^9$)，表示每个激光器的初始高度。

输出格式

对于每个测试用例，输出一个整数，表示最大可能的可见激光器数量。

样例

Input
3
4 4
1 2 3 4
4 5
1 1 1 1
9 2
4 3 3 10 5 5 5 99 11

Output
4
3
7

样例解释

• 测试用例 1：所有激光器初始高度均不相同，没有遮挡，因此 4 个激光器全部可见。

• 测试用例 2：初始所有 4 个激光器高度均为 1，只有坐标最大的第 4 个激光器可见。

  • 可以将第 2 个激光器高度增加 1（变 2），消耗 1 次操作。
  • 将第 3 个激光器高度增加 2（变 3），消耗 2 次操作。
  • 最终高度变为 [1, 2, 3, 1]。高度 1 的激光器中第 4 个可见，高度 2 的第 2 个可见，高度 3 的第 3 个可见。总共 3 个可见。

• 测试用例 3：初始有 3 个高度为 5 的激光器，其中仅 1 个可见。可以将其中一个高度为 5 的激光器移动到高度 6（消耗 1 次操作），从而增加 1 个可见数量，总可见数达到 7。

思路讲解

删除式 set 的思路尝试

我感觉其实这道题目类似于 mex 类似于 mex 我们可以采用求 mex 的删除式 set 做法。
讲讲我现在的想法以及卡点：
现在想法就是，已经确定高度的地方呢，我们就把它删掉。就是求 mix 嘛，要把它删掉，把这个 set 中的这个点就删掉。就是第一次出现，如果说这个高度第一次出现，我们就把 set 中的这个点给删掉。
然后这样子我们最后就得到了一些被挡住的点，以及剩下的所有的可选高度。
如果我不能使用删除式 set 的原因，其实是因为这样子的。原因是什么呢？其实是这个值域太大，你把所有点都塞进这个 set 里面就会出问题。

由于不能够使用删除式 set 实现查找最靠近的点的这个操作。

Asia EC Online 2025 (I)——Canvas Painting （ 使用 dsu on next 实现大值域未涂色点的快速查找）

我们使用 DSU on next 实现未涂色点的快速查找。

然后我们会发现这个 dsu on next 配合 priority queue 进行懒更新会导致这个问题，它会导致出现这个 TLE。

使用这样子的一个更新，它的问题在于，比如说，如果说所有的高度都为一的话，那么其实会被反复的插入。说白了就是如果说是同样的这个值的话，如果说是同样值的话，实际上它是会被反复操作的。哎，不过其实啊，这个叫什么？我们其实就同一个值，我们操作一次即可。

TLE 的根本原因在于：当前的 DSU + 优先队列方案中，元素会被反复弹出再塞回优先队列。以所有 $a_i = 1$、$N = 2 \times 10^5$ 为例，每个元素平均会被重新插入 $O(N)$ 次，总复杂度退化到 $O(N^2)$。

上面是 AI 告诉我们的，你稍微想一下，你就会知道，确实是这样子的。

while (!pq.empty()) {
    auto [dis,u]=pq.top();
    pq.pop();
    ll to=u+dis;
    if (op_num-dis<0) {
        break;
    }
    if (fa_mp.contains(to)) {
        to=find(find,to);
        pq.push({to-u,u});
    }else {
        op_num-=dis;
        fa_mp[to]=to+1;
        ++ans;
    }
}

https://codeforces.com/gym/106169/submission/363034637

TLE 代码

/**
 * Problem: J. Laser Balancing
 * Contest: 2025
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106169/problem/J
 * Created: 2026-02-15 18:22:28
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define debug3d(a)                                         \
cerr << #a << " = [\n";                                \
for (int i = 0; i < (int)(a).size(); i++)              \
{                                                      \
cerr << "  [\n";                                   \
for (int j = 0; j < (int)(a[i]).size(); j++)       \
{                                                  \
cerr << "    [";                               \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k];     \
cerr << "]\n";                                 \
}                                                  \
cerr << "  ]\n";                                   \
}                                                      \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */
struct Dis_u{
    ll dis,u;
    bool operator<(const Dis_u &o) const {
        if (dis!=o.dis) return dis>o.dis;
        return u<o.u;
    }
};
void Solve() {
    ll N,op_num;
    cin >> N >> op_num;
    vector<ll> A(N+2);
    for (int i=1;i<=N;++i) {
        cin>>A[i];
    }
    // 使用 DSU on Next 实现未涂色点的快速查找。
    map<ll,ll> fa_mp;
    auto find=[&](auto && self,ll u) {
        if (!fa_mp.contains(u)) return u;
        return fa_mp[u]=self(self,fa_mp[u]);
    };
    // 先反向遍历
    // 我们准备用一个懒更新，用一个懒更新，我们这边全部都塞最优的值。
    priority_queue<Dis_u> pq;
    ll ans=0;
    for (ll i=N;i>=1;--i) {
        ll height=A[i];
        if (fa_mp.contains(height)) {
            ll to=find(find,height);
            pq.push({to-height,height});
        }else {
            fa_mp[height]=height+1;
            ans++;
        }
    }
    while (!pq.empty()) {
        auto [dis,u]=pq.top();
        pq.pop();
        ll to=u+dis;
        if (op_num-dis<0) {
            break;
        }
        if (fa_mp.contains(to)) {
            to=find(find,to);
            pq.push({to-u,u});
        }else {
            op_num-=dis;
            fa_mp[to]=to+1;
            ++ans;
        }
    }
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
1
4 5
1 1 1 1

*/

解决 DSU on Next 加 Priority Queue 懒更新的 TLE 问题。

那么我们上面已经说了，问题的关键在于重复值，它会非常傻的继续去全部都操作一遍。那么其实就是重复值我们一起操作就行了。

我们就给这个往 Priority Queue 里面塞的这个结构体啊，再加一个属性。这个结构体我们加一个属性，加一个属性 cnt 然后进行一起操作，懒操作就好了。

struct Dis_u_cnt{
    ll dis,u,cnt;
    bool operator<(const Dis_u_cnt &o) const {
        if (dis!=o.dis) return dis>o.dis;
        // 随便又写了一个这个东西，随便写了一个比较，其实无所谓。
        return u<o.u;
    }
};

我们的懒操作其实也很好写，其实就加一个 cnt 属性。你把它弹出来以后，如果 cnt 还大于一，你就减一。如果 cnt 已经是小于等于一了，那你 pop 掉了以后，其实这东西就没有了嘛，对吧？

while (!pq.empty()) {
    auto [dis,u,cnt]=pq.top();
    pq.pop();
    ll to=u+dis;
    if (op_num-dis<0) {
        break;
    }
    if (fa_mp.contains(to)) {
        to=find(find,to);
        pq.push({to-u,u,cnt});
    }else {
        op_num-=dis;
        fa_mp[to]=to+1;
        ++ans;
        if (cnt>1) {
            to=find(find,to);
            pq.push({to-u,u,cnt-1});
        }
    }
}

AC代码

AC

https://codeforces.com/gym/106169/submission/363039919

源代码

/**
 * Problem: J. Laser Balancing
 * Contest: 2025
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106169/problem/J
 * Created: 2026-02-15 18:22:28
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define debug3d(a)                                         \
cerr << #a << " = [\n";                                \
for (int i = 0; i < (int)(a).size(); i++)              \
{                                                      \
cerr << "  [\n";                                   \
for (int j = 0; j < (int)(a[i]).size(); j++)       \
{                                                  \
cerr << "    [";                               \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k];     \
cerr << "]\n";                                 \
}                                                  \
cerr << "  ]\n";                                   \
}                                                      \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */
struct Dis_u_cnt{
    ll dis,u,cnt;
    bool operator<(const Dis_u_cnt &o) const {
        if (dis!=o.dis) return dis>o.dis;
        // 随便又写了一个这个东西，随便写了一个比较，其实无所谓。
        return u<o.u;
    }
};
void Solve() {
    ll N,op_num;
    cin >> N >> op_num;
    vector<ll> A(N+2);
    for (int i=1;i<=N;++i) {
        cin>>A[i];
    }
    // 使用 DSU on Next 实现未涂色点的快速查找。
    map<ll,ll> fa_mp;
    auto find=[&](auto && self,ll u) {
        if (!fa_mp.contains(u)) return u;
        return fa_mp[u]=self(self,fa_mp[u]);
    };
    // 先反向遍历
    // 我们准备用一个懒更新，用一个懒更新，我们这边全部都塞最优的值。
    priority_queue<Dis_u_cnt> pq;
    ll ans=0;
    map<ll,ll> freq;
    for (ll i=N;i>=1;--i) {
        ll height=A[i];
        if (fa_mp.contains(height)) {
            // ll to=find(find,height);
            // pq.push({to-height,height});
            freq[height]++;
        }else {
            fa_mp[height]=height+1;
            ans++;
        }
    }
    for (auto [u,cnt]:freq) {
        ll to=find(find,u);
        pq.push({to-u,u,cnt});
    }
    while (!pq.empty()) {
        auto [dis,u,cnt]=pq.top();
        pq.pop();
        ll to=u+dis;
        if (op_num-dis<0) {
            break;
        }
        if (fa_mp.contains(to)) {
            to=find(find,to);
            pq.push({to-u,u,cnt});
        }else {
            op_num-=dis;
            fa_mp[to]=to+1;
            ++ans;
            if (cnt>1) {
                to=find(find,to);
                pq.push({to-u,u,cnt-1});
            }
        }
    }
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
1
4 5
1 1 1 1

*/

心路历程（WA，TLE，MLE……）