社区讨论
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 条回复,欢迎继续交流。
正在加载回复...