C++差分数组

[AHOI2024 初中组] 操作

题目描述

小可可有一个数组 { a n } \{a_n\} {an​}（初始值为 { a n } = { 0 , 0 , … , 0 } \{a_n\}=\{0,0,\ldots,0\} {an​}={0,0,…,0}）和从左到右的 $m$ 个机器，其中第 $i$ 个机器有类别 o i ∈ { 1 , 2 } o_i \in \{1,2\} oi​∈{1,2} 和参数 $x_i,y_i$。第 $i$ 个机器执行的操作如下：

• 若 $o_i=1$，则将 $a_{(x_i)}$ 加上 $y_i$，此时保证 $1\le x_i\le n$，$1\le y_i\le 10^4$。
• 若 $o_i=2$，则执行第 $x_i\sim y_i$ 个机器的操作各一次，此时保证 $1\le x_i\le y_i\le i-1$。
• 特别地，保证 $o_1=1$。

现在，小可可依次执行了第 $c_1,c_2,\dots ,c_k$ 个机器的操作各一次，她想知道最后得到的数组 { a n } \{a_n\} {an​} 是什么。

由于数组中元素的值可能很大，你只需要帮她求出每个元素除以 $10007$ 的余数即可。

输入格式

第一行三个正整数 $n,m,k$。

接下来一行 $k$ 个正整数 { c k } \{c_k\} {ck​}。

接下来 $m$ 行，第 $i$ 行三个正整数 $o_i,x_i,y_i$。

输出格式

一行 $n$ 个非负整数，表示数组 { a n } \{a_n\} {an​} 中每个元素的值除以 $10007$ 的余数。

样例 #1

样例输入 #1

2 3 3
1 2 3
1 1 2
2 1 1
2 1 2

样例输出 #1

8 0

提示

样例 1 解释

先执行第 $1$ 个机器的操作，给 $a_1$ 加上了 $2$。

然后执行第 $2$ 个机器的操作，它操作了第 $1$ 个机器，给 $a_1$ 加上了 $2$。

然后执行第 $3$ 个机器的操作。它先操作了第 $1$ 个机器，给 $a_1$ 加上了 $2$；然后操作了第 $2$ 个机器，第 $2$ 个机器又操作了第 $1$ 个机器，给 $a_1$ 加上了 $2$。

综上所述，最后得到的数组为 { 8 , 0 } \{8,0\} {8,0}。

数据范围

对于 $10\%$ 的数据，$n,m,k\le 10$。

对于 $30\%$ 的数据，$n,m,k\le 1000$。

对于另外 $20\%$ 的数据，$n=1$。

对于另外 $20\%$ 的数据，$k=1$。

对于 $100\%$ 的数据，$1\le n,m,k\le 2\times 10^5$，$1\le c_i\le n$， o i ∈ { 1 , 2 } o_i \in \{1,2\} oi​∈{1,2}，$o_1=1$。此外，对于第 $i$ 个机器，保证：

• 若 $o_i=1$，则 $1\le x_i\le n$，$1\le y_i\le 10^4$。
• 若 $o_i=2$，则 $1\le x_i\le y_i\le i-1$。

差分数组

i<j 机器j可能调用机器i，反之则不会。故从大到小枚举，可以保证无后效性。调用机器x，vDiff[x]++,vDiff[x-1]–。
调用机器[x,y]，vDiff[y]++,vDiff[x-1]–。
cur = 0
for i = n to 1
cur += vDiff[i]
如果第i个机器是类型一,a[x] += y*cur
如果是类型二，vDiif[y] += cur,vDiff[x-1] -= cur

代码

核心代码

#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 <math.h>
#include <climits>
#include<assert.h>
#include<cstring>

#include <bitset>
using namespace std;

template<class T1, class T2>
std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {
	in >> pr.first >> pr.second;
	return in;
}

template<class T1, class T2, class T3 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {
	in >> get<0>(t) >> get<1>(t) >> get<2>(t) ;
	return in;
}

template<class T1, class T2, class T3, class T4 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {
	in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);
	return in;
}

template<class T = int>
vector<T> Read() {
	int n;
	scanf("%d", &n);
	vector<T> ret(n);
	for(int i=0;i < n ;i++) {
		cin >> ret[i];
	}
	return ret;
}

