P1438 无聊的数列

链接：https://www.luogu.com.cn/problem/P1438
题面：

思路：
差分＋线段树。
刚开始的想法是建立一个双tag线段树：basetag和addtag。然后传递的时候basetag就是l的基准,addtag不变。求的话就是求节点值。
但是这样容易溢出。。。
所以考虑差分：利用前缀和代替当前某一点的值：query(1,n) = val[n]。
所以：注意点

• 初始数据的输入
  采用后到前差分的形式,确保前缀和是当前值。
  代码：

  for (ll i = 1; i <= n; i++)cin >> a[i];
  for (ll i = n; i >= 1; i--)a[i] -= a[i - 1];
  

• tag的使用
  实际上这里的tag就相当于[l+1,r]的区间里面都加上一个delta。然后[l]处加上一个base。[r]处加上一个-base-(r-l)*delta。

  update(L , L, 1, 1, n, base);
  update(R+1, R+1, 1, 1, n, -base-(R-L)*d);
  update(L+1, R, 1, 1, n, d);
  

• 最后添加条件判断
  注意到只有R不比n大的时候才可以添加补偿数,以及L小于R的时候才可以添加d。

  update(L , L, 1, 1, n, base);
  if(R<n)update(R+1, R+1, 1, 1, n, -base-(R-L)*d);
  if(L<R)update(L+1, R, 1, 1, n, d);
  

总的代码：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
ll a[N];
ll tree[N << 2];
ll tag[N << 2];


ll ls(ll p)
{
	return p << 1;
}
ll rs(ll p)
{
	return p << 1 | 1;
}
void push_up(ll p)
{
	tree[p] = tree[ls(p)] + tree[rs(p)];
	//从下往上传递 
}
void build(ll p, ll pl, ll pr)
{
	tag[p] = 0;
	if (pl == pr) { tree[p] = a[pl]; return; }
	ll mid = (pl + pr) >> 1;
	build(ls(p), pl, mid);
	build(rs(p), mid + 1, pr);
	push_up(p);
}
void addtag(ll p, ll pl, ll pr, ll d)
{
	//改，加上tag的作用 
	
	tag[p] += d;
	tree[p] += d * (pr - pl + 1);
}

void push_down(ll p, ll pl, ll pr)
{
	if (tag[p])
	{
		ll mid = (pl + pr) >> 1;
		addtag(ls(p), pl, mid,tag[p]);
		addtag(rs(p), mid + 1, pr,tag[p]);
		tag[p] = 0;
	}
}
void update(ll L, ll R, ll p, ll pl, ll pr, ll d)
{
	if (L <= pl and pr <= R)
	{
		addtag(p, pl, pr, d);
		return;
	}
	push_down(p, pl, pr);
	ll mid = (pl + pr) >> 1;
	if (L <= mid)update(L, R, ls(p), pl, mid, d);
	if (R > mid)update(L, R, rs(p), mid + 1, pr, d);
	push_up(p);
}


ll query(ll L, ll R, ll p, ll pl, ll pr)
{
	if (pl >= L and R >= pr)return tree[p];
	push_down(p, pl, pr);
	ll res = 0;
	ll mid = (pl + pr) / 2;
	if (L <= mid)res += query(L, R, ls(p), pl, mid);
	if (R > mid)res += query(L, R, rs(p), mid + 1, pr);
	return res;
}

signed main()
{
	IOS;
	ll n, m;
	cin >> n >> m;
	for (ll i = 1; i <= n; i++)cin >> a[i];
	for (ll i = n; i >= 1; i--)a[i] -= a[i - 1];
	build(1, 1, n);

	while (m--)
	{
		ll q, L, R, d;
		cin >> q;
		if (q == 1)
		{
			ll base;
			cin >> L >> R >>base>> d;
			update(L , L, 1, 1, n, base);
			if(R<n)update(R+1, R+1, 1, 1, n, -base-(R-L)*d);
			if(L<R)update(L+1, R, 1, 1, n, d);


		}
		else {
			cin  >> R;
			cout << query(1, R, 1, 1, n)<<'\n';
		}
	}

	return 0;
}