C. Monoblock（贡献 子段） CF 1715C

题目：

​ 给出长度为n的序列，计算其所有子段的答案和\((\sum_{l=1}^{n}\sum_{r=l}^n g(l, r))\)。对于子段\([l, r]\)的计算公式\(g(l, r)\)=l到r之间合并后的块数。
​ 合并：对于\(i\) \((2 <= n)\)，若\(a_i = a_i-1\)，他们可以被看做是同一块。

分析：

​ 可以通过\(n^2\)的暴力计算得到答案，但是这样做时间复杂度会非常高，所以我们要想办法优化。由于每次只对一个数值进行修改，所以很容易将思维转化到计算贡献上。我们一开始可以用\(O(n)\)来预处理出初始状态的答案，然后对于每一次的修改，我们要对其进行贡献的修正，若是原本是相同，改后是不相同，那就要加上贡献，若是原本不相同，改后相同，那就要减去贡献。对于一个位置上的修改，要考虑修改前后他与左右的关系。

实现：

​ 那么我们已经得到了一个思路，但是计算贡献又是一个难题。对于初始状态来说，假设现在整段都是1，那么他的贡献为\(\sum_{i=1}^{n}i\)，那么当\(a_i\)和\(a_{i-1}\)不同的时候，\(l\)的取值范围是\([1, i - 1]\)，\(r\)的取值范围是\([i,n]\)，那么这对数对于\((i-1)*(n-i+1)\)个子段贡献+1。那么初始化就做好了。

​ 接下来看修改的部分，若\(i\)被修改的时候，分别讨论左和右的情况，计算其影响的子段数量，从而得到总贡献的增减情况。

#include <bits/stdc++.h>
    
using namespace std;
#define rep(i, a, n) for(int i = a; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define ios ios::sync_with_stdio(false);cin.tie(0);
#define debug(x)    cout << x << endl;
#define SZ(x)    (int)x.size()
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;
void read(int &x) {int s = 0, f = 1; char ch = getchar(); while(!isdigit(ch)) {f = (ch == '-' ? -1 : f); ch = getchar();} while(isdigit(ch)) {s = s * 10 + ch - '0'; ch = getchar();} x = s * f;}

const int N = 100005;
int n, m;
int a[N];
LL res = 0;

void init()
{
    for(int i = 2; i <= n; i ++)
        if(a[i - 1] != a[i])
            res += 1ll * (i - 1) * (n - i + 1);
}

signed main()
{
    scanf("%d%d", &n, &m);
    res = 1ll * n * (n + 1) / 2; //初始贡献
    for(int i = 1; i <= n; i ++)
        scanf("%d", &a[i]);
    init(); //初始化贡献

    while(m --)
    {
        int idx, val;
        scanf("%d%d", &idx, &val);
        if(idx > 1 && a[idx] != a[idx - 1])
            res -= 1ll * (idx - 1) * (n - idx + 1);
        if(idx < n && a[idx] != a[idx + 1])
            res -= 1ll * idx * (n - idx);
        a[idx] = val; 
        if(idx > 1 && a[idx] != a[idx - 1])
            res += 1ll * (idx - 1) * (n - idx + 1);
        if(idx < n && a[idx] != a[idx + 1])
            res += 1ll * idx * (n - idx);
        printf("%lld\n", res);
    }   
}