Asia EC Online 2025 (I)——Canvas Painting （ 使用 dsu on next 实现大值域未涂色点的快速查找） · znzryb
## 思路讲解
不难想到，其实这个区间长度比较大的自由度
区间长度小的自由度比较小
因为咒语之间的顺序不重要，那么肯定是要排序的。
我们不妨用右端点排序。
那么我们发现，只要两个块颜色不同，且两个块中有一个未经过染色
（即保留着自己初始的独特颜色）
那么就是有一个贡献。
可以使用 dsu on next 进行下一个未涂色点的查询。
[https://chatgpt.com/share/68bfb91c-7cf0-8013-8e65-7615f4bf510f](https://chatgpt.com/share/68bfb91c-7cf0-8013-8e65-7615f4bf510f)
核心贪心代码
```cpp
ll ans=N;
for (auto&[r, vec] : g) {
for(auto l:vec){
ll x=find(l); // 第一个未被涂色的点
if(x<r){
fa[x]=x+1;
--ans;
}
}
}
```
## AC代码
[https://qoj.ac/submission/1307214](https://qoj.ac/submission/1307214)
::: 源代码
```cpp
// by Gospel_rock
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())
using namespace std;
#ifdef _DEBUG
template<typename T> void _print(T x) {
cerr << x;
}
// 可以打印多层数组，但是格式不是很好
template<typename T> void _print(vector<T> v) {
cerr << "[ ";
for (T i : v) _print(i), cerr << " ";
cerr << "]";
}
template<typename T> void _print(set<T> s) {
cerr << "{ ";
for (T i : s) _print(i), cerr << " ";
cerr << "}";
}
template<typename T, typename U> void _print(pair<T, U> p) {
cerr << "{";
_print(p.first);
cerr << ", ";
_print(p.second);
cerr << "}";
}
template<typename T, typename U> void _print(map<T, U> m) {
cerr << "{ ";
for (auto &p : m) _print(p), cerr << " ";
cerr << "}";
}
// 打印两层数组，格式好一些
template<typename T> void _print(vector<vector<T >> v) {
cerr << "{\n"; for (auto i : v) _print(i), cerr << "\n"; cerr << " }";
}
#endif
using ll = long long; using ull = unsigned long long;
using ld = double; using LD = long double;
using i128 = __int128;
using pdd = pair<ld, ld>; using plb = pair<ll, bool>;
using pll = pair<ll, ll>; using vll = vector<ll>; using vb = vector<bool>;
using tll = tuple<ll, ll, ll>; using vii = vector<int>;
using vpll = vector<pll>; using vtll = vector<tll>;
using vdb = vector<ld>; using vc = vector<char>;
using arr3 = array<ll, 3> ; using arr2 = array<ll, 2>;
using CD = complex<double>;
static constexpr ll MAXN = (ll)2e5+10, INF = (ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod = (ll)1e9+7; // 998244353;
static constexpr double eps = 1e-8; const double pi = acos(-1.0);
ll N, M, Q, X, K, T, lT;
inline void __();
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> lT;
while (lT--)
__();
return 0;
}
/*
不难想到，其实这个区间长度比较大的自由度
区间长度小的自由度比较小
因为咒语之间的顺序不重要，那么肯定是要排序的。
我们不妨用右端点排序。
那么我们发现，只要两个块颜色不同，且两个块中有一个未经过染色
（即保留着自己初始的独特颜色）
那么就是有一个贡献。
可以使用 dsu on next 进行下一个未涂色点的查询。
https://chatgpt.com/share/68bfb91c-7cf0-8013-8e65-7615f4bf510f
*/
arr2 lr[MAXN];
map<ll, ll> fa;
ll find(ll x) {
if (!fa.count(x)) return x;
return fa[x] = find(fa[x]);
}
inline void __() {
cin >> M >> N;
FOR(i, 1, M) {
cin >> lr[i][0] >> lr[i][1];
}
sort(lr + 1, lr + 1 + M, [&](const arr2 & a, const arr2 & b) {
if (a[1] != b[1]) return a[1] < b[1];
return a[0] < b[0];
});
map<ll, vector<ll> > g;
FOR(i, 1, M) {
g[lr[i][1]].push_back(lr[i][0]);
}
fa.clear();
ll ans=N;
for (auto&[r, vec] : g) {
for(auto l:vec){
ll x=find(l);
if(x<r){
fa[x]=x+1;
--ans;
}
}
}
cout<<ans<<"\n";
}
/*
AC
https://qoj.ac/submission/1307214
*/
```
:::
## 心路历程（WA，TLE，MLE……）