差分、前缀和

区间加等差数列，使用二次差分完成。第一次差分处理等差数列的差，为了方便将等差数列首项也计入公差。

对于在 $[l,r]$ 上加一个首项为 $S$，末项为 $T$ 的等差数列，首先计算公差 $K = \dfrac{T-S}{r-l}$，然后将 $[l,r]$ 区间加 $K$ 后前缀和一次，然后在 $r+1$ 处减去 $K \times (r-l+1)$ 消除公差的影响。最后再将 $[l,r]$ 区间加 $S-K$ 后前缀和一次。

注意开 long long，最后输出序列上所有元素异或和和最大值。实现里的很多循环可以合并，但是题目不卡常所以没改。

时间复杂度 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
long long ans,uim,S[300'005],T[300'005],K[300'005],sum[10'000'005];
int n,m,l[300'005],r[300'005];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>l[i]>>r[i]>>S[i]>>T[i];
    for(int i=1;i<=m;i++) K[i]=(T[i]-S[i])/(r[i]-l[i]);
    for(int i=1;i<=m;i++) sum[l[i]]+=K[i],sum[r[i]+1]-=K[i];
    for(int i=1;i<=n;i++) sum[i]+=sum[i-1];
    for(int i=1;i<=m;i++) sum[r[i]+1]-=K[i]*(r[i]-l[i]+1);
    for(int i=1;i<=m;i++) sum[l[i]]+=S[i]-K[i],sum[r[i]+1]-=S[i]-K[i];
    for(int i=1;i<=n;i++) sum[i]+=sum[i-1];
    for(int i=1;i<=n;i++) ans^=sum[i],uim=max(uim,sum[i]);
    cout<<ans<<' '<<uim<<'\n';
    return 0;
}