当前位置：首页 > backend >正文

【线段树】3525. 求出数组的 X 值 II|2645

backend 2025/9/3 16:11:10

本文涉及知识点

C++线段树

3525. 求出数组的 X 值 II

给你一个由正整数组成的数组 nums 和一个正整数 k。同时给你一个二维数组 queries，其中 queries[i] = [indexi, valuei, starti, xi]。
你可以对 nums 执行一次操作，移除 nums 的任意后缀，使得 nums 仍然非空。
给定一个 x，nums 的 x值定义为执行以上操作后剩余元素的乘积除以 k 的余数为 x 的方案数。
对于 queries 中的每个查询，你需要执行以下操作，然后确定 xi 对应的 nums 的 x值：
将 nums[indexi] 更新为 valuei。仅这个更改在接下来的所有查询中保留。
移除前缀 nums[0…(starti - 1)]（nums[0…(-1)] 表示空前缀）。
返回一个长度为 queries.length 的数组 result，其中 result[i] 是第 i 个查询的答案。
数组的一个前缀是从数组开始位置到任意位置的子数组。
数组的一个后缀是从数组中任意位置开始直到结束的子数组。
子数组是数组中一段连续的元素序列。
注意：操作中所选的前缀或后缀可以是空的。
注意：x值在本题中与问题 I 有不同的定义。
示例 1：
输入： nums = [1,2,3,4,5], k = 3, queries = [[2,2,0,2],[3,3,3,0],[0,1,0,1]]
输出： [2,2,2]
解释：
对于查询 0，nums 变为 [1, 2, 2, 4, 5] 。移除空前缀后，可选操作包括：
移除后缀 [2, 4, 5] ，nums 变为 [1, 2]。
不移除任何后缀。nums 保持为 [1, 2, 2, 4, 5]，乘积为 80，对 3 取余为 2。
对于查询 1，nums 变为 [1, 2, 2, 3, 5] 。移除前缀 [1, 2, 2] 后，可选操作包括：
不移除任何后缀，nums 为 [3, 5]。
移除后缀 [5] ，nums 为 [3]。
对于查询 2，nums 保持为 [1, 2, 2, 3, 5] 。移除空前缀后。可选操作包括：
移除后缀 [2, 2, 3, 5]。nums 为 [1]。
移除后缀 [3, 5]。nums 为 [1, 2, 2]。
示例 2：
输入： nums = [1,2,4,8,16,32], k = 4, queries = [[0,2,0,2],[0,2,0,1]]
输出： [1,0]
解释：
对于查询 0，nums 变为 [2, 2, 4, 8, 16, 32]。唯一可行的操作是：
移除后缀 [2, 4, 8, 16, 32]。
对于查询 1，nums 仍为 [2, 2, 4, 8, 16, 32]。没有任何操作能使余数为 1。
示例 3：
输入： nums = [1,1,2,1,1], k = 2, queries = [[2,1,0,1]]
输出： [5]
提示：
$1 <= nums[i] <= 10^9$
$1 <= nums.length <= 10^5$
1 <= k <= 5
$\times 10^4$
queries[i] == [indexi, valuei, starti, xi]
0 <= indexi <= nums.length - 1
$1 <= valuei <= 10^9$
0 <= starti <= nums.length - 1
0 <= xi <= k - 1

乘积线段树

