2025-2026 ICPC NERC, Kyrgyzstan Regional Contest 吉尔吉斯斯坦——J. Laser Balancing（ 使用 dsu on next 实现未涂色点的快速查找）（同一个值的一起操作，避免 TLE） · znzryb
## 题目大意
**题目总结**
实验室里悬挂着 $n$ 个激光器，每个激光器的位置坐标为 $x_i = i$，初始距离天花板的高度为 $a_i$。所有激光器朝向屏幕发射光线。
规则如下：
1. 如果多个激光器处于**同一高度**（$a_i$ 相同），则**坐标较小**的激光器发出的光线会被阻挡，只有该高度下**坐标最大**的那个激光器能被屏幕接收。
1. 你可以进行操作：选定任意一个激光器，将其高度增加 1（即 $a_i \leftarrow a_i + 1$）。
1. 最多可以进行 $k$ 次操作。
1. 高度只能增加，不能减少。
你的目标是确定在不超过 $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 实现大值域未涂色点的快速查找）](/2025/09/09/20250909-af0238b4)
我们使用 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 告诉我们的，你稍微想一下，你就会知道，确实是这样子的。
```cpp
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](https://codeforces.com/gym/106169/submission/363034637)
::: TLE 代码
```cpp
/**
* 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 然后进行一起操作，懒操作就好了。
```cpp
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 掉了以后，其实这东西就没有了嘛，对吧？
```cpp
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](https://codeforces.com/gym/106169/submission/363039919)
::: 源代码
```cpp
/**
* 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……）