题解 | #不点两面(hard version)#

这题核心就一句：
一个数字 x 安不安全，只看牌河里有没有 x-3 或 x+3，和张数本身没关系。

所以我们维护两类信息：

• c[v]：牌河里数字 v 现在有几张（多重集合计数）。
• s[x]：当前有多少个“活跃数字”在保护 x。
  也就是有多少个 v 满足 v-3=x 或 v+3=x 且 c[v]>0。

再维护一个总答案 ans，表示当前有多少个 x 满足 s[x]>0（即安全牌种数）。

每次操作只会影响两个位置：num-3 和 num+3，所以可以做到 O(1) 更新。

1）加入一张 num

• 如果 c[num] 原来是 0，说明这个数字从“不活跃”变“活跃”，它会新保护：
  • num-3
  • num+3
• 对这两个位置做 s[x]++：
  • 若 s[x] 从 0 变 1，ans++
• 最后 c[num]++

如果 c[num] 原来就大于 0，这次加入不会新增保护范围，不用改 s。

2）移出一张 num

• 先 c[num]--
• 只有当 c[num] 从 1 变 0 时，num 才从“活跃”变“不活跃”，它对
  • num-3
  • num+3 的保护需要取消
• 对这两个位置做 s[x]--：
  • 若 s[x] 从 1 变 0，ans--

边界上注意一下：num-3 或 num+3 可能不在 [1,m]，这种直接忽略。

复杂度

• 每次操作最多改 2 个位置，时间 O(1)
• 总时间 O(q)
• 空间 O(m)

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

using ll=long long;
using ull=unsigned long long;
using ld=long double;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vvi=vector<vector<int>>;
using vll=vector<ll>;
using vvll=vector<vector<ll>>;
using vc=vector<char>;
using vs=vector<string>;
using vb=vector<bool>;
using vpii=vector<pii>;
using vpll=vector<pll>;

const int INF=1e9;
const ll LINF=4e18;
const int MOD=1e9+7;
const int MOD2=998244353;

#define IOS ios::sync_with_stdio(false); cin.tie(nullptr);
#define endl '\n'
#define all(x) x.begin(),x.end()
#define ral(x) x.rbegin(),x.rend()
#define fi first
#define se second
#define fix(x) fixed<<setprecision(x)

ll gcd(ll a,ll b){
	return b?gcd(b,a%b):a;
}
ll lcm(ll a,ll b){
	return a/gcd(a,b)*b;
}

ll qpow(ll a,ll b,ll mod=MOD){
	ll res=1;
	a%=mod;
	while(b){
		if(b&1)res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}

ll modinv(ll a,ll p=MOD){
	return qpow(a,p-2,p);
}

struct Node{
	int a,b;
	
	bool operator<(const Node &y)const{
		return b>y.b;
	}
};

void solve(){
    int m,q;cin>>m>>q;
    vi c(m+1),s(m+1);
    int ans=0;
    auto add=[&](int x){
        if(x<1||x>m)return;
        if(s[x]==0)++ans;
        ++s[x];
    };
    auto del=[&](int x){
        if(x<1||x>m)return;
        --s[x];
        if(s[x]==0)--ans;
    };
    for(int i=1;i<=q;++i){
        int op,num;cin>>op>>num;
        if(op==1){
            if(c[num]==0){
                add(num-3);
                add(num+3);
            }
            ++c[num];
        }else{
            --c[num];
            if(c[num]==0){
                del(num-3);
                del(num+3);
            }
        }
        cout<<ans<<endl;
    }
}

int main(){
	IOS;
	int _=1;//cin>>_;
	while(_--){
		solve();
	}
	return 0;
}