这是一道非常优秀的差分题。听说过二阶差分维护吗？
我们在区间加的时候是可以用差分维护的，不过这次我们要往里面加一个等差数列，这个维护起来就稍微麻烦了一点。
我的想法比较复杂，就是先用第一阶差分去维护公差，在l+1和r的位置进行修改，前者加公差后者减公差。然后我们同时要记录首项和末项相反数，然后在每次修改l的位置加上首项，在r+1的位置加上末项相反数，再跑一遍差分，就得到最后的数组啦。
最后异或+比大小即可。
完美的O（n）。
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<queue> #include<cstring> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(‘\n‘) #define pr pair<int,int> #define mp make_pair #define fi first #define sc second using namespace std; typedef long long ll; const int M = 300005; const int N = 10000005; int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < ‘0‘ || ch > ‘9‘) { if(ch == ‘-‘) op = -1; ch = getchar(); } while(ch >=‘0‘ && ch <= ‘9‘) { ans *= 10; ans += ch - ‘0‘; ch = getchar(); } return ans * op; } ll n,m,l,r,s,e,c[N],p[M],ans,maxn,v[M],d,q[M],g[M]; int main() { n = read(),m = read(); rep(i,1,m) { l = read(),r = read(),s = read(),e = read(); d = (e-s) / (r-l); c[l+1] += d,c[r+1] -= d; q[i] = l,g[i] = s,p[i] = r+1,v[i] = -e; } rep(i,1,n) c[i] += c[i-1]; //rep(i,1,n) printf("%d ",c[i]);enter; rep(i,1,m) c[q[i]] += g[i],c[p[i]] += v[i]; //rep(i,1,n) printf("%d ",c[i]);enter; rep(i,1,n) c[i] += c[i-1]; //rep(i,1,n) printf("%d ",c[i]);enter; rep(i,1,n) ans ^= c[i],maxn = max(maxn,c[i]); printf("%lld %lld\n",ans,maxn); return 0; }
原文：https://www.cnblogs.com/captain1/p/9743752.html