社区讨论

NI_MA 为什么我这个不是差分的线段树错了!!??

P1438无聊的数列参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@m1qffjq5
此快照首次捕获于
2024/10/01 20:40
去年
此快照最后确认于
2024/10/01 23:31
去年
查看原帖
RT
CPP
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
il ll read()
{
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x*f;
}
const int N=1e7+7;
ll n,m;
ll opt,l,r,D,K,q;
ll arr[N];
ll tre[N];
ll tsl[N];
ll dsl[N];
il void lazy(ll i,ll K,ll D)
{
	tsl[i]+=K,dsl[i]+=D;
}
il void down(ll i,ll n)
{
	if(tsl[i]!=0&&dsl[i]!=0)
	{
		lazy(i<<1,tsl[i],dsl[i]);
	    lazy(i<<1|1,tsl[i]+dsl[i]*n,dsl[i]);
	    tsl[i]=0,dsl[i]=0;
	}
}
il void build(ll l,ll r,ll i)
{
	if(l==r) tre[i]=arr[l];
	else 
	{
		ll mid=(l+r)>>1;
		build(l,mid,i<<1);
		build(mid+1,r,i<<1|1);
	}
}
il void change(ll jobl,ll jobr,ll jobK,ll jobD,ll l,ll r,ll i)
{
	if(jobl<=l&&jobr>=r) lazy(i,jobK,jobD);
	else 
	{
		ll mid=(l+r)>>1;
		down(i,mid-l+1);
		ll L=max((ll)0,mid-jobl+1);
		if(jobl<=mid) change(jobl,jobr,jobK,jobD,l,mid,i<<1);
		if(jobr>mid) change(jobl,jobr,jobK+L*jobD,jobD,mid+1,r,i<<1|1);
	}
}
il ll query(ll jobn,ll l,ll r,ll i)
{
	if(l==r&l==jobn) return tsl[i];
	ll mid=(l+r)>>1,ans;
	down(i,mid-l+1);
	if(jobn<=mid) ans=query(jobn,l,mid,i<<1);
	if(jobn>mid) ans=query(jobn,mid+1,r,i<<1|1);
	return ans;
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++) arr[i]=read();
	build(1,n,1);
	for(int i=1;i<=m;i++)
	{
		opt=read();
		if(opt==1)
		{
			l=read(),r=read(),K=read(),D=read();
			change(l,r,K,D,1,n,1);
		}
		if(opt==2)
		{
			q=read();
			printf("%lld\n",query(q,1,n,1)+arr[q]);
		}
	}
}
/*
5 8
1 2 3 4 5
1 2 4 -1 -2
1 5 5 -100 -999
1 1 5 1 1
2 1
2 2
2 3
2 4
2 5

2
3
3
3
-90
*/

回复

0 条回复,欢迎继续交流。

正在加载回复...