题目大意：
m次给某个[l,r]加上一个等差数列，求所有数的最大值和序列异或和
第一眼：线段树差分维护区间，查询是从[1,i]，复杂度nlogn
再看数据范围n<=1e7,???
不能线段树，wtf，这咋搞哇
一次差分不行，那就二次差分
a数组为原数，b数组为一次差分，c数组为二次差分。
如果区间修改的话，只看b数组就是
b[l]+=s,b[l+1->r]+=d,b[r+1]-=e;
那么c数组对每次b数组的差分就是
c[l]+=s,c[l+1]+=d-s,c[r+1]=c[r+1]-e-d,c[r+2]+=d
然后求a[i]的花，先对c[1->i]求和是b[i]，然后对b[1->i]求和就是a[i];
然后对a进行异或和取最大值就完了。
#include<iostream> #include<cstdio> using namespace std; typedef long long LL; const int N=1e7+5; int n,m; LL a[N],b[N],c[N],ans,mx; inline int read(){ int s=0,w=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)w=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){s=s*10+ch-‘0‘;ch=getchar();} return s*w; } int main(){ n=read();m=read(); int l,r,s,e,d; for(int i=1;i<=m;++i){ l=read();r=read();s=read();e=read(); d=(e-s)/(r-l); c[l]+=s;c[l+1]+=d-s; if(r!=n){ c[r+1]=c[r+1]-d-e; c[r+2]=c[r+2]+e; } } for(int i=1;i<=n;++i){ b[i]=b[i-1]+c[i]; a[i]=a[i-1]+b[i]; mx=mx<a[i]?a[i]:mx; ans^=a[i]; } printf("%lld %lld",ans,mx); return 0; }
原文：https://www.cnblogs.com/sanjinliushi/p/11687987.html