发现一种很新奇的思路,不到50行
查看原帖
发现一种很新奇的思路,不到50行
777846
Feny_233楼主2024/8/14 17:12

不用懒标记,不用差分,直接把答案加起来

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+114;
int n,q,a[N],k[4*N],d[4*N]; 
void update(int x,int l,int r,int L,int R,int K,int D)
{
	if(l>R||r<L) return;
	if(l>=L&r<=R){
		k[x]+=K+(l-L)*D;
		d[x]+=D;
		return;
	}
	int mid=l+r>>1;
	update(x<<1,l,mid,L,R,K,D);
	update(x<<1|1,mid+1,r,L,R,K,D);
}
int query(int x,int l,int r,int P)
{
	if(l>P||r<P) return 0;
	if(l==r) return k[x];
	int mid=l+r>>1;
	return k[x]+(P-l)*d[x]+query(x*2,l,mid,P)+query(x*2+1,mid+1,r,P);
}

signed main()
{
	cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>a[i];
	while(q--)
	{
		int opt;
		cin>>opt;
		if(opt==1){
			int l,r,K,D;
			cin>>l>>r>>K>>D;
			update(1,1,n,l,r,K,D);
		}
		else if(opt==2){
			int p;
			cin>>p;
			cout<<query(1,1,n,p)+a[p]<<'\n';
		}
	}
	return 0;
}
2024/8/14 17:12
加载中...