题解：P14379 【MX-S9-T2】「LAOI-16」摩天大楼

Lysra · 2025-11-02 20:03:57 · 题解

作个充要转化，求以下区间个数：

• 不含 1。

• 以 1 为两端且不含 2。

第一个直接 set 存所有 1 的位置每次暴力修改，第二个再写个 set 存所有 2 的位置，配合 BIT 维护 1 的位置即可维护。

#include<bits/stdc++.h>
#define int long long
#define N 1000005
#define INF 1e18
#define lb(x) (x&(-x))
using namespace std;
int n,q,k,a[N],ans,t[N],lst;
set<int>s1,s2;
set<int>::iterator it,itl,itr;
void add(int x,int y){
    for(int i=x;i<=n+1;i+=lb(i)) t[i]+=y;
}
int query(int x){
    int res=0;
    for(int i=x;i;i-=lb(i)) res+=t[i];
    return res;
}
signed main(){
    ios::sync_with_stdio(false);
    cin>>n>>q,ans=n*(n-1)/2;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]==1) s1.insert(i),add(i,1);
        if(a[i]==2) s2.insert(i);
    }
    s1.insert(0),s1.insert(n+1);
    s2.insert(0),s2.insert(n+1);
    for(int val:s1){
        if(!val) continue;
        ans-=(val-lst-1)*(val-lst-2)/2,lst=val;
    }
    lst=0;
    for(int val:s2){
        if(!val) continue;
        k=query(val)-query(lst);
        ans-=k*(k-1)/2,lst=val;
    }
    int x,v;
    while(q--){
        cin>>x>>v;
        if(a[x]==v){
            cout<<ans<<endl;
            continue;
        }
        if(a[x]==1){
            itr=s2.lower_bound(x),itl=itr,itl--;
            k=query(*itr)-query(*itl),ans+=k*(k-1)/2,add(x,-1);
            k=query(*itr)-query(*itl),ans-=k*(k-1)/2;
            it=s1.find(x),itr=it,itl=it,itl--,itr++;
            ans+=((*it)-(*itl)-1)*((*it)-(*itl)-2)/2;
            ans+=((*itr)-(*it)-1)*((*itr)-(*it)-2)/2;
            ans-=((*itr)-(*itl)-1)*((*itr)-(*itl)-2)/2;
            s1.erase(it);
        }
        if(a[x]==2){
            it=s2.find(x),itr=it,itl=it,itl--,itr++;
            k=query(*itr)-query(*it),ans+=k*(k-1)/2;
            k=query(*it)-query(*itl),ans+=k*(k-1)/2;
            k=query(*itr)-query(*itl),ans-=k*(k-1)/2;
            s2.erase(it);
        }
        if(v==1){
            itr=s2.lower_bound(x),itl=itr,itl--;
            k=query(*itr)-query(*itl),ans+=k*(k-1)/2,add(x,1);
            k=query(*itr)-query(*itl),ans-=k*(k-1)/2;
            s1.insert(x);
            it=s1.find(x),itr=it,itl=it,itl--,itr++;
            ans+=((*itr)-(*itl)-1)*((*itr)-(*itl)-2)/2;
            ans-=((*it)-(*itl)-1)*((*it)-(*itl)-2)/2;
            ans-=((*itr)-(*it)-1)*((*itr)-(*it)-2)/2;
        }
        if(v==2){
            s2.insert(x);
            it=s2.find(x),itr=it,itl=it,itl--,itr++;
            k=query(*itr)-query(*it),ans-=k*(k-1)/2;
            k=query(*it)-query(*itl),ans-=k*(k-1)/2;
            k=query(*itr)-query(*itl),ans+=k*(k-1)/2;
        }
        a[x]=v,cout<<ans<<endl;
    }
    return 0;
}