线段树类型：单点修改静态开点。
每个节点(nums[left $⋯\cdots$ r]包括两个数据： $nums[left⋯r]的乘积modKnums[left\cdots r]的乘积 \mod K$ ,cnt[k]= y的数量。 $y=Πj=leftrnums[j]modKy=\Pi_{j=left}^r nums[j] \mod K$
单点修改无需处理缓存。直接更新叶子节点，通过子节点更新父节点。另外要写查询函数。

修改叶子节点

mul = $\mod K,cnt[0\cdots K-1]=0,cnt[mul]=1$

更新父节点

父节点的mul = 子节点的mul $modK\mod K$
父节点的cnt[i]= 子节点cnt[i]之和。

查询

mul =1
依次查询各节点:
如果mul是0,则结果一定是0，如果 $x_i$ 是0,ans += (r -left)+1 ，continue;
ans += cnt[ $xi÷mulx_i \div mul$ ] 注意：逆元可以提前算好。
mul =mul $×\times$ 当前节点的mul。

代码

核心代码

		template<long long MOD = 1000000007,class T1 = int, class T2 = long long>
class C1097Int
{
public:C1097Int(T1 iData = 0) :m_iData(iData% MOD){}C1097Int(T2 llData) :m_iData(llData% MOD) {}C1097Int  operator+(const C1097Int& o)const{return C1097Int(((T2)m_iData + o.m_iData) % MOD);}C1097Int& operator+=(const C1097Int& o){m_iData = ((T2)m_iData + o.m_iData) % MOD;return *this;}C1097Int& operator-=(const C1097Int& o){m_iData = ((T2)MOD + m_iData - o.m_iData) % MOD;return *this;}C1097Int  operator-(const C1097Int& o)const{return C1097Int(((T2)MOD + m_iData - o.m_iData) % MOD);}C1097Int  operator*(const C1097Int& o)const{return((T2)m_iData * o.m_iData) % MOD;}C1097Int& operator*=(const C1097Int& o){m_iData = ((T2)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(T2 n)const{C1097Int iRet = (T1)1, iCur = *this;while (n){if (n & 1){iRet *= iCur;}iCur *= iCur;n >>= 1;}return iRet;}C1097Int PowNegative1()const{return pow(MOD - 2);}T1 ToInt()const{return ((T2)m_iData + MOD) % MOD;}
private:T1 m_iData = 0;;
};
template<class TSave, class TRecord >
class CSingeUpdateLineTree
{
protected:virtual void OnQuery(TSave& ans,const TSave& cur, const int& iSaveLeft, const int& iSaveRight) = 0;virtual void OnUpdate(TSave& save, int iSaveIndex, const TRecord& update) = 0;virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) = 0;
};template<class TSave, class TRecord >
class CVectorSingUpdateLineTree : public CSingeUpdateLineTree<TSave, TRecord>
{
public:CVectorSingUpdateLineTree(int iEleSize, TSave tDefault) :m_iEleSize(iEleSize),m_save(iEleSize*4,tDefault), m_tDefault(tDefault){}void Update(int index, TRecord update) {Update(1, 0, m_iEleSize-1, index, update);}TSave Query(int leftIndex, int leftRight,TSave tDefault) {TSave ans = tDefault;Query(ans,1, 0, m_iEleSize - 1, leftIndex, leftRight);return ans;}TSave Query(int leftIndex, int leftRight) {		return Query(leftIndex,leftRight, m_tDefault);}void Init(std::function<void(TSave&,const int&)> fun) {Init(fun,1, 0, m_iEleSize - 1);}TSave QueryAll() {return m_save[1];}
protected:int m_iEleSize;void Init(std::function<void(TSave&, const int&)> fun,int iNodeNO, int iSaveLeft, int iSaveRight){if (iSaveLeft == iSaveRight) {fun(m_save[iNodeNO], iSaveLeft);return;}const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;Init(fun,iNodeNO * 2, iSaveLeft, mid);Init(fun,iNodeNO * 2 + 1, mid + 1, iSaveRight);this->OnUpdateParent(m_save[iNodeNO], m_save[iNodeNO*2], m_save[iNodeNO*2+1], iSaveLeft, iSaveRight);}void Query(TSave& ans,int iNodeNO, int iSaveLeft, int iSaveRight, int iQueryLeft, int iQueryRight) {if ((iSaveLeft >= iQueryLeft) && (iSaveRight <= iQueryRight)) {this->OnQuery(ans,m_save[iNodeNO],iSaveLeft,iSaveRight);return;}if (iSaveLeft == iSaveRight) {//没有子节点return;}const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;if (mid >= iQueryLeft) {Query(ans,iNodeNO * 2, iSaveLeft, mid, iQueryLeft, iQueryRight);}if (mid + 1 <= iQueryRight) {Query(ans,iNodeNO * 2 + 1, mid + 1, iSaveRight, iQueryLeft, iQueryRight);}}void Update(int iNodeNO, int iSaveLeft, int iSaveRight, int iUpdateNO, TRecord update) {if (iSaveLeft == iSaveRight){this->OnUpdate(m_save[iNodeNO], iSaveLeft, update);return;}const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;if (iUpdateNO <= mid) {Update(iNodeNO * 2, iSaveLeft, mid, iUpdateNO, update);}else {Update(iNodeNO * 2 + 1, mid + 1, iSaveRight, iUpdateNO, update);}this->OnUpdateParent(m_save[iNodeNO], m_save[iNodeNO*2], m_save[iNodeNO*2+1], iSaveLeft, iSaveRight);}vector<TSave> m_save;const TSave m_tDefault;
};typedef	C1097Int<> BI;class CData{public:CData() {}int mul = 1;int cnt[5] = { 0 };};template<class TSave = CData, class TRecord = int>class  CMyLineTree : public CVectorSingUpdateLineTree<TSave, TRecord>{public:CMyLineTree(int iEleSize, int K,TSave tDefault):m_iK(K), CVectorSingUpdateLineTree<TSave, TRecord>(iEleSize,tDefault) {}		protected:			virtual void OnQuery(TSave& ans, const TSave& cur, const int& iSaveLeft, const int& iSaveRight) {Union(ans, ans, cur);}virtual void OnUpdate(TSave& save, int iSave, const TRecord& updatee) {save.mul = updatee % m_iK;memset(save.cnt, 0, sizeof(save.cnt));save.cnt[save.mul] = 1;}virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) {Union(par, left, r);}void Union(TSave& par, const TSave& left, const TSave& r) {		memcpy(par.cnt, left.cnt, sizeof(par.cnt));for (int i = 0;i < m_iK;i++) {const int i1 = (i * left.mul) % m_iK;par.cnt[i1] += r.cnt[i];}par.mul = left.mul * r.mul % m_iK;}const int m_iK;};class Solution {public:vector<int> resultArray(vector<int>& nums, int K, vector<vector<int>>& queries) {const int N = nums.size();CMyLineTree lineTree(N, K , CData());for (int i = 0;i < N;i++) {lineTree.Update(i, nums[i]);}vector<int> ans;for (const auto& v : queries) {lineTree.Update(v[0],v[1]);nums[v[0]] = v[1];auto curAns = lineTree.Query(v[2], N - 1);ans.emplace_back(curAns.cnt[v[3]]);}return ans;}};

单元测试

vector<int> nums;int k;vector<vector<int>> queries;TEST_METHOD(TestMethod01){nums = { 1,2,3,4,5 }, k = 3, queries = { {2,2,0,2},{3,3,3,0},{0,1,0,1} };auto res = Solution().resultArray(nums, k,queries);AssertEx({ 2,2,2 }, res);}TEST_METHOD(TestMethod02){nums = { 1,2,4,8,16,32 }, k = 4, queries = { {0,2,0,2},{0,2,0,1} };auto res = Solution().resultArray(nums, k, queries);AssertEx({ 1,0 }, res);}TEST_METHOD(TestMethod03){nums = { 1,1,2,1,1 }, k = 2, queries = { {2,1,0,1} };auto res = Solution().resultArray(nums, k, queries);AssertEx({ 5 }, res);}

后缀积线段树(放弃：错误或过于复杂想法)

性质一：suff[n]表示nums长度为n的后缀的乘积。则nums删除长度为n1的前缀和长度为n2的后缀后为num1，则num1的乘积为 $suff[N−n1]÷suff[n2],0≠suff[n2]suff[N-n1]\div suff[n2],0 \neq suff[n2]$ 。
性质二：如果符合性质一，则n1 = $starti,0≤n2<N−n1start_i,0 \le n2 < N-n1$ ,则判断 $\div suff[n2] == y,y \equiv x_i \mod K$ 。即 $suff[N-n1]\div x_i$ ,即suff[n2]中为 $x_i$ 的数量。
性质三：如果nums[i]是0，则nums[i $⋯j\cdots j$ ]的乘积一定是0， $\ge i$ 。

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
员工说：技术至上，老板不信；投资人的代表说：技术至上，老板会信。
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功