请教一下,这样维护首项和公差为何会错
查看原帖
请教一下,这样维护首项和公差为何会错
554480
行者学数学楼主2022/3/16 10:49
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<stdlib.h>
using namespace std;
typedef long long ll;
const int N = 1e5  +5;
int n, m, a[N];

struct T
{
    int l, r;
    ll s, lz1, lz2;
}tree[N<<2];

void build(int l,int r,int p)
{
    if(l == r)
    {
        tree[p].l = tree[p].r = l;
        tree[p].s = a[l];
        return ;
    }
    tree[p].l = l, tree[p].r = r;
    int mid = (tree[p].l + tree[p].r)>>1;
    build(l, mid, p<<1);
    build(mid+1, r, p<<1|1);
    tree[p].s = tree[p<<1].s + tree[p<<1|1].s;
}

void spread(int p)
{
    if(tree[p].lz1 || tree[p].lz2)
    {
        int len = tree[p<<1].r - tree[p<<1].l + 1; ll a1 = tree[p].lz1, d = tree[p].lz2;
        tree[p<<1].s += (ll) len*a1 +ll(len)*(len-1)*d/2;
        tree[p<<1].lz1 += a1;
        tree[p<<1].lz2 += d;
        a1 = a1 + len*d , len = tree[p<<1|1].r - tree[p<<1|1].l +1;
        tree[p<<1|1].s +=(ll) len*a1 +ll(len)*(len-1)*d/2;
        tree[p<<1|1].lz1 += a1;
        tree[p<<1|1].lz2 += d;
        tree[p].lz1 = tree[p].lz2 = 0;
    }
}

void update(int cl,int cr, ll a1,ll d,int p)
{
    if(cl <= tree[p].l && tree[p].r <=cr)
    {
        int len = tree[p].r - tree[p].l+1;
        tree[p].s +=(ll) len*a1 +(ll)len*(len-1)*d/2;
        tree[p].lz1 += a1, tree[p].lz2 += d;
        return;
    }
    spread(p);
    int mid = (tree[p].l + tree[p].r)>>1;
    if(cl <= mid)  update(cl, cr, a1, d, p<<1);
    if(mid < cr)   update(cl, cr, a1+d*(mid-cl+1), d, p<<1|1);
    tree[p].s = tree[p<<1].s + tree[p<<1|1].s;
}

ll query(int q,int p)
{
    if(tree[p].l == tree[p].r && tree[p].l == q)   return tree[p].s;
    spread(p);
    int mid = (tree[p].l + tree[p].r)>>1;
    if(q <= mid)  return query(q, p<<1);
    else   return query(q, p<<1|1);
} 

int main()
{
    cin >>n >> m;
    for(int i=1; i<=n; ++i)  scanf("%d",&a[i]);
    build(1, n, 1);
    int opt, l, r, k, d;
    while(m--)
    {
        scanf("%d",&opt);
        if(opt == 1)
        {
            cin >> l>> r>>k >> d;
            update(l,r, k, d,1);
        }
        else
        {
            cin >> k;
            cout<<query(k, 1)<<endl;
        }
    }
}
2022/3/16 10:49
加载中...