专栏文章

题解：AT_abc406_d [ABC406D] Garbage Removal

jjess1ca1o0g3
AT_abc406_d题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip9qs1h
此快照首次捕获于
2025/12/03 08:28
3 个月前
此快照最后确认于
2025/12/03 08:28
3 个月前
查看原文
D 严格小于 C。

思路

考虑维护两个集合，一个以行为关键字，一个以列为关键字。每次询问就把一行或一列删完，然后在另一个集合里面把对应的点删除。实际写的时候用 map<int,set<int>> 来做。可以结合代码理解。

代码

CPP
#include<bits/stdc++.h>
#define i64 long long
#define L(a,b,c,d) for(int a=b;a<=c;a+=d)
#define R(a,b,c,d) for(int a=b;a>=c;a-=d)

using namespace std;
void solve();
int n,m,k,q;
map<int,set<int>> st1,st2; 

signed main(){
  int Test=1;
  while(Test--) solve();
  return 0;
}

void solve(){
  scanf("%d%d%d",&n,&m,&k);
  L(i,1,k,1){
    int x,y;
    scanf("%d%d",&x,&y);
    st1[x].insert(y);
    st2[y].insert(x);
  }
  scanf("%d",&q);
  while(q--){
    int op,x,ans;
    scanf("%d%d",&op,&x);
    if(op==1){
      ans=st1[x].size();
      for(auto y:st1[x]){
        st2[y].erase(x);
      }
      st1[x].clear();
    }
    else{
      ans=st2[x].size();
      for(auto y:st2[x]){
        st1[y].erase(x);
      }
      st2[x].clear();
    }
    printf("%d\n",ans);
  }
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...