# 蜂蜜柚子茶(Honey grapefruit tea)-其他

## 蜂蜜柚子茶(Honey grapefruit tea)

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

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

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

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

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

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

``````5
``````

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

``````5
2
7
6
``````

``````#include<bits/stdc++.h>
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<y)
update(o<<1|1,md+1,r,x,y,z);
tr[o].sum=tr[o<<1].sum+tr[o<<1|1].sum;
}
long long query(int o,int l,int r,int x,int y)
{
if(x<=l&&r<=y)
return tr[o].sum;
pushdown(o,l,r);
int md=l+r>>1;
long long ret=0;
if(md>=x)
ret+=query(o<<1,l,md,x,y);
if(md<y)
ret+=query(o<<1|1,md+1,r,x,y);
return ret;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf(" %c",&op);
if(op=='?')
{
scanf("%d",&x);
printf("%lld\n",query(1,1,n,1,x));
}
else
{
scanf("%d%d%d",&x,&y,&w);
l=max(x-y,1),r=min(x+y,n);
if(l!=r)
{
update(1,1,n,l,l,w-x+l);
if(r<n)
update(1,1,n,r+1,r+1,r-x-w);
if(l<x)
update(1,1,n,l+1,x,1);
if(x<r)
update(1,1,n,x+1,r,-1);
}
else
update(1,1,n,x,x,w);
}
}
return 0;
}
``````
————————

Title Description

When did it start···

Probably on the night of “selling wine”, Xiao Li quietly filled their box with honey grapefruit tea with a lot of sugar.

When you have been filled with a lot of wine, give it to yourself who has always been addicted to sweetness.

Xiaoli put \ (n \) cup of honey grapefruit tea with normal sweetness in front of him. The bottom of the tea has been prepared long ago, which is a carefully prepared proportion. There was no precedent for adding sugar to it.

But if it’s for LCT, why not.

Xiaoli’s “wine selling” equipment is advanced, and there is a machine for batch adding sugar to multiple drinks. To add sugar is to sprinkle sugar. Xiao Li arranges n cups of drinks in a row on the bar. Each operation will take a point as the center and add sugar to some drinks within a radius. In this way, the beverage that is always in the center is added with the most sugar, and as it is farther and farther away from the center, the sugar sprinkled in the beverage gradually decreases. Specifically, one time sugar spraying can be described by three parameters: \ (x_i, r_i, w_i \), where

\(x_i \): indicates the center of sugar.

\(r_i \): indicates the radius of sugar spraying. For all \ (J \) of \ (1 ≤ J ≤ n \), when \ (|jx_i| ≤ r_i \), sugar will be sprinkled into the \ (J \) cup of drink. Note that this does not mean \ (xr_i ∈ [1, n] \), of course, the machine may sprinkle sugar outside the cup. We don’t need to consider these sugars sprinkled out of the boundary. In other words, when the distance between a drink and the center of sugar spraying does not exceed the radius Ri of sugar spraying, the drink will be sprinkled with sugar.

Wi: used to quantify the sugar sprinkled. For the drink \ (J \) in the sugar spraying radius, that is, a \ (J \) that meets \ (|jx_i124≤ r_i \), the sugar of \ (w_i|jx_i124\) unit will be sprinkled in the sugar spraying process. In other words, the sugar center will be sprinkled into wi units of sugar. Each time it moves left / right, the amount of sugar sprinkled will be reduced by one unit. Of course, the premise of being sprinkled with sugar is that it is within the sugar sprinkle radius, and the amount of sugar sprinkled into drinks outside the sugar sprinkle radius is 0.

Xiao Li will also take some samples in the process of sprinkling, such as specifying a drink and asking how much sugar it currently adds.

Note that at the beginning, all drinks have normal sugar content, which can be considered as 0 unit of added sugar.

Input format
The first line contains two numbers \ (n, m \). It indicates the number of drinks and the number of operations respectively.

The next M lines are in one of the following formats:

+\ (x_i r_i w_i \): it means that Xi is the sugar scattering center, \ (r_i \) is the sugar scattering radius, and \ (w_i \) is the amount of sugar scattered in the sugar scattering center for one sugar scattering operation.

? \ (x_i \): it means asking about the sweetness of the \ (x_i \) drink.

Guarantee \ (1 ≤ x_i, r_i ≤ n, 0 ≤ w_i ≤ 10 ^ 9 \). Ensure \ (r_i ≤ w_i \), that is, the sugar “sprinkled” in the sugar sprinkle operation must be a non negative integer and will not “smoke” sugar.

Output format
For each? The output line represents the answer.

Sample input 1

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

Sample output 1

``````5
``````

Sample input 2

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

Sample output 2

``````5
2
7
6
``````

Topic limitation
Time limit: 1000ms

Space limit: 512MB

For 30% of the data, \ (n, m ≤ 10 ^ 3 \).

Another 20% of the data meet \ (w_i ≤ 10 ^ 4 \).

For 100% data, meet \ (n, m ≤ 2 × 10^5\)。 Guarantee \ (1 ≤ x_i, r_i ≤ n, 0 ≤ w_i ≤ 10 ^ 9, r_i ≤ w_i \).

In fact, the second example of this problem does not meet the requirements of the problem. You can try it if you haven’t done so

Interval addition, single point summation, try to solve it with segment tree.

First of all, if the interval is added with an equal difference sequence, it can also be done with line segment tree, but it is too troublesome. We will consider using some simple methods to solve it.

After the difference of the original sequence, we can find that in a certain interval, the difference sequence increases by 1 and then decreases by 1

Firstly, calculate the sugar spreading interval \ (L \) and 1 \ (R \) through the radius, and then find that the difference sequence of \ (L + 1 \ SIM x \) is added with 1, and the segment of \ (x + 1 \ SIM R \) is reduced by 1. At the same time, calculate the increments \ (x \) and \ (Y \) of \ (L \) and \ (R \) according to the formula given in the topic, and then increase \ (x \) at L and decrease y at \ (R + 1 \).

Pay attention to dealing with the boundary problem (n = 1), and output the sum of \ (1 \ SIM x \) when asking X.

``````#include<bits/stdc++.h>
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<y)
update(o<<1|1,md+1,r,x,y,z);
tr[o].sum=tr[o<<1].sum+tr[o<<1|1].sum;
}
long long query(int o,int l,int r,int x,int y)
{
if(x<=l&&r<=y)
return tr[o].sum;
pushdown(o,l,r);
int md=l+r>>1;
long long ret=0;
if(md>=x)
ret+=query(o<<1,l,md,x,y);
if(md<y)
ret+=query(o<<1|1,md+1,r,x,y);
return ret;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf(" %c",&op);
if(op=='?')
{
scanf("%d",&x);
printf("%lld\n",query(1,1,n,1,x));
}
else
{
scanf("%d%d%d",&x,&y,&w);
l=max(x-y,1),r=min(x+y,n);
if(l!=r)
{
update(1,1,n,l,l,w-x+l);
if(r<n)
update(1,1,n,r+1,r+1,r-x-w);
if(l<x)
update(1,1,n,l+1,x,1);
if(x<r)
update(1,1,n,x+1,r,-1);
}
else
update(1,1,n,x,x,w);
}
}
return 0;
}
``````