CCPC2024-Zhengzhou G Same Sum（线段树）

CCPC2024-Zhengzhou G Same Sum

给一个序列。两种操作：

1. 区间加；

2. 查询一个偶数长区间，其中的值是否可以两两配对得到和相等。

首先知道区间内的值两两配对得到的相等的和值为区间的平均数 m 。

可以转化为，这个区间的值分布关于 m 对称。

\[x^{a_i+a_j}=x^{2m} \Rightarrow x^{a_i}=\frac{x^{2m}}{x^{a_j}}, x^{a_j}=\frac{x^{2m}}{x^{a_i}} \]

\[\sum_{i=l}^r x^{a_i}=x^{2m}\sum_{i=l}^r x^{-a_i} \]

维护区间平均值 m，\(\sum x^{a_i}\)，\(\sum x^{-a_i}\) 即可。

这个值为什么能正确刻画这个分布？我还没搞明白...QvQ?

const i64 x=(rng()%P*rng()%P)%P;
i64 ux; // ux=power(x,P-2);i64 power(i64 A,i64 B)
{u64 ANS=1,BASE=A%P;for (;B;B>>=1,BASE=BASE*BASE%P)if (B&1) ANS=ANS*BASE%P;return ANS;
}void R()
{int n,q;cin>>n>>q;vector<i64> a(n);for (int i=0;i<n;i++) cin>>a[i];vector<Info> info(n);for (int i=0;i<n;i++)info[i]={power(x,a[i]),power(ux,a[i]),a[i],i,i};SGT<Info,Tag> sgt(info);while (q--){int opt,l,r;i64 v;cin>>opt>>l>>r; l--;if (opt==1){cin>>v;sgt.rangeApply(l,r,{power(x,v),power(ux,v),v});}else{auto [U,V,m,ll,rr]=sgt.rangeQuery(l,r);i64 len=r-l;if (m%(len/2)!=0) { cout<<"NO\n"; continue; }if (V*power(x,m/(len/2))%P==U) cout<<"YES\n";else cout<<"NO\n";}}return;
}