线段树+差分 P1438 无聊的数列

传送门https://www.luogu.com.cn/problem/P1438

这道题要求维护一个等差数列的区间加，我们可以将等差数列的问题转化成差分的问题（因为等差数列每次维护的复杂度使O（n） ，但是如果用差分就只用O（1）就可以解决。

也就是只维护三个位置

• 第一个点（全部都要加上首项）
• 第二个点（一整段都要加上公差）
• 第三个点（减掉前面加上的）

我写的时候没想到（差分题练少了）

想好思路，维护并不难（就是板子随便套点东西）

代码如下（注意：建树要开到n+1，小心越界）

// Problem: 
//     P1438 无聊的数列
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1438
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<iostream>
using namespace std;
const int N=1e5+10;
#define int long long
struct node{
	int l,r,sum,add;
}tr[N*4];
int e[N];
int f[N];
int n,m;
#define lc u<<1
#define rc u<<1|1
#define endl '\n'

void pushup(int u){
	tr[u].sum=tr[lc].sum+tr[rc].sum;
}
void pushdown(int u){
	if(tr[u].add){
		tr[lc].sum+=(tr[lc].r-tr[lc].l+1)*tr[u].add;
		tr[rc].sum+=(tr[rc].r-tr[rc].l+1)*tr[u].add;
		tr[lc].add+=tr[u].add;
		tr[rc].add+=tr[u].add;
		tr[u].add=0;
	}
}
void build(int u,int l,int r){
	tr[u]={l,r};
	if(l==r){
		tr[u].sum=f[l];return;
	}
	int m=(l+r)>>1;
	build(lc,l,m);
	build(rc,m+1,r);
	pushup(u);
}
int query(int u,int l,int r){
	if(l<=tr[u].l&&tr[u].r<=r) return tr[u].sum;
	pushdown(u);
	int sum=0;
	int m=(tr[u].l+tr[u].r)>>1;
	if(l<=m) sum=query(lc,l,r);
	if(r>m) sum+=query(rc,l,r);
    return sum;
}
void update_line(int u,int l,int r,int k){
	if(l<=tr[u].l&&tr[u].r<=r){
		tr[u].add+=k;
		tr[u].sum+=(tr[u].r-tr[u].l+1)*k;
		return;
	}
	pushdown(u);//这里不pushdown有啥后果
	int m=(tr[u].l+tr[u].r)>>1;
	if(l<=m) update_line(lc,l,r,k);
	if(r>m) update_line(rc,l,r,k);
	pushup(u);
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;++i) cin>>e[i];
    for(int i=1;i<=n;++i) f[i]=e[i]-e[i-1];//差分
    build(1,1,n+1);
	while(m--){
		int op;cin>>op;
		if(op==2){
			int a;cin>>a;
			cout<<query(1,1,a)<<endl;
		}
		else{
			int a,b,c,d;cin>>a>>b>>c>>d;
			int cnt=c+(b-a)*d;
			update_line(1,a,a,c);
			if(a+1<=b) update_line(1,a+1,b,d);
			update_line(1,b+1,b+1,-cnt);
		}
	}
    return 0;
}