题意

原图中初始没有任何节点。我们将所有区域按照其动物数量从大到小排序，然后逐个加入图中。

思路

当我们加入区域 $i$ 时，同时加入所有连接 $i$ 与已加入区域 $j$ 的道路 $(i, j)$。
此时，一些原本不连通的连通分量会合并。如果两个区域 $p$ 和 $q$ 分别位于刚刚合并的两个不同连通分量中，那么 $f(p, q)$ 必然等于当前区域 $i$ 的动物数量 $v_i$，因为直到加入节点 $i$ 时它们才连通。

算法步骤

1. 将所有区域按动物数量降序排序。
2. 初始化并查集，维护每个连通分量的大小。
3. 按排序后的顺序依次加入每个区域：
   • 加入区域 $i$ 时，遍历所有与 $i$ 相连且已加入的区域 $j$。
   • 若 $i$ 和 $j$ 当前不在同一个连通分量中，则合并它们，并利用两个分量的大小计算贡献：
     [ \text{贡献} = v_i \times \text{size}(p) \times \text{size}(q) ]
   • 将贡献累加到答案中。
4. 输出最终答案。

复杂度分析

• 排序时间复杂度为 $O(n \log n)$。
• 每个节点和每条边在并查集操作中最多被处理一次，总时间复杂度为 $O(n + m \cdot \alpha(n))$，其中 $\alpha$ 为反阿克曼函数，近似常数。
• 空间复杂度为 $O(n + m)$。

代码说明

• 使用并查集（Union-Find Set）维护连通分量及其大小。
• 按动物数量降序遍历节点，每次合并时计算当前动物数量与两个分量大小的乘积，并累加至答案。
• 注意使用 long long 类型存储答案，避免溢出。

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

using namespace std;

typedef long long ll;
typedef __int128 i128;

const ll N = 1e5 + 9;

//快读快写
char buf[1 << 21], *p1, *p2;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline ll read() {ll x = 0, f = 1;char ch = getchar();while (ch < '0' || ch > '9') {if (ch == '-')f = -1;ch = getchar();}while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();return x * f;}
inline void print(ll x, char ch = 0) {if (x < 0) putchar('-'), print(-x);else {if (x >= 10) print(x / 10);putchar(x % 10 + '0');}if (ch) putchar(ch);return;}

int n, m, l, r, x, opt;
ll a[N], ans;

int main() {
    
	n = read();
	m = read();
	for (ll i = 1; i <= n; ++i) {
		a[i] = read();
	}
	while (m--) {
		ans = 0;
		opt = read();
		l = read();
		r = read();
		if (opt == 1) {
			for (ll i = l; i <= r; ++i) {
				ans += a[i];
			}
			print(ans, '\n');
		}
		else
		if (opt == 2) {
			x = read();
			i128 y = ((i128)1 << 64) / x;
			ll i;
         //循环展开
			for (i = l; i + 4 <= r; i += 5) {
				//巴雷特模乘
                if (a[i] >= x) {
                    a[i] = a[i] - ((i128)a[i] * y >> 64) * x;
                    if (a[i] >= x) a[i] -= x;
                }
                if (a[i + 1] >= x)
                {
                    a[i + 1] = a[i + 1] - ((i128) a[i + 1] * y >> 64) * x;
                    if (a[i + 1] >= x) a[i + 1] -= x;
                }
                if (a[i + 2] >= x)
                {
                    a[i + 2] = a[i + 2] - ((i128) a[i + 2] * y >> 64) * x;
                    if (a[i + 2] >= x) a[i + 2] -= x;
                }
                if (a[i + 3] >= x)
                {
                    a[i + 3] = a[i + 3] - ((i128) a[i + 3] * y >> 64) * x;
                    if (a[i + 3] >= x) a[i + 3] -= x;
                }
                if (a[i + 4] >= x)
                {
                    a[i + 4] = a[i + 4] - ((i128) a[i + 4] * y >> 64) * x;
                    if (a[i + 4] >= x) a[i + 4] -= x;
                }
			}
			while (i <= r) {
				if (a[i] >= x) {
                    a[i] = a[i] - ((i128)a[i] * y >> 64) * x;
                    if (a[i] >= x) a[i] -= x;
                }
				++i;
			}
		}
		else {
			a[l] = r;
		}
	}
    return 0;
}