蜂蜜柚子茶

题目描述

是从什么时候开始的呢···

大概是在「沽酒」的那一晚，小戾不声不响地给他们包厢上了多放了很多糖的蜂蜜柚子茶。

在自己被灌了不少酒之时，给向来嗜甜的自己。

小戾的面前放了\(N\)杯正常甜度的蜂蜜柚子茶，茶底都是早就做好的，是精心调配的比例。先前并没有往里添加糖的先例。

不过如果是给LCT的话，又有何不可。

小戾的「沽酒」设备先进，有批量给多杯饮品加糖的机器。说是加糖，其实就是撒糖。小戾在吧台上将N杯饮品排成一排，每次操作会以一个点为中心，在一个半径内给一些饮料添加糖。使用这种方式，总是位于中心的饮料被加的糖最多，而随着与中心的距离越来越远，饮品中被撒入的糖逐渐减少。具体来说，一次撒糖可以用三个参数来描述：\(x_i,r_i,w_i\)，其中

\(x_i\)：表示撒糖的中心。

\(r_i\)：表示撒糖的半径。对于\(1≤j≤n\)的所有\(j\)，当\(|j?x_i|≤r_i\)时，第\(j\)杯饮品中就会被撒入糖。注意，这并不代表\(x?r_i∈[1,n]\)，机器撒糖当然有可能会将糖撒到杯子外面，我们不需要考虑这些撒出边界的糖。也就是说，当一杯饮品与撒糖中心之间的距离不超过撒糖半径ri时，这杯饮品就会被撒入糖。

wi：用于量化被撒到的糖。对于在该次撒糖半径中的饮品\(j\)，即满足\(|j?x_i|≤r_i\)的某个\(j\)，在该次撒糖过程中将会被撒到\(w_i?|j?x_i|\)单位的糖。也就是说，撒糖中心会被撒到wi单位的糖，每往左/右移一位，撒的糖数量就会减少一个单位。当然，被撒到糖的前提是位于撒糖半径内，在撒糖半径之外的饮品被撒入糖的量都是0。

小戾在撒的过程中也会做一些抽样，比如指定某一杯饮品，问它目前添加的糖有多少。

注意，初始时所有饮品都为正常糖量，可被认为是0单位添加糖。

输入格式
第一行两个数\(N,M\)。分别表示饮品的数量和操作的个数。

接下来M行，每行格式为下面的某一种：

+ \(x_i r_i w_i\)：表示以xi为撒糖中心，\(r_i\)为撒糖半径，\(w_i\)为撒糖中心被撒到的糖量进行一次撒糖操作。

? \(x_i\)：表示询问第\(x_i\)杯饮品的甜度。

保证\(1≤x_i,r_i≤n，0≤w_i≤10^9\)。保证\(r_i≤w_i\)，即撒糖操作「撒」的糖必然是非负整数，不会「抽」糖。

输出格式
对于每个?输出一行表示答案。

样例输入1

3 5
+ 2 3 4
+ 1 1 2
+ 3 1 2
? 1
+ 1 2 8

样例输出1

5

样例输入2

10 5
+ 9 9 7
? 7
? 4
? 9
? 10

样例输出2

5
2
7
6

题目限制
时间限制：1000ms

空间限制：512MB

对于30%的数据，\(N,M≤10^3\)。

另有20%的数据，满足\(w_i≤10^4\)。

对于100%的数据，满足\(N,M≤2×10^5\)。 保证\(1≤x_i,r_i≤n，0≤w_i≤10^9，r_i≤w_i\)。

这道题其实第二个样例不符合题目要求，没过的可以尝试

区间加，单点求和，尝试用线段树解决。

首先如果区间加的是一个等差数列，其实也能用线段树做，但是太麻烦了，我们考虑用一些简单的方法解决。

对原数列进行差分后，我们可以发现，在某一段区间差分序列增加了1，后面又减少了1.

先通过半径求出撒糖的区间\(l\)和1\(r\)，然后发现\(l+1\sim x\)的差分序列加了1，\(x+1\sim r\)这一段减少了1,同时按照题目给的公式求出\(l\)和\(r\)的增量\(x\)和\(y\)，然后在l处差分序列增加\(x\)，\(r+1\)处减少了y。

注意处理边界问题（n=1),询问x时输出\(1\sim x\)的和即可。

#include
using namespace std;
const int N=2e5+5; 
int n,m,x,y,w,l,r;
char op;
struct node{
	long long sum,tag;
}tr[N<<2];
void pushdown(int o,int l,int r)
{
	int md=l+r>>1;
	tr[o<<1].tag+=tr[o].tag;
	tr[o<<1|1].tag+=tr[o].tag;
	tr[o<<1].sum+=tr[o].tag*(md-l+1);
	tr[o<<1|1].sum+=tr[o].tag*(r-md);
	tr[o].tag=0;
}
void update(int o,int l,int r,int x,int y,int z)
{
	if(x<=l&&r<=y)
	{
		tr[o].sum+=1LL*(r-l+1)*z;
		tr[o].tag+=z;
		return;
	}
	pushdown(o,l,r);
	int md=l+r>>1;
	if(md>=x)
		update(o<<1,l,md,x,y,z);
	if(md>1;
	long long ret=0;
	if(md>=x)
		ret+=query(o<<1,l,md,x,y);
	if(md