P1438 无聊的数列 全WA求助
  • 板块题目总版
  • 楼主Kketchup
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/8/26 11:00
  • 上次更新2023/10/27 13:38:03
查看原帖
P1438 无聊的数列 全WA求助
551760
Kketchup楼主2022/8/26 11:00
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int N=1e5+10;
#define ls p<<1
#define rs p<<1|1

int n,m;
long long a[N],c[N];

struct segment
{
	int l,r;
	long long dat,lazy;
}t[N<<2];

inline void pushup(int p)
{
	t[p].dat=t[ls].dat+t[rs].dat;
}

inline void pushdown(int p)
{
	if(t[p].lazy!=0)
	{
		t[ls].lazy+=t[p].lazy;
		t[rs].lazy+=t[p].lazy;
		t[ls].dat+=(t[ls].r-t[ls].l+1)*t[p].lazy;
		t[rs].dat+=(t[rs].r-t[rs].l+1)*t[p].lazy;
		t[p].lazy=0;
	}
}

void build(int p,int l,int r)
{
	t[p].l=l;
	t[p].r=r;
	t[p].lazy=0;
	if(l==r)
	{
		t[p].dat=c[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	pushup(p);
}

void update(int p,int l,int r,int k)
{
	if(l<=t[p].l&&t[p].r<=r)
	{
		t[p].dat+=(r-l+1)*k;
		t[p].lazy+=k;
		return ;
	}
	pushdown(p);
	int mid=(t[p].l+t[p].r)>>1;
	if(l<=mid) update(ls,l,mid,k);
	if(mid+1<=r) update(rs,mid+1,r,k);
	pushup(p);
}

long long query(int p,int l,int r)
{
	if(l<=t[p].l&&t[p].r<=r)
	{
		return t[p].dat;
	}
	pushdown(p);
	long long ans=0;
	int mid=(t[p].l+t[p].r)>>1;
	if(l<=mid) ans+=query(ls,l,mid);
	if(mid+1<=r) ans+=query(rs,mid+1,r);
	return ans;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
	{
		scanf("%lld",&a[i]);
	}
	for(int i=n-1;i>0;--i)
	{
		c[i+1]=a[i+1]-a[i];
	}
	build(1,1,n);
	int op,l,r,k,d,x;
	while(m--)
	{
		scanf("%d",&op);
		if(op==1)
		{
			scanf("%d%d%d%d",&l,&r,&k,&d);
			update(1,l,l,k);	
			if(l+1<=r) update(1,l+1,r,d);
			if(r<n) update(1,r+1,r+1,-(k+d*(r-l)));
		}
		else
		{
			scanf("%d",&x);
			printf("%lld\n",query(1,1,x));
		}
	}
	return 0;
}

求助dalao们qwq

2022/8/26 11:00
加载中...