提出 #76482666

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAX=3e5+10;
int treeR[MAX],treeC[MAX],lastR[MAX],lastC[MAX];
int n,q;

void add(int tree[],int index,int value){
    while(index<=q){
        tree[index]+=value;
        index+=(index&-index);
    }
}

int sum(int tree[],int index){
    int total=0;
    while(index>0){
        total+=tree[index];
        index-=(index&-index);
    }
    return total;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>q;
    ll totalBlack=0;
    for(int i=1;i<=q;i++){
        int type,x;
        cin>>type>>x;
        if(type==1){
            int oldTime=lastR[x];
            if(oldTime==0){
                totalBlack+=n;
            }
            else{
                int whiteCols=sum(treeC,q)-sum(treeC,oldTime);
                totalBlack+=whiteCols;
                add(treeR,oldTime,-1);
            }
            lastR[x]=i;
            add(treeR,i,1);
        }
        else if(type==2){
            int oldTime=lastC[x];
            int blackRows=sum(treeR,q)-sum(treeR,oldTime);
            totalBlack-=blackRows;
            if(oldTime>0){
                add(treeC,oldTime,-1);
            }
            lastC[x]=i;
            add(treeC,i,1);
        }
        cout<<totalBlack<<"\n";
    }
}

提出情報

ジャッジ結果