本文涉及知识点

C++差分数组

洛谷 P3655不成熟的梦想家

某团队共有N+1人，第i个人的唱歌是a[i]。
某机器人将a[i1…i2]全部+z，z可以是负数。
我们可以使用这个机器人Q次，第i次数据为use[i] = {i1,i2,z}。
S和T是常数，各成员的魅力值为b[i]：
b[0]=0
如果a[i-1]小于a[i]则：b[i] = S$\times$( a[i-1]-a[i])
否则：b[i] = T$\times$(a[i-1]-a[i])
队伍的魅力值B等于b[i]之和。
N,Q <= 2e5 1 <= a[i],S,T <=1e6 |z|<=1e6
1 <=x,y <=1e6

差分数组

b[i]之和a[i]和a[i-1]有关。
如果a[i]和a[i-1]都没变，则b[i]也不变。
如果a[i]和a[i-1]都增加z，则b[i]也不变。
只有两种情况要处理：
a[i1]增加，a[i1-1]没变。
a[i2+1]不边，a[i2]增加
很容易想到的是：我们实时维护数组a的值， 减去操作之前的b[i]，加上操作之后的b[i]。实时维护数组a的时间复杂度是：O(nn)，超时。
改进思路：我们不需要记录a[i]，只需要记录dfff[i] ,即diff[0]等于任意值，比如0。i>0，diff[i]=diff[i]-diff[i-1]。也就是差分数组

代码

核心代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>

#include <bitset>
using namespace std;

class Solution {
public:
	vector<long long> Cal(long long S,long long T,const vector<int>& a, const vector<vector<int>>& add) {
		const int N = a.size();
		vector<long long> diff(N + 1);
		long long b = 0;
		auto Cal = [&](long long diff) {
			if (diff > 0) {
				return -S * diff;
			}
			return -T * diff;
		};
		for (int i = 1; i < N; i++) {
			diff[i] = a[i] - a[i - 1];
			b += Cal(diff[i]);
		}
		vector<long long> ret;
		for (const auto& v : add ) {
			long long llAdd = 0;
			llAdd -= Cal(diff[v[0]]);
			diff[v[0]] += v[2];
			llAdd += Cal(diff[v[0]]);
			const int end = v[1] + 1;
			if (end < N) {
				llAdd -= Cal(diff[end]);
				diff[end] -= v[2];
				llAdd += Cal(diff[end]);
			}
			b += llAdd;
			ret.emplace_back(b);
		}	
		return ret;
	}
};

int main() {


	int N,Q,S,T;
	scanf("%d%d%d%d", &N, & Q, & S, & T);
	vector<int> a(N + 1);	
	vector<vector<int>> add(Q, vector<int>(3));
	for (int i = 0; i < N+1; i++) {
		scanf("%d", &a[i]);
	}
	for (int i = 0; i < Q; i++) {
		scanf("%d%d%d", &add[i][0],&add[i][1],&add[i][2]);
	}
	//Out(moves);
	auto res =  Solution().Cal(S,T,a,add);
	for (auto n : res) {
		printf("%lld\n", n);
	}
	return 0;
}

单元测试

int S,T;
		vector<vector<int>> add;
		vector<int> a;
		TEST_METHOD(TestMethod1)
		{
			S = 2, T = 3, a = { 0,1,2 }, add = { {1,1,1}, {2,2,-1 }, {1,2,3 } };
			auto res = Solution().Cal(S, T, a, add);
			AssertEx(vector<long long>{-4, -1,-7}, res);
		}
		TEST_METHOD(TestMethod2)
		{
			S = 2, T = 3, a = { 0,2,1 }, add = { {1,1,1}, {2,2,-1 }, {1,2,3 } };
			auto res = Solution().Cal(S, T, a, add);
			AssertEx(vector<long long>{0, 3, -3}, res);
		}
		TEST_METHOD(TestMethod11)
		{
			S=2,T=3, a={ 0,5,2,4,6 },add= { {1, 2, 1}, { 3,4,-3 }, { 1,4,2 }};
			auto res = Solution().Cal(S,T,a,add);
			AssertEx(vector<long long>{-9,-1,-5}, res);
		}