CF1744B Even-Odd Increments

简要题意

\(T\) 组数据，每组数据给定一个长度为 \(n\) 的数列，有 \(q\) 次操作，共有两种操作：

• \(\texttt{0 x}\)，给数列中所有偶数加上 \(x\)；
• \(\texttt{1 x}\)，给数列中所有奇数加上 \(x\);

每一次操作结束后，输出数列的和。

\(1 \leq T \leq 10^{4},1 \leq n,q \leq 10^{5}\)

思路

相当巧妙的一道思维题。

首先，如果直接暴力搞貌似不太行，线段树太难写，而且也没有区间操作。

其实这道题有一个更简单的做法，首先，如果 \(x\) 时奇数，那么在 \(0\) 操作中所有数都会变成偶数，在 \(1\) 操作中所有数都会变成奇数。（因为奇数加奇数为偶数，奇数加偶数为奇数，偶数加偶数为偶数）。再维护一个全局和，你发现就可以 \(O(1)\) 操作了。

整体时间复杂度 \(O(T(n+q))\)。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

int odd,even,sum,n,q,a[100005];

void solve(){
	odd=0;even=0;sum=0;
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum += a[i];
		if(a[i]&1)odd++;
		else even++;
	}
	while(q--){
		int op,x;
		cin>>op>>x;
		if(op==0){
			sum += even*x;
			if(x&1){
				odd=n;
				even=0;
			}
		}
		else{
			sum += odd*x;
			if(x&1){
				even=n;
				odd=0;
			}
		}
		cout<<sum<<'\n';
	}
}

signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int t;cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

原文地址：http://www.cnblogs.com/zheyuanxie/p/cf1744b.html