树状数组+二次差分只过一个点求助(悬赏关注
查看原帖
树状数组+二次差分只过一个点求助(悬赏关注
569235
w9095楼主2023/4/30 14:57
#include <bits/stdc++.h>
using namespace std;
long long n,m,a[100010],b1[100010],b2[100010],c1[100010],c2[100010];
long long lowbit(long long x)
{
	return x&(-x);
}

void add(long long c[],long long x,long long d)
{
	while(x<=n)c[x]+=d,x+=lowbit(x);
}

long long getsum(long long c[],long long x)
{
	long long ans=0;
	while(x>0)ans+=c[x],x-=lowbit(x);
	return ans;
}

void change()
{
	long long l,r,k,d;
	scanf("%lld%lld%lld%lld",&l,&r,&k,&d);
	add(c1,l,k);add(c2,l,k*l);
	if(l+1<=r)add(c1,l+1,d-k);add(c2,l+1,(d-k)*(l+1));
	if(r+1<=n)add(c1,r+1,-k-(r-l+1)*d);add(c2,r+1,(-k-(r-l+1)*d)*(r+1));
}

long long query()
{
	long long x;
	scanf("%lld",&x);
	return getsum(c1,x)*(x+1)-getsum(c2,x);
}

int main()
{
	scanf("%lld%lld",&n,&m);
	for(long long i=1;i<=n;i++)
	    {
	    scanf("%lld",&a[i]);
	    b1[i]=a[i]-a[i-1];
	    b2[i]=b1[i]-b1[i-1];
	    }
	for(long long i=1;i<=n;i++)add(c1,i,b2[i]);
	for(long long i=1;i<=n;i++)add(c2,i,b2[i]*i);
	for(long long i=1;i<=m;i++)
	    {
	    	long long op;
	    	scanf("%lld",&op);
	    	if(op==1)change();
	    	else if(op==2)printf("%lld\n",query());
		}
	return 0;
}
2023/4/30 14:57
加载中...