标签：return 数列 无聊 mid long cin build change
- 通过这道题，了解了标记永久化的思想，也加深了对线段树的理解~
- 另外，这道题也是可以将原数组转化成差分数组做
点击查看代码
#include <bits/stdc++.h>
using namespace std;
long long a[100005];
struct t1
{
long long l,r;
long long k,d;
}t[400005];
void build(long long p,long long l,long long r)
{
t[p].l=l;
t[p].r=r;
t[p].k=t[p].d=0;
if(l==r)
{
t[p].k=a[l];
return;
}
long long mid=(l+r)>>1;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
}
void change(long long p,long long l,long long r,long long k,long long d)
{
if(l<=t[p].l&&r>=t[p].r)
{
t[p].k+=(k+(t[p].l-l)*d);
t[p].d+=d;
return;
}
long long mid=(t[p].l+t[p].r)>>1;
if(l<=mid)
{
change(p*2,l,r,k,d);
}
if(r>mid)
{
change(p*2+1,l,r,k,d);
}
}
long long ask(long long p,long long x)
{
if(t[p].l==t[p].r)
{
return t[p].k;
}
long long mid=(t[p].l+t[p].r)>>1;
long long va=t[p].k+(x-t[p].l)*t[p].d;
if(x<=mid)
{
va+=ask(p*2,x);
}
else
{
va+=ask(p*2+1,x);
}
return va;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
long long n,m;
cin>>n>>m;
for(long long i=1;i<=n;i++)
{
cin>>a[i];
}
build(1,1,n);
for(long long i=1;i<=m;i++)
{
long long opt;
cin>>opt;
if(opt==1)
{
long long l,r,k,d;
cin>>l>>r>>k>>d;
change(1,l,r,k,d);
}
else
{
long long p;
cin>>p;
cout<<ask(1,p)<<"\n";
}
}
return 0;
}
标签：return,
数列,
无聊,
mid,
long,
cin,
build,
change
From： https://www.cnblogs.com/watersail/p/18471034