91pts #2wa 求调
查看原帖
91pts #2wa 求调
856517
mikisayaka楼主2023/6/28 12:12

两个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;
		}
	}
}

2023/6/28 12:12
加载中...