两个lazytag分别维护区间首项和公差,查询是把区间查询当单点用,感觉都很对啊
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
#define ll long long
ll l[4*N],r[4*N],sum[4*N],k[4*N],d[4*N],a[N];
void pushup(int p)
{
sum[p]=sum[p<<1]+sum[p<<1|1];
l[p]=l[p<<1];
r[p]=r[p<<1|1];
}
void pushdown(int p)
{
if(k[p]!=0)
{
k[p<<1]+=k[p];
k[p<<1|1]+=k[p]+d[p]*(l[p<<1|1]-l[p<<1]);
d[p<<1]+=d[p];
d[p<<1|1]+=d[p];
sum[p<<1]+=(2*k[p]+d[p]*(r[p<<1]-l[p]))*(r[p<<1]-l[p]+1)/2;
sum[p<<1|1]+=(2*k[p]+d[p]*(r[p]-l[p]))*(r[p]-l[p]+1)/2-(2*k[p]+d[p]*(r[p<<1]-l[p]))*(r[p<<1]-l[p]+1)/2;
k[p]=0;
d[p]=0;
}
}
void build(int p,int s,int t)
{
if(s==t)
{
sum[p]=a[s];
l[p]=r[p]=s;
return;
}
int mid=s+t>>1;
if(mid>=s)build(p<<1,s,mid);
if(mid+1<=t)build(p<<1|1,mid+1,t);
pushup(p);
}
void update(int p,int s,int t,int K,int D)
{
if(l[p]>=s&&r[p]<=t)
{
sum[p]+=(2*K+D*(r[p]-s))*(r[p]-s+1)/2-(2*K+D*(l[p]-1-s))*(l[p]-s)/2;
k[p]+=K+D*(l[p]-s);
d[p]+=D;
//cout<<l[p]<<' '<<r[p]<<' '<<k[p]<<endl;
return;
}
int mid=l[p]+r[p]>>1;
pushdown(p);
if(mid>=s)update(p<<1,s,t,K,D);
if(mid+1<=t)update(p<<1|1,s,t,K,D);
pushup(p);
//cout<<l[p]<<' '<<r[p]<<' '<<k[p]<<endl;
}
ll query(int p,int s,int t)
{
if(l[p]>=s&&r[p]<=t)
{
//cout<<l[p]<<' '<<r[p]<<' '<<k[p]<<endl;
return sum[p];
}
int mid=l[p]+r[p]>>1;
ll ans=0;
pushdown(p);
if(mid>=s)ans+=query(p<<1,s,t);
if(mid+1<=t)ans+=query(p<<1|1,s,t);
//cout<<l[p]<<' '<<r[p]<<' '<<k[p]<<endl;
return ans;
}
int main()
{
int n,m,cnt=1;
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
build(1,1,n);
for(int i=1;i<=m;i++)
{
int op,s,t;
cin>>op;
if(op==1)
{
int L,R,K,D;
cin>>L>>R>>K>>D;
update(1,L,R,K,D);
}
else
{
int P;
cin>>P;
cout<<cnt++<<' '<<query(1,P,P)<<endl;
}
}
}