82pts WA2、4求调!!!@Firecode
查看原帖
82pts WA2、4求调!!!@Firecode
1100403
xuyunao楼主2024/10/20 22:50
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e5+10;
int a[maxn],d[maxn];
int tr[maxn << 2];
int lazy[maxn << 2];
void push_up(int rt)
{
	tr[rt] = tr[rt * 2] + tr[rt*2+1];
}

void build(int rt,int l,int r)
{
	if(l == r)
	{
		tr[rt] = d[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(rt*2,l,mid);
	build(rt*2+1,mid+1,r);
	push_up(rt);
}

void push_down(int rt,int l,int r)
{
	int mid = (l + r) >> 1;
	tr[rt * 2] += (mid - l + 1) * lazy[rt];
	tr[rt * 2 + 1] += (r - mid) * lazy[rt];
	lazy[rt * 2] += lazy[rt];
	lazy[rt * 2 + 1] += lazy[rt];
	lazy[rt] = 0;
}
void update(int rt,int l,int r,int x,int y,int k)
{
	if(l >= x && y >= r)
	{
		lazy[rt] += k;
		tr[rt] += (r - l + 1) * k;
		return;
	}
	int mid = (l + r) >> 1;
	push_down(rt,l,r);
	if(x <= mid) update(rt * 2,l,mid,x,y,k);
	if(y > mid) update(rt*2+1,mid+1,r,x,y,k);
	push_up(rt);
}

int query(int rt,int l,int r,int x,int y)
{
	if(l >= x && y >= r)
	{
		return tr[rt];
	}
	int ans = 0;
	push_down(rt,l,r);
	int mid = (l + r) >> 1;
	if(x <= mid) ans += query(rt*2,l,mid,x,y);
	if(y > mid) ans += query(rt*2+1,mid+1,r,x,y);
	return ans;
}
signed main()
{
	int n,m;
	cin >> n >> m;
	for(int i = 1;i <= n;i++)
	{
		cin >> a[i];
		d[i] = a[i] - a[i-1];
	}
	build(1,1,n);
	int opt,l,r,k,d,p;
	for(int i= 1;i <= m;i++)
	{
		cin >> opt;
		if(opt == 1)
		{
			cin >> l >> r >> k >> d;
			update(1,1,n,l,l,k);
			update(1,1,n,l+1,r,d);
			update(1,1,n,r+1,r+1,-(k+d*(r-l)));
		}
		else
		{
			cin >> p;
			cout << query(1,1,n,1,p) << endl;
		}
	}
	return 0;
}
2024/10/20 22:50
加载中...