UAPC 2011 F Cosmic Market

問題

r行c列の座席に人が最初座っている。
q個の命令が来る。

• i行目の人を立たせる（or座らせる）
• i列目の人を立たせる（or座らせる）

命令が着たときに既に立っていたり座っていたりした人はそのまま。
最後に立っている人の数を求める。

方針

シミュレートでは間に合わない。
クエリを逆から見る。
すると、一度操作をした列に関しては立つor座るの状態が変化することはない。

なので、新しく立つ人の人数がすぐに求まる。

int h,w,q;
int a[50000],b[50000],o[50000];
bool row[50000],col[50000];
int main(){
  while(cin>>h>>w>>q,h){
    rep(i,q)cin>>a[q-i-1]>>b[q-i-1]>>o[q-i-1];
    memset(row,0,sizeof(row)); memset(col,0,sizeof(col));
    ll ans=0;
    int nrow=0, ncol=0;
    rep(i,q){
      if(a[i]==0){
        if(row[b[i]])continue;
        row[b[i]]=1; nrow++;
        if(o[i])ans+=w-ncol;
      }
      else{
        if(col[b[i]])continue;
        col[b[i]]=1; ncol++;
        if(o[i])ans+=h-nrow;
      }
    }
    cout<<ans<<endl;
  }
  return 0;
}