题解：AT_abc406_d [ABC406D] Garbage Removal

jess1ca1o0g3 · 2025-05-18 13:37:31 · 题解

D 严格小于 C。

思路

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

代码

#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);
  }
}