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

#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;
}