详见注释

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const LL P = 998244353;
const int N = 5e5 + 10;

LL a[N], ans;
int fa[21][N];
// fa[i][j] 其实并不代表着 [j, j + (1 << i) - 1] 区间的都属于 j 的并查集
// 不然初始化的时候不就直接把区间合并了嘛！
// 其实这不能单独来看，换句话说，只有两个不同的 j
// 在 fa[i] 里都属于一个并查集，才能代表 [j, j + (1 << i) - 1] 和 [j', j' + (1 << i) - 1] 同属
// 这类似于懒标记，但不是向下传递
// 如果这一层两个不同的点并查集相同，那就没有接着往下的必要了 

int findfa(int c, int x) {
	if (fa[c][x] == x) {
		return fa[c][x];
	}
	return fa[c][x] = findfa(c, fa[c][x]);
}

void merge(int C, int x, int y) {
	int tx = findfa(C, x), ty = findfa(C, y);
	if (tx != ty) {
		fa[C][tx] = ty;   // 合并第 C 层的并查集 
		if (C != 0) {
			merge(C - 1, x, y);
			merge(C - 1, x + (1 << (C - 1)), y + (1 << (C - 1)));
		}
		else {
			ans = (ans + a[tx] * a[ty] % P) % P; 
			a[ty] = (a[ty] + a[tx]) % P;   
			 // 只有到最底层才合并 a 数组，因为 a 数组管的是单个 
		}
	}
}

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n, Q;
	cin >> n >> Q;
	
	for (int i = 0; i < n; i ++) {
		cin >> a[i];
	}
	
	for (int i = 0; i <= 20; i ++) {
		for (int j = 0; j < n; j ++) {
			fa[i][j] = j;
		}
	}
	
	ans = 0;
	while (Q --) {
		int len, x, y;
		cin >> len >> x >> y;
		if (len == 0) {
			cout << ans << "\n";
			continue;
		}
		
		int lg = log2(len);
		// 1<<(log2(n)) <= n
		// len = 0 时 lg 会等于负数，所以要特判 
		merge(lg, x, y);
		merge(lg, x + len - (1 << lg), y + len - (1 << lg));
		
		cout << ans << "\n";
	}
	
	return 0;
} 

这波糖了没想到倍增以为是一个很高级的算法。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+10,P=998244353;
int fa[21][N],a[N],ans;
int findfa(int c,int x){return fa[c][x]==x?fa[c][x]:fa[c][x]=findfa(c,fa[c][x]);}
void merge(int c,int x,int y)
{
	int tx=findfa(c,x),ty=findfa(c,y);
	if(tx!=ty)
	{
		fa[c][tx]=ty;
		if(c)
		{
			merge(c-1,x,y);
			merge(c-1,x+(1<<(c-1)),y+(1<<(c-1)));
		}
		else
		{
			ans=(ans+a[tx]*a[ty])%P;
			a[ty]=(a[ty]+a[tx])%P;
		}
	}
}
signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n,q;cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=0;i<20;i++)for(int j=1;j<=n;j++)fa[i][j]=j;
	while(q--)
	{
		int l,x,y;cin>>l>>x>>y;x++,y++;
		if(l==0){cout<<ans<<'\n';continue;}
		int lim=log2(l);
		merge(lim,x,y);
		merge(lim,x+l-(1<<lim),y+l-(1<<lim));
		cout<<ans<<'\n';
	}
	return 0;
}