RE+WA求助
查看原帖
RE+WA求助
703022
wuyixiang楼主2024/7/7 17:01
#include <iostream>
#define int long long
using namespace std;
int n,m,a[800005],c,d,e,f,g;
struct node
{
    int ze,ye,sum,add;
}tr[800005];
void pushup(int p)
{
    tr[p].sum = tr[p * 2 + 1].sum + tr[p * 2 + 2].sum;
}
void pushdown(int p)
{
	tr[p * 2 + 1].sum += tr[p].add * (tr[p * 2 + 1].ye - tr[p * 2 + 1].ze + 1);
	tr[p * 2 + 2].sum += tr[p].add * (tr[p * 2 + 2].ye - tr[p * 2 + 2].ze + 1);
	tr[p * 2 + 1].add += tr[p].add;
	tr[p * 2 + 2].add += tr[p].add;
	tr[p].add = 0;
}
void build(int p,int x,int y)
{
    tr[p] = {x,y,a[x],0};
    if(x == y){return ;}
    build(p * 2 + 1,x,(x + y) >> 1);
    build(p * 2 + 2,((x + y) >> 1) + 1,y);
    pushup(p);
}
void jia(int x,int u,int v,int k)
{
    pushdown(x);
	if(tr[x].ze == u && v == tr[x].ye)
	{
		tr[x].sum += (v - u + 1) * k;
		tr[x].add += k;
		return ;
	}
	int mid = (tr[x].ze + tr[x].ye) >> 1;
	if(u <= mid)jia(x * 2 + 1,u,min(v,mid),k);
	if(v > mid)jia(x * 2 + 2,max(u,mid + 1),v,k);
	pushup(x);
}
int query(int x,int u,int v)
{
    pushdown(x);
	int num = 0;
	if(tr[x].ze == u && v == tr[x].ye)return tr[x].sum;
	int mid = (tr[x].ze + tr[x].ye) >> 1;
	if(u <= mid)num += query(x * 2 + 1,u,min(v,mid));
	if(v > mid)num += query(x * 2 + 2,max(u,mid + 1),v);
	return num;
}
signed main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i ++)cin >> a[i];
    for(int i = n;i >= 1;i --)a[i] -= a[i - 1];
    build(0,1,n);
    for(int i = 1;i <= m;i ++)
    {
        scanf("%lld",&c);
        if(c == 1)
        {
            cin >> d >> e >> f >> g;
            jia(0,d,d,f);
            if(d != e)jia(0,d + 1,e,g);
            jia(0,e + 1,e + 1,f + (e - d) * g);
        }
        else
        {
            cin >> d;
            cout << query(0,1,d) << '\n';
        }
    }
}
2024/7/7 17:01
加载中...