首页 > 其他分享 >C. Monoblock

C. Monoblock

时间:2024-07-28 10:39:28浏览次数:11  
标签:题解 ll long Monoblock solve ans

原题链接

题解

把美丽看成 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

相关文章

  • C. Monoblock(贡献 子段) CF 1715C
    题目:​ 给出长度为n的序列,计算其所有子段的答案和\((\sum_{l=1}^{n}\sum_{r=l}^ng(l,r))\)。对于子段\([l,r]\)的计算公式\(g(l,r)\)=l到r之间合并后的块数。​ 合并......
  • CF1715C Monoblock 题解
    思路根据题意我们不难看出,求一个区间的块的数量即求区间内\(a_i\neqa_{i-1}\)的数量,如果直接枚举每个区间的话,时间复杂度是\(\mathcalO(n^2)\)显然这样做是不行的,但......
  • CodeForces-1715C Monoblock
    Monoblockdp先想想如何计算初始值\(dp[x]\)表示以第\(x\)个位置为\(r\),他的所有贡献状态转移:如果\(a_x=a_{x-1}\):\(dp[x]=dp[x-1]+1\),代表只增加了\(l......