令 $B$ 为值域分治的阈值。

关于若公差 $>B$ 则直接暴力做的复杂度证明。

看似最多有 $\sqrt n$ 段这种的，每种复杂度 $n/B$，复杂度也寄了。（本人第一次的想法）

但实际上，注意到 $\sum d_i\times L_i=O(n)$，其中 $L_i$ 表示第 $i$ 段等差数列的长度。于是 $\forall d_i>B,\sum L_i\le n/B$，就保证了复杂度。

并提供一种好写的 set 维护连续段的实现：

#include<bits/stdc++.h>
#define LL long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=2e5+5,B=100;
int n,m,c[N],t,A[N],C[N],fr[N],d[N],L[N],f[B+5][N];LL a[N];
struct node
{
	int l,r;
	inline int L(){return r-l+1;}
	bool operator<(node x)const{return l<x.l;}
};set<node>S;
set<int>ap;
inline void del(node t){if(!(--c[t.L()])) ap.erase(t.L());S.erase(t);}
inline void add(node t){if(!(c[t.L()]++)) ap.insert(t.L());S.insert(t);}
inline void spl(int p)
{
	auto t=--S.upper_bound({p,0});
	int l=t->l,r=t->r;del(*t);
	add({l,p});add({p+1,r});
}
inline void meg(int p)
{
	auto t=S.upper_bound({p,0});auto t1=t;t1--;
	int l=t1->l,r=t->r;del(*t);del(*t1);
	add({l,r});
}
inline void upd(int p,int x)
{
	if(a[p]==0&&a[p]+x!=0) meg(p);
	if(a[p]!=0&&a[p]+x==0) spl(p);a[p]+=x;
}
inline void sol()
{
	t=0;for(int i:ap) A[++t]=i,C[t]=c[i];d[t+1]=fr[t+1]=0;
	for(int i=t;i;i--) d[i]=d[i+1]+C[i],L[i]=A[i]-A[i-1];
	for(int i=t;i;i--) fr[i]=C[i]+fr[i+1]+L[i+1]*d[i+1];
	int ans=0;
	for(int i=1;i<=t;i++)
	{
		if(d[i]<=B)
		{
			int ll=fr[i],rr=fr[i]+(L[i]-1)*d[i];
			ans^=f[d[i]][rr];if(ll>d[i]) ans^=f[d[i]][ll-d[i]];
		}
		else for(int j=1,s=fr[i];j<=L[i];j++,s+=d[i]) ans^=s;
	}cout<<ans<<"\n";
}
inline void init()
{
	for(int i=1;i<=min(n,B);i++)
	{
		for(int j=1;j<=i;j++) f[i][j]=j;
		for(int j=i+1;j<=n;j++) f[i][j]=f[i][j-i]^j;
	}
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];init();
	for(int i=1;i<n;i++) a[i]-=a[i+1];add({1,n});
	for(int i=1;i<n;i++) if(a[i]==0) spl(i);sol();
	for(int l,r,x;m--;)
	{
		cin>>l>>r>>x;
		if(l>1) upd(l-1,-x);if(r<n) upd(r,x);sol();
	}
	return 0;
}