原题链接题解把美丽看成1+有多少相邻的不同的连接块这样就能贡献来做了code#include<bits/stdc++.h>#definelllonglongusingnamespacestd;lla[100005];voidsolve(){lln,q;cin>>n>>q;for(inti=1;i<=n;i++)cin>>a[i];llans=n*(n+1)/

题目：​ 给出长度为n的序列，计算其所有子段的答案和\((\sum_{l=1}^{n}\sum_{r=l}^ng(l,r))\)。对于子段\([l,r]\)的计算公式\(g(l,r)\)=l到r之间合并后的块数。​ 合并

思路根据题意我们不难看出，求一个区间的块的数量即求区间内\(a_i\neqa_{i-1}\)的数量，如果直接枚举每个区间的话，时间复杂度是\(\mathcalO(n^2)\)显然这样做是不行的，但

Monoblockdp先想想如何计算初始值\(dp[x]\)表示以第\(x\)个位置为\(r\)，他的所有贡献状态转移：如果\(a_x=a_{x-1}\)：\(dp[x]=dp[x-1]+1\)，代表只增加了\(l