题解：AT_abc466_d [ABC466D] Placing Rooks

题意分析网格NNN行NNN列初始无棋子共MMM次操作每次操作三步1.清空第RiR_iRi​行所有棋子2.清空第CiC_iCi​列所有棋子3.在(Ri,Ci)(R_i,C_i)(Ri​,Ci​)放一枚棋子。求最终网格上有多少棋子。思路对于第kkk次操作放在(Rk,Ck)(R_k, C_k)(Rk​,Ck​)上的棋子要想保留则RkR_kRk​和CkC_kCk​后续都不能被清空。于是很容易想到用l[x]l[x]l[x]表示最后一次操作第xxx行的时间r[y]r[y]r[y]表示最后一次操作第yyy列的时间。然后遍历每一次操作如果l[Ri]l[R_i]l[Ri​]的值等于该次操作r[Ci]r[C_i]r[Ci​]的值也等于该次操作即后续没有对第RiR_iRi​行和第CiC_iCi​列清空所以棋子数增加一。代码#includebits/stdc.husingnamespacestd;constintN3e55,M3e55;intn,m,cnt,qr[M],qc[M],l[N],r[N];intmain(){cinnm;for(inti1;im;i){cinqr[i]qc[i];l[qr[i]]i,r[qc[i]]i;// 记录最后一次操作时间}for(inti1;im;i){if(l[qr[i]]ir[qc[i]]i){cnt;// 如果后续没有操作,棋子数增加}}coutcnt;return0;}