题解思路

这道题的核心在于理解乘积相等的数学本质。由于数组只包含1和2，段的乘积实际上完全由该段中2的个数决定。

1. 问题转化分析

对于任意一个连续子数组，其乘积等于 $2^k$，其中k是该子数组中2的个数。要使z个段的乘积相等，等价于每个段中2的个数相同。

关键观察：

• 如果总共有 $count_2$ 个元素2，要分成z个乘积相等的段，则每段必须恰好包含 $\frac{count_2}{z}$ 个元素2
• 如果 $count_2$ 不能被z整除，则无解
• 如果所有元素都是1（即 $count_2 = 0$），则任意划分都满足条件

2. 可行性判断算法

核心判断条件包括：

1. 基础约束：$z \leq n$（段数不能超过数组长度）
2. 均分条件：如果 $count_2 > 0$，则必须 $count_2 \bmod z = 0$
3. 分布约束：设每段需要 $k = \frac{count_2}{z}$ 个元素2，前 $z-1$ 段总共需要 $(z-1) \times k$ 个元素2，这些元素2必须能够在数组的前 $n-1$ 个位置中找到

第三个条件是关键：我们需要确保前 $z-1$ 段能够分配到足够的元素2，剩余的元素2恰好构成最后一段。

3. 动态维护策略

使用 $count_2$ 变量实时维护数组中2的总个数，每次修改操作时：

• 如果 $a[x-1] \neq y$，则更新 $count_2$
• 然后应用上述判断逻辑

4. 时间复杂度分析

• 单次查询：$O(1)$
• 总时间复杂度：$O(T \times (n + m))$
• 空间复杂度：$O(n)$

Java题解代码

import java.io.*;
import java.util.*;

public class Main {
    
    static class FastIO {
        BufferedReader br;
        StringTokenizer st;
        
        public FastIO() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        
        public String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        public int nextInt() {
            return Integer.parseInt(next());
        }
    }
    
    public static void main(String[] args) {
        FastIO io = new FastIO();
        StringBuilder result = new StringBuilder();
        
        int T = io.nextInt();
        
        while (T-- > 0) {
            int n = io.nextInt();
            int m = io.nextInt();
            
            int[] arr = new int[n];
            int countTwos = 0;
            
            // 读取数组并统计2的个数
            for (int i = 0; i < n; i++) {
                arr[i] = io.nextInt();
                if (arr[i] == 2) {
                    countTwos++;
                }
            }
            
            // 处理m次操作
            for (int i = 0; i < m; i++) {
                int x = io.nextInt() - 1; // 转换为0-based索引
                int y = io.nextInt();
                int z = io.nextInt();
                
                // 更新数组和2的计数
                if (arr[x] != y) {
                    if (arr[x] == 2) {
                        countTwos--; // 从2变为1
                    } else {
                        countTwos++; // 从1变为2
                    }
                    arr[x] = y;
                }
                
                // 判断是否可以完成划分
                if (canPartition(arr, n, z, countTwos)) {
                    result.append("Yes\n");
                } else {
                    result.append("No\n");
                }
            }
        }
        
        System.out.print(result.toString());
    }
    
    /**
     * 判断是否可以将数组划分为z个乘积相等的段
     */
    private static boolean canPartition(int[] arr, int n, int z, int countTwos) {
        // 段数不能超过数组长度
        if (z > n) {
            return false;
        }
        
        // 如果没有2，任意划分都可以
        if (countTwos == 0) {
            return true;
        }
        
        // 2的个数必须能被z整除
        if (countTwos % z != 0) {
            return false;
        }
        
        int k = countTwos / z; // 每段需要的2的个数
        
        // 计算前n-1个位置中2的个数
        int prefixTwos = countTwos;
        if (arr[n - 1] == 2) {
            prefixTwos--;
        }
        
        // 前z-1段总共需要(z-1)*k个2，必须能在前n-1个位置找到
        return (z - 1) * k <= prefixTwos;
    }
}

C++题解代码

#include <iostream>
#include <vector>
#include <ios>

using namespace std;

class ArrayPartitionSolver {
private:
    vector<int> arr;
    int n, countTwos;
    
public:
    void solve() {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        
        int T;
        cin >> T;
        
        while (T--) {
            int m;
            cin >> n >> m;
            
            arr.resize(n);
            countTwos = 0;
            
            // 读取数组并统计2的个数
            for (int i = 0; i < n; i++) {
                cin >> arr[i];
                if (arr[i] == 2) {
                    countTwos++;
                }
            }
            
            // 处理m次操作
            for (int i = 0; i < m; i++) {
                int x, y, z;
                cin >> x >> y >> z;
                x--; // 转换为0-based索引
                
                // 更新数组状态
                updateArray(x, y);
                
                // 输出判断结果
                if (canPartition(z)) {
                    cout << "Yes\n";
                } else {
                    cout << "No\n";
                }
            }
        }
    }
    
private:
    /**
     * 更新数组指定位置的值并维护2的计数
     */
    void updateArray(int index, int newValue) {
        if (arr[index] != newValue) {
            if (arr[index] == 2) {
                countTwos--; // 从2变为1
            } else {
                countTwos++; // 从1变为2
            }
            arr[index] = newValue;
        }
    }
    
    /**
     * 判断是否可以将数组划分为z个乘积相等的段
     */
    bool canPartition(int z) {
        // 基本约束检查
        if (z > n) return false;
        
        // 特殊情况：没有2的元素
        if (countTwos == 0) return true;
        
        // 2的个数必须能被z整除
        if (countTwos % z != 0) return false;
        
        int segmentTwos = countTwos / z; // 每段需要的2的个数
        
        // 计算前n-1个位置的2的个数
        int prefixTwos = countTwos;
        if (arr[n - 1] == 2) {
            prefixTwos--;
        }
        
        // 验证分布约束
        return (z - 1) * segmentTwos <= prefixTwos;
    }
};

int main() {
    ArrayPartitionSolver solver;
    solver.solve();
    return 0;
}