题解
把美丽看成 1+有多少相邻的不同的连接块 这样就能贡献来做了
code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[100005];
void solve()
{
ll n,q;
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>a[i];
ll ans=n*(n+1)/2;
for(ll i=1;i<n;i++)
{
ans+=(a[i]!=a[i+1])*i*(n-i);
}
//cout<<ans<<'\n';
while(q--)
{
ll x,v;
cin>>x>>v;
if(x>1) ans-=(a[x]!=a[x-1])*(x-1)*(n-x+1);
if(x<n) ans-=(a[x]!=a[x+1])*(x)*(n-x);
a[x]=v;
if(x>1) ans+=(a[x]!=a[x-1])*(x-1)*(n-x+1);
if(x<n) ans+=(a[x]!=a[x+1])*(x)*(n-x);
cout<<ans<<'\n';
}
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t=1;
//cin>>t;
while(t--) solve();
return 0;
}
标签:题解,ll,long,Monoblock,solve,ans
From: https://www.cnblogs.com/pure4knowledge/p/18327956