区间合并+并查集

前言：写完这个题目的时候没意识到这个和区间合并是等价的，现在看起来确实是一个区间合并的题目
（注意这个多米诺骨牌是可以连续推倒的）

#include<bits/stdc++.h>
using namespace std;#define int long long
int t;
int n,m;
const int N = (int)2e5+5;
struct node{int h,pos;bool operator<(node b){return pos < b.pos;}
}sto[N];
int fa[N];
int find(int x){if(x==fa[x]) return x;return fa[x] = find(fa[x]);
}
int ans[N];bool cmp(int a,int b){return a>b;
}signed main(){cin >> t;while(t--){cin >> n >> m;for(int i=1;i<=n;i++){cin >> sto[i].h;}for(int i=1;i<=n;i++){cin >> sto[i].pos;}sort(sto+1,sto+1+n);for(int i=1;i<=n;i++) fa[i] = i;int j;for(int i=1;i<=n;i=j){int hi = sto[i].h, posi= sto[i].pos;int en = hi + posi;for(j=i+1;j<=n;j++){int hj = sto[j].h, posj = sto[j].pos;if(en>=posj){  // 如果能够到达 fa[j] = i;//更新我们的长度en = max(en,hj+posj); }else{break;}}}for(int i=1;i<=n;i++) ans[i] = 0;for(int i=1;i<=n;i++){int x = find(i);//cout << " i " << x << endl;ans[x]++;}sort(ans+1,ans+1+n,cmp);int e = 0;//cout << " ans 1 " << ans[1] << endl;for(int i=1;i<=m;i++){e+=ans[i];}cout << e << endl;}return 0;
}