求助线段树+差分0pts
查看原帖
求助线段树+差分0pts
941575
Stars_visitor_tyw楼主2023/12/20 22:56
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int a[N], n, m, tag[4*N], tree[4*N];
int diff[400005];
void pushup(int cur)
{
	tree[cur]=tree[cur*2]+tree[cur*2+1];
	return ;
}
void addtag(int cur, int lt, int rt, int val)
{
	tag[cur]+=val;
	tree[cur]+=(rt-lt+1)*val;
	return ;
}
void pushdown(int cur, int lt, int rt)
{
	if(tag[cur]==0)
	{
		return ;
	}
	int mid=lt+rt>>1;
	addtag(cur*2,lt,mid,tag[cur]);
	addtag(cur*2+1,mid+1,rt,tag[cur]);
	tag[cur]=0;
	return ;
} 
void build(int cur, int lt, int rt)
{
	if(lt==rt)
	{
		tree[cur]=diff[lt];
		return ;
	}
	int mid=lt+rt>>1;
	build(cur*2,lt,mid);
	build(cur*2+1,mid+1,rt);
	pushup(cur);
	return ;
}
int query(int cur, int lt, int rt, int qx, int qy)
{
	if(qy<lt||qx>rt)
	{
		return 0;
	}
	if(qx<=lt&&rt<=qy)
	{
		return tree[cur];
	}
	pushdown(cur,lt,rt);
	int mid=lt+rt>>1;
	return query(cur*2,lt,mid,qx,qy)+query(cur*2+1,mid+1,rt,qx,qy);
}
void update(int cur, int lt, int rt, int qx, int qy, int val)
{
	if(qy<lt||qx>rt)
	{
		return ;
	}
	if(qx<=lt&&rt<=qy)
	{
		addtag(cur,lt,rt,val);
		return ;
	}
	pushdown(cur,lt,rt);
	int mid=lt+rt>>1;
	update(cur*2,lt,mid,qx,qy,val);
	update(cur*2+1,mid+1,rt,qx,qy,val);
	pushup(cur);
	return ;
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
        cin>>diff[i];
	}
    for(int i=n-1;i>0;i--)
    {
        diff[i+1]=diff[i+1]-diff[i];
    }
	build(1,1,n);
	while(m--)
	{
		int opt, x, y, first, len;
		cin>>opt>>x;
		if(opt==1)
		{
			cin>>y>>first>>len;
			if(x+1<=y)
			{
			    update(1,1,n,x+1,y,len);
			}
            if(y<n)
            {
                update(1,1,n,y+1,y+1,-(first+len*(y-x)));
            }
		}
		else
		{
			cout<<query(1,1,n,x,x)<<"\n";
		}
	}
	return 0;
}

样例输出:3

2023/12/20 22:56
加载中...