【组合数学算贡献+枚举】CF816div2 C. Monoblock

女爷i 2024-03-22 11:36 70阅读 0赞

题解都看了半天才懂

[Problem - C - Codeforces][]

题意：

![82342572fc4d4cdd8ad06219e506c00a.png][]

![0f15d41a24714a42b7d0ff7fe95b1b5c.png][]

思路：

一开始的思路是这样的：

![442a88957f074576a3d7bb3dfb3dbf4a.jpeg][]

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

也想到了修改操作与（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

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

![8e2d36578880428aaa3aaab728f8d034.png][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using 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;
    }

[Problem - C - Codeforces]: https://codeforces.com/contest/1715/problem/C
[82342572fc4d4cdd8ad06219e506c00a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/b3a60ff26a2f4560836fc53426dab47f.png
[0f15d41a24714a42b7d0ff7fe95b1b5c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/5bd6c2e8d45340c2ba4a763b21d27c0a.png
[442a88957f074576a3d7bb3dfb3dbf4a.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/3060a2b3118845e389be1b7e6e37a48a.png
[8e2d36578880428aaa3aaab728f8d034.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/704a66069f5b423383ead691ec430f32.png