题解都看了半天才懂

Problem - C - Codeforces

题意：

 

思路：

一开始的思路是这样的：

 

只能说，想到了更换枚举对象，然后组合数学算贡献

也想到了修改操作与（a[i]和a[i-1]）有关

但是我想的是枚举区间长度，然后对于每个长度len计算贡献

对于相邻的len-1和len，贡献能不能O(1)或O(logn)计算

事实上枚举的对象都错了

应该去枚举的是每个端点包含的所有区间的贡献

先去考虑怎么计算初始价值

如果a[i]!=a[i-1]，那么加上i左边的所有端点1~i对应的所有区间贡献都，即+=i

否则总贡献就加上[i,i]这个区间对应的贡献，即+1

然后去考虑每次修改对总贡献的影响

Code：

#include <bits/stdc++.h>#define int long longusing namespace std;const int mxn=2e5+10;int N,Q,x,y;
int a[mxn];void solve(){cin>>N>>Q;for(int i=1;i<=N;i++) cin>>a[i];a[0]=-1;int ans=1,sum=1;for(int i=2;i<=N;i++){sum+=(a[i]==a[i-1])?1:i;ans+=sum;}while(Q--){cin>>x>>y;if(a[x]==y){cout<<ans<<'\n';continue;}if(y==a[x-1]){ans-=(x-1)*(N-x+1);}else if(a[x]==a[x-1]){ans+=(x-1)*(N-x+1);}if(y==a[x+1]){ans-=x*(N-x);}else if(a[x]==a[x+1]){ans+=x*(N-x);}a[x]=y;cout<<ans<<'\n';}
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;//cin>>__;while(__--)solve();return 0;
}