template<class T = int>
vector<T> Read(int n) {
	vector<T> ret(n);
	for (int i = 0; i < n; i++) {
		cin >> ret[i];
	}
	return ret;
}

template<int MOD = 1000000007>
class C1097Int
{
public:
	C1097Int(long long llData = 0) :m_iData(llData% MOD)
	{

	}
	C1097Int  operator+(const C1097Int& o)const
	{
		return C1097Int(((long long)m_iData + o.m_iData) % MOD);
	}
	C1097Int& operator+=(const C1097Int& o)
	{
		m_iData = ((long long)m_iData + o.m_iData) % MOD;
		return *this;
	}
	C1097Int& operator-=(const C1097Int& o)
	{
		m_iData = (m_iData + MOD - o.m_iData) % MOD;
		return *this;
	}
	C1097Int  operator-(const C1097Int& o)
	{
		return C1097Int((m_iData + MOD - o.m_iData) % MOD);
	}
	C1097Int  operator*(const C1097Int& o)const
	{
		return((long long)m_iData * o.m_iData) % MOD;
	}
	C1097Int& operator*=(const C1097Int& o)
	{
		m_iData = ((long long)m_iData * o.m_iData) % MOD;
		return *this;
	}
	C1097Int  operator/(const C1097Int& o)const
	{
		return *this * o.PowNegative1();
	}
	C1097Int& operator/=(const C1097Int& o)
	{
		*this /= o.PowNegative1();
		return *this;
	}
	bool operator==(const C1097Int& o)const
	{
		return m_iData == o.m_iData;
	}
	bool operator<(const C1097Int& o)const
	{
		return m_iData < o.m_iData;
	}
	C1097Int pow(long long n)const
	{
		C1097Int iRet = 1, iCur = *this;
		while (n)
		{
			if (n & 1)
			{
				iRet *= iCur;
			}
			iCur *= iCur;
			n >>= 1;
		}
		return iRet;
	}
	C1097Int PowNegative1()const
	{
		return pow(MOD - 2);
	}
	int ToInt()const
	{
		return (m_iData + MOD) % MOD;
	}
private:
	int m_iData = 0;;
};

class Solution {
	typedef  C1097Int<10007> BI;
public:
	vector<int> Ans(int N, vector<int>& a, vector<tuple<int, int, int>>& b) {
		const auto M = b.size();
		b.insert(b.begin(), make_tuple(0, 0, 0));
		vector<BI> diff(M + 1);
		for (const auto& i : a) {
			diff[i] += 1; diff[i - 1] -= 1;
		}
		vector<BI> bans(N + 1);
		BI cur = 0;
		for (int i = M; i >= 1; i--) {
			cur += diff[i];
			const auto& [o, x, y] = b[i];
			if (1 == o) {
				bans[x] += BI(y) * cur;
			}
			else {
				diff[y] += cur; diff[x - 1] -= cur;
			}
		}
		vector<int> ans;
		for (int i = 1; i <= N; i++) {
			ans.emplace_back(bans[i].ToInt());
		}
		return ans;
	}
};

int main() {
#ifdef _DEBUG
	freopen("a.in", "r", stdin);
#endif // DEBUG	
	int n,m,k;
	cin >> n >> m >> k ;
	auto a = Read<int>(k);
	auto b = Read<tuple<int, int, int>>(m);	
#ifdef _DEBUG	
	//printf("N=%d", n);
	//Out(a, ",a=");
	//Out(b, ",b=");
#endif	
	auto res = Solution().Ans(n,a,b);
	for (auto i : res)
	{
		cout << i << " ";
	}
	return 0;
}

单元测试

int N;
		vector<int> a;
		vector<tuple<int,int,int>> b;
		TEST_METHOD(TestMethod11)
		{
			N = 2, a = { 1,2,3 }, b = { {1,1,2},{2,1,1},{2,1,2} };
			auto res = Solution().Ans(N, a, b);
			AssertEx({ 8,0 }, res);
		}

扩展阅读

计算几何为骨，排样优化为魂
作品：亲士CAD工具箱
经典文章推荐：二维排样
万物皆数学
查阅鄙人的博文，请点击博文下载学院导航
活到老，学到老。明朝中后期，大约50%的进士能当上堂官(副部及更高)；能当上堂官的举人只有十余人。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。