【题型总结】给区间加等差数列求值问题
一、前言：
上一篇题型总结不知道扔哪去了，下午训练看到个很眼熟的题，感觉见过很多次了，就顺手总结下。
需要会的前置知识有：差分与前缀和，树状数组基础，线段树基础
二、UPC 2020年夏混合个人训练第八十场 问题 B: 序列 （二阶差分）
题意：
给定长度为n的数组和m次操作，每次操作都表示将区间[l,r]加上一个首项为s，末项为e的等差数列，求操作后序列每一项的异或和。
思路：
序列[l]+=首项;
序列[l+1]+=公差-首项;
序列[r+1]-=首项+(r-l+1)*公差;//注意r+1处要减，其余的均为加。
序列[r+2]+=首项+(r-l)*公差;
代码：
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") #pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native") #pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; #define ll long long #define I_int ll typedef pair<int,int> PII; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } char F[200]; inline void out(I_int x) { if (x == 0) return (void) (putchar('0')); I_int tmp = x > 0 ? x : -x; if (x < 0) putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0) putchar(F[--cnt]); //cout<<" "; } const int maxn=500000+100; ll a[maxn],n,m; int main(){ n=read(),m=read(); while(m--){ ll l=read(),r=read(),s=read(),e=read(); ll q=(e-s)/(r-l); a[l]+=s;a[l+1]+=q-s; a[r+1]-=s+(r-l+1)*q;a[r+2]+=s+(r-l)*q; } for(int i=1;i<=n;i++) a[i]+=a[i-1]; ll res=0; for(int i=1;i<=n;i++){ a[i]+=a[i-1]; res^=a[i]; } out(res); return 0; }
参考博客：
博客的题就是以前训练的题，只是变了变题目背景。
三、洛谷P1438 无聊的数列 （差分+线段树/树状数组/分块）原题链接
题意：
维护一个数组和两种操作，操作一就是将区间加上一个等差数列，操作二是查询某点的值。
思路：
考虑一下本题跟上一题的区别，上一题的询问是执行完所有区间加法后进行的，本题是强制在线。这时候如果再采用上题的二阶差分显然不可取。
最特殊的情况就是等差数列的公差为0，这样题目就变成了单纯的区间修改 单点查询，线段树树状数组分块都可以写。
那么对于一般情况可以借鉴一下上题的思路，开设一个差分数组，对于区间[l,r]进行修改的话，就是对于第l个点加首项s，对于第l+1到r的点加上公差d，对于第r+1个点减去之前加上的所有差分值，即减去s+(r-l)*d;
简单说下原理，根据差分的性质，我们执行完以上操作后，对原数组的贡献是第l个数加了s，第l+1个数加了s+d……第r+1个数不变。这就恰好符合我们的要求。
这样对于操作一，我们就转化成了单点修改和区间修改。
对于操作二，我们只需要在原数组的基础上加上差分数组的前缀和即可，本质就是一个区间求和。
然后用线段树什么的维护一下差分数组就可以了。
其他思路和代码： 洛谷题解
看到了个很短的分块代码，还是分块无敌啊。
四、牛客小白月赛20 E 区区区间（等差数列求和公式+线段树）
原题链接
题意：
给定一个长度为n的数组和m次操作，操作一是将区间替换程以k为首项，1为公差的等差数列，操作二是查询区间的和。
思路：
操作一可以看成是区间修改，操作二可以看成是区间求和，因为一段区间被修改后一定是等差数列，所以知道首项的值就可以根据等差数列的求和公式推出区间的和，所以记录一下修改后左端点的值，然后线段树维护一下左端点的值和区间的和即可。
代码：
但学长说我写法常数有点大emm，还是参考下其他巨巨的写法吧。
五、感谢阅读。
希望各位期末不挂！
