线段树+差分【p1438】无聊的数列

Description

维护一个数列{a[i]}，支持两种操作：

1、1 L R K D：给出一个长度等于R-L+1的等差数列，首项为K，公差为D，并将它对应加到a[L]~a[R]的每一个数上。即：令a[L]=a[L]+K，a[L+1]=a[L+1]+K+D，

a[L+2]=a[L+2]+K+2D……a[R]=a[R]+K+(R-L)D。

2、2 P：询问序列的第P个数的值a[P]。

Input

第一行两个整数数n，m，表示数列长度和操作个数。

第二行n个整数，第i个数表示a[i]（i=1,2,3…,n）。

接下来的m行，表示m个操作，有两种形式：

1 L R K D

2 P 字母意义见描述（L≤R）。

Output

对于每个询问，输出答案，每个答案占一行。

很明显,这个题需要数据结构来维护。

维护区间,显然我们会想到线段树(貌似写树状数组更简单一些.)

维护一个等差数列会比较麻烦.

但是我们考虑一下等差数列的性质

\[a_{i+1}-a_i=d
\]

此时可以发现,我们维护一下前缀和不就好了.!

但是还可能影响到后面的状态,因此我们在最后减去这些项的和即可.

注意要在一个修改操作的起始位置赋值成\(k\)(首项),然后后面的每一项加上\(d\)即可.

最后如果右端点不为\(n\),我们需要减去前面等差数列的最后一项.

代码

#include<cstdio>

#include<cctype>

#define ls o<<1

#define rs o<<1|1

#define N 100008

#define R register

inline void in(int &x)

{

	int f=1;x=0;char s=getchar();

	while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}

	while(isdigit(s)){x=x*10+s-'0';s=getchar();}

	x*=f;

}

int n,m;

int a[N],tr[N<<2],tg[N<<2];

inline void up(int o)

{

	tr[o]=tr[ls]+tr[rs];

}

inline void down(int o,int l,int r)

{

	if(tg[o])

	{

		tg[ls]+=tg[o];tg[rs]+=tg[o];

		int mid=(l+r)>>1;

		tr[ls]+=(mid-l+1)*tg[o];

		tr[rs]+=(r-mid)*tg[o];

		tg[o]=0;

	}

}

void change(int o,int l,int r,int x,int y,int z)

{

	if(x<=l and y>=r)

	{

		tr[o]+=(r-l+1)*z;

		tg[o]+=z;

		return;

	}

	int mid=(l+r)>>1;

	down(o,l,r);

	if(x<=mid)change(ls,l,mid,x,y,z);

	if(y>mid)change(rs,mid+1,r,x,y,z);

	up(o);

}

int query(int o,int l,int r,int x,int y)

{

	if(x<=l and y>=r)return tr[o];

	down(o,l,r);

	int res=0,mid=(l+r)>>1;

	if(x<=mid)res+=query(ls,l,mid,x,y);

	if(y>mid)res+=query(rs,mid+1,r,x,y);

	return res;

}

int main()

{

	in(n);in(m);

	for(R int i=1;i<=n;i++)in(a[i]);

	for(R int opt,x,y,k,d;m;m--)

	{

		in(opt);

		if(opt==1)

		{

			in(x),in(y),in(k),in(d);

			change(1,1,n,x,x,k);

			if(y>x)change(1,1,n,x+1,y,d);

			if(y!=n)change(1,1,n,y+1,y+1,-(k+(y-x)*d));

		}

		else

		{

			in(x);

			printf("%d\n",a[x]+query(1,1,n,1,x));

		}

	}

}

巴特西

线段树+差分【p1438】无聊的数列

Description

Input

Output

最新文章

热门文章