蜂蜜柚子茶(Honey grapefruit tea)

题目描述

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

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

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

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

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

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

\(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。

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

注意,初始时所有饮品都为正常糖量,可被认为是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<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;
}