12.2日志

1.P1438 无聊的数列 - 洛谷 | 计算机科学教育新生态

线段树 + 差分,一开始的思路是直接将整个等差数列加到线段树中,但是pushdown不好维护于是改变思路,想到我们可以去维护a的差分数组,这样一来对[l , r]加上一个首项为看，公差为d的等差数列其实就是在l上加k，[l + 1 ~ r]上加d,之后我们求第p项也转变成求[1 ~ p]的区间和即可，一开始多尝试新思路,不要在困难的思路上折磨自己,多想少code

#define yyy cout<<"Yes"<<"\n" 
#define nnn cout<<"No"<<"\n" 
#define x first 
#define y second
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<ll , ll> pii;
typedef pair<int , string> pis;
const int N = 1e5 + 10,inf = 0x3f3f3f3f,mod = 1e9 + 7;
const double pi = 3.1415926535898;

struct node
{
    int l,r;
    ll sum,add;
}tr[4 * N];

int n,m;
ll a[N],b[N];

void pushup(node &u,node &l,node &r)
{
    u.sum = l.sum + r.sum;
}

void pushup(int u)
{
    pushup(tr[u] , tr[u << 1] , tr[u << 1 | 1]);
}

void pushdown(node &u,node &l,node &r)
{
    if(u.add)
    {
        l.sum += (l.r - l.l + 1) * u.add;
        r.sum += (r.r - r.l + 1) * u.add;
        l.add += u.add,r.add += u.add;
        u.add = 0;
    }
}

void pushdown(int u)
{
    pushdown(tr[u] , tr[u << 1] , tr[u << 1 | 1]);
}

void build(int u,int l,int r)
{
    if(l == r)
    {
        tr[u] = {l , r , b[l] , 0};
    }else
    {
        tr[u] = {l , r};
        int mid = (l + r) / 2;
        build(u << 1 , l , mid);
        build(u << 1 | 1 , mid + 1 , r);
        pushup(u);
    }
}

void modify(int u,int l,int r,ll d)
{
    if(tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].sum += (tr[u].r - tr[u].l + 1) * d;
        tr[u].add += d;
    }else
    {
        int mid = (tr[u].l + tr[u].r) / 2;
        pushdown(u);
        if(l <= mid)
        {
            modify(u << 1 , l , r , d);
        }
        if(r > mid)
        {
            modify(u << 1 | 1 , l , r , d);
        }
        pushup(u);
    }
}

node query(int u,int l,int r)
{
    if(tr[u].l >= l && tr[u].r <= r)
    {
        return tr[u];
    }else
    {
        int mid = (tr[u].l + tr[u].r) / 2;
        pushdown(u);
        if(r <= mid)
        {
            return query(u << 1 , l , r);
        }else if(l > mid)
        {
            return query(u << 1 | 1 , l , r);
        }else
        {
            node left = query(u << 1 , l , r);
            node right = query(u << 1 | 1 , l , r);
            node res;
            pushup(res , left , right);
            return res;
        }
    }
}

int main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

    cin>>n>>m;
    for(int i = 1 ; i <= n ; i++)
    {
        cin>>a[i];
        b[i] = a[i] - a[i - 1];
    }        

    build(1 , 1 , n);

    while(m--)
    {
        int op;
        cin>>op;
        if(op == 1)
        {
            ll l,r,d,k;
            cin>>l>>r>>k>>d;
            modify(1 , l , l , k);
            if(r + 1 <= n)
            {
                modify(1 , r + 1 , r + 1 , - k);
            }
            if(r > l)
            {
                modify(1 , l + 1 , r , d);
                if(r + 1 <= n)
                {
                    modify(1 , r + 1 , r + 1 , -d * (r - l));
                }   
            }
        }else
        {
            int p;
            cin>>p;
            cout<<query(1 , 1 , p).sum<<"\n";
        }
    }
    return 0;
}


// 5 8
// 1 2 3 4 5
// 1 2 4 1 2
// 1 3 5 4 9
// 1 1 2 1 2
// 2 1
// 2 2
// 2 3
// 2 4
// 2 5

// 2 
// 6
// 10
// 22
// 27