P1438 无聊的数列

*原题链接*

做法：线段树+差分

很巧的一道题，区间操作单点询问，很容易想到诸如树状数组、线段树等数据结构，但发现这个题的区间加不是很好维护，一时没了思路。但是再去观察，发现给我们的是等差数列，如果我们把原序列差分一下，那么实际上就是在差分数组中进行区间加区间查了。所以我们对差分数组维护一颗线段树，这道题就做完了。至于对差分数组的操作可以自己手推一下式子。

CODE：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;

int n,m,a[N];

struct node{
	int l,r;
	int sum,add;
}tr[N*4];

void pushdown(int u){
	node &root=tr[u],&left=tr[u<<1],&right=tr[u<<1|1];
	if(!root.add) return;
	left.add+=root.add,left.sum+=root.add*(left.r-left.l+1);
	right.add+=root.add,right.sum+=root.add*(right.r-right.l+1);
	root.add=0;
}

void pushup(int u){
	tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}

void build(int u,int l,int r){
	if(l==r) tr[u]={l,r,a[l]-a[l-1],0};
	else{
		tr[u].l=l,tr[u].r=r;
		int mid=(l+r)>>1;
		build(u<<1,l,mid),build(u<<1|1,mid+1,r);
		pushup(u);
	}
}

void modify(int u,int l,int r,int x){
	if(tr[u].l>=l&&tr[u].r<=r){
		tr[u].add+=x;
		tr[u].sum+=x*(tr[u].r-tr[u].l+1);
	}
	else{
		pushdown(u);
		int mid=(tr[u].l+tr[u].r)>>1;
		if(l<=mid) modify(u<<1,l,r,x);
		if(r>mid) modify(u<<1|1,l,r,x);
		pushup(u);
	}
}

int query(int u,int l,int r){
	if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;
	pushdown(u);
	int mid=(tr[u].l+tr[u].r)>>1,ans=0;
	if(l<=mid) ans+=query(u<<1,l,r);
	if(r>mid) ans+=query(u<<1|1,l,r);
	return ans;
}

signed main(){
	
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	build(1,1,n);
	while(m--){
		int opt,l,r,k,d;
		cin>>opt;
		if(opt==1){
			cin>>l>>r>>k>>d;
			modify(1,l,l,k);
			if(r+1<=n) modify(1,r+1,r+1,-k+(l-r)*d);//注意一下r+1的范围
			if(l+1<=r) modify(1,l+1,r,d);
		}
		else{
			cin>>k;
			cout<<query(1,1,k)<<endl;
		}
	}
	
	return 0;
}