提出 #76482967

---

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;
#define ll long long

struct Fenwick{
    int n;
    vector<ll> bit;
    Fenwick(int n_):n(n_),bit(n_+2,0){}

    void add(int i,ll x){
        i ++;
        while(i <= n+1){
            bit[i] += x;
            i += i&-i;
        }
        return ;
    }
    ll sum(int i){
        if(i < 0){
        	return 0;	
		}
        i ++;
        ll res = 0;
        while(i > 0){
            res += bit[i];
            i -= i&-i;
        }
        return res;
    }
    ll range(int l,int r){
        if(l > r){
        	return 0;
		}
        return sum(r)-sum(l-1);
    }
};

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,q;
    cin>>n>>q;
    Fenwick row(q+2),col(q+2);
    vector<int> rt(n+1,0);
    vector<int> ct(n+1,0);
    row.add(0, n);
    col.add(0, n);
    ll ans = 0;
    for(int t=1;t<=q;t++){
        int op,x;
        cin>>op>>x;
        if(op == 1){
            int old = rt[x];
            if(old != 0){
                ans -= col.sum(old-1);
            }
            row.add(old,-1);
            rt[x] = t;
            row.add(t,1);
            ans += col.sum(t-1);
        }
		else{
            int old = ct[x];
            if(old != 0){
                ans -= (row.sum(q+1)-row.sum(old));
            }
			else{
                ans -= (row.sum(q+1)-row.sum(0));
            }
            col.add(old,-1);
            ct[x] = t;
            col.add(t,1);
            ans += (row.sum(q+1)-row.sum(t));
        }
        cout<<ans<<'\n';
    }
    return 0;
}

提出情報

ジャッジ結果