- 题目链接：https://www.nowcoder.com/exam/company?currentTab=recommand&jobId=100&selectStatus=0&tagIds=179
4.删除区间 #
#include <iostream>
#include <cmath>
using namespace std;
const int N = 1e5;
int n, a[N+5];
// two为前i个数中2的个数，five为前i个数中5的个数
int two[N+5], five[N+5];
int get(int i, int j){
// 即2.1.1方案，求出去掉区间[i,j]后乘积末尾 0的个数
return min(two[n]-two[j]+two[i-1], five[i-1]+five[n]-five[j]);
}
int main() {
int k; cin >> n >> k;
for(int i=1; i<=n; i++) cin >> a[i];
for(int i=1; i<=n; i++){
// 求因子2，5的个数
while(a[i]%2==0) two[i]++, a[i]/=2;
while(a[i]%5==0) five[i]++, a[i]/=5;
// 维护前缀和
two[i] += two[i-1];
five[i] += five[i-1];
}
int l = 0, r = 0;// 记录上一次删除区间，防止重复相加
long long ans = 0;
for(int i=1, j=1; i<=n && j<=n; ){
j = max(j, i);// 当 i右移超过j后，j不能比 i小，所以需要更新一下
while(j <=n && get(i, j) >= k) j++;//当剩余区间值不小于k，就不断向右移
ans += 1LL*(j-i)*(j-i+1)/2;// 删除方案即该区间的等差数列公式
if(r >= i) ans -= 1LL*(r-i)*(r-i+1)/2;
//如果上一个区间[l,r]的右端点不小于本次区间[i,j]的左端点，则产生重复需要删去 [i, r]方案数
l = i, r = j;//上次删除区间更新为[i,j]
while(i <= j && get(i, j)<k) i++;//右移i，直到再次可以删除 或 左右边界重合 停止
}
cout << ans;
}
5.小美的朋友关系 #
小美认为，在人际交往中，但是随着时间的流逝，朋友的关系也是会慢慢变淡的，最终朋友关系就淡忘了。
现在初始有一些朋友关系，存在一些事件会导致两个人淡忘了他们的朋友关系。小美想知道某一时刻中，某两人是否可以通过朋友介绍互相认识？
事件共有 2 种：
1 u v：代表编号 u 的人和编号 v 的人淡忘了他们的朋友关系。2 u v：代表小美查询编号 u 的人和编号 v 的人是否能通过朋友介绍互相认识。
注：介绍可以有多层，比如 2 号把 1 号介绍给 3 号，然后 3 号再把 1 号介绍给 4 号，这样 1 号和 4 号就认识了。
输入描述：
第一行输入三个正整数n,m,q，代表总人数，初始的朋友关系数量，发生的事件数量。
接下来的m行，每行输入两个正整数u,v，代表初始编号u的人和编号v的人是朋友关系。
接下来的q行，每行输入三个正整数op,u,v，含义如题目描述所述。
- $1\leq n \leq 10^9$
- $1\leq m,q \leq 10^5$
- $1\leq u,v \leq n$
- $1\leq op \leq 2$
保证至少存在一次查询操作。
输出描述：
对于每次 2 号操作，输出一行字符串代表查询的答案。如果编号 u 的人和编号 v 的人能通过朋友介绍互相认识，则输出"Yes"。否则输出"No"。
输入例子：
5 3 5
1 2
2 3
4 5
1 1 5
2 1 3
2 1 4
1 1 2
2 1 3
输出例子：
Yes
No
No
例子说明：
第一次事件，1 号和 5 号本来就不是朋友，所以无事发生。
第二次事件是询问，1 号和 3 号可以通过 2 号的介绍认识。
第三次事件是询问，显然 1 号和 4 号无法互相认识。
第四次事件，1 号和 2 号淡忘了。
第五次事件，此时 1 号无法再经过 2 号和 3 号互相认识了。
解题时并没有做出来，
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt(), m = in.nextInt(), q = in.nextInt();
Set<List<Integer>> relationship = new HashSet<>();
UnionFind union = new UnionFind(n + 1);
int[][] events = new int[q][4];
for (int i = 0; i < m; i++) {
int u = in.nextInt(), v = in.nextInt();
relationship.add(Arrays.asList(Math.min(u, v), Math.max(u, v)));
union.parent[u]=u;
union.parent[v]=v;
}
for (int i = 0; i < q; i++) {
events[i][3] = Integer.MAX_VALUE;
}
for (int i = 0; i < q; i++) {
int op = in.nextInt(), u = in.nextInt(), v = in.nextInt();
events[i][0] = op;
events[i][1] = u;
events[i][2] = v;
if (op == 1) {
if (relationship.contains(Arrays.asList(Math.min(u, v), Math.max(u, v)))) {
relationship.remove(Arrays.asList(Math.min(u, v), Math.max(u, v)));
events[i][3] = Math.min(events[i][3], i);
}
}
}
for (List<Integer> relation : relationship) {
union.union(relation.get(0), relation.get(1));
}
List<String> ans = new ArrayList<>();
for (int i = events.length - 1; i >= 0; i--) {
if (events[i][0] == 1) {
if ( events[i][3] == i)
union.union(events[i][1], events[i][2]);
} else {
if(union.parent[events[i][1]]==0) union.parent[events[i][1]] = events[i][1];
if(union.parent[events[i][2]]==0) union.parent[events[i][2]] = events[i][2];
ans.add(union.query(events[i][1], events[i][2]) ? "Yes" : "No");
}
}
for (int i = ans.size() - 1; i >= 0; i--) {
System.out.println(ans.get(i));
}
}
public static class UnionFind {
public int[] parent;
public UnionFind(int N) {
parent = new int[N];
// for (int i = 0; i < N; i++) {
// parent[i] = i;
// }
}
public int find(int v) {
if (v != parent[v]) {
parent[v] = find(parent[v]);
}
return parent[v];
}
public void union(int v1, int v2) {
int f1 = find(v1);
int f2 = find(v2);
if (f1 != f2) {
parent[f2] = f1;
}
}
public boolean query(int i, int j) {
return find(i) == find(j);
}
public void out() {
for (int i = 0; i < parent.length; i++) {
System.out.print(parent[i] + " ");
}
System.out.println();
}
}
}
一直报错
后来看的别人的题解
#include <iostream>
#include <set>
#include <vector>
#include <map>
using namespace std;
const int N = 1e5;
using PII = pair<int,int>;
int n, m, q;
map<int,int>f;// 并查集父亲数组
struct node{
int op, u, v;
}ord[N+5];// 新的操作数组
int find(int x){// 路径压缩
while(f[x] != x) x = f[x] = f[f[x]];
return x;
}
void merge(int u,int v){// 并查集合并
int fa = find(u);
int fb = find(v);
f[fb] = fa;
}
int main() {
cin >> n >> m >> q;
set<PII>st;// 关系集合
for(int i=0, u, v; i<m; i++){
cin >> u >> v;
st.insert({u, v}); // u, v放进关系集合中
f[u] = u, f[v] = v;// 把出现的结点父节点设置为自己
}
int num = 0;// 新的操作数组长度
for(int i=0; i<q; i++){
int op, u, v; cin >> op >> u >> v;
//如果是查询操作，可以直接存入
// 如果是删除操作，需要判断原关系集合中是否存在
if(op == 1){
// 可能是 {u,v} 形式存储
if(st.find({u, v}) != st.end()) st.erase({u, v});
// 可能是 {v,u} 形式存储
else if(st.find({v, u}) != st.end()) st.erase({v, u});
// 如果不存在直接跳过，不储存此次删除操作
else continue;
}
// 存入新的操作数组中
ord[num++] = {op, u, v};
}
// 删除之后，剩余关系集合就是没有涉及到的，也是最终的并查集
for(auto [u,v]:st) merge(u, v);
vector<bool>ans;// 存储答案
for(int i=num-1; i>=0; i--){// 倒着重新进行操作
int op = ord[i].op, u = ord[i].u, v = ord[i].v;
if(op == 1) merge(u, v);// 如果是删除操作，反过来进行合并
else{
// 当 f[u] = 0时，就是第一次出现该节点，需要初始化f[i]=i,方便进行路径压缩
if(!f[u]) f[u] = u;
if(!f[v]) f[v] = v;
ans.emplace_back(find(u) == find(v));// 查询操作，就储存答案
}
}
//因为是倒着遍历操作的，所以答案是倒着存储的
for(int i=ans.size()-1; i>=0; i--)
if(ans[i]) cout << "Yes" << endl;
else cout << "No" << endl;
}