线♂段♂树♂性♂感♂代♂码♂在♂线♂求♂调

liangbob @ 2023-03-11 22:53:21

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
const int N = 1e5 + 10;

struct node
{
    int l, r, d, z;
};
node t[N << 2];
int a[N];

void down(int k)
{
    if(t[k].z)
    {
        int lc = k * 2;
        int rc = k * 2 + 1;
        t[lc].z += t[k].z;
        t[lc].d += t[k].z * (t[lc].r - t[lc].l + 1);
        t[rc].z += t[k].z;
        t[rc].d += t[k].z * (t[rc].r - t[rc].l + 1);
        t[k].z = 0;
    }
}

void build(int k, int l, int r)
{
    t[k].l = l;
    t[k].r = r;
    if(l == r)
    {
        t[k].d = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    int lc = k * 2;
    int rc = k * 2 + 1;
    build(lc, l, mid);
    build(rc, mid + 1, r);
    t[k].d = t[lc].d + t[rc].d;
}

void update(int k, int l, int r, int p)
{
    if(t[k].l == l && t[k].r == r)
    {
        t[k].d += t[k].d * (t[k].r - t[k].l + 1);
        t[k].z += p;
        return;
    }
    down(k);
    int mid = (t[k].l + t[k].r) / 2;
    int lc = k * 2;
    int rc = k * 2 + 1;
    if(r <= mid)
    {
        update(lc, l, r, p);    
    }
    else if(l > mid)
    {
        update(rc, l, r, p);
    }
    else
    {
        update(lc, l, mid, p);
        update(rc, mid + 1, r, p);
    } 
    t[k].d = t[lc].d + t[rc].d;
}

int query(int k, int l, int r)
{
    if(t[k].l == l && t[k].r == r)
    {
        return t[k].d;
    }
    down(k);
    int mid = (t[k].l + t[k].r) / 2;
    int lc = k * 2;
    int rc = k * 2 + 1;
    if(r <= mid)
    {
        return query(lc, l, r);
    }
    else if(l > mid)
    {
        return query(rc, l, r);
    }
    else
    {
        return query(lc, l, mid) + query(rc, mid + 1, r);
    }
}

signed main()
{
    int n;
    cin >> n;
    int q;
    cin >> q;
    for(int i = 1;i <= n;i++) scanf("%lld ", &a[i]);
    build(1, 1, n);
    while(q--)
    {
        int op;
        scanf("%lld", &op);
        if(op == 1)
        {
            int x, y, k;
            scanf("%lld %lld %lld", &x, &y, &k);
            update(1, x, y, k);
        }
        else
        {
            int x, y;
            scanf("%lld %lld", &x, &y);
            printf("%lld\n", query(1, x, y));
        }
    }
    return 0;
}

by wpy233 @ 2023-03-11 22:56:35

@liangbob 老♂年♂退♂役♂选♂手♂在♂线♂摆♂烂

by RP_INT_MAX @ 2023-03-11 22:56:46

btd(?)

by REMAC @ 2023-03-11 22:58:27

您不能指望线段树的节点正好等于所选区间……

if(t[k].l == l && t[k].r == r)

应为

if(t[k].l >= l && t[k].r <= r)

(也AFO，可能不对)

@liangbob

by REMAC @ 2023-03-11 22:59:21

以及，确实btd（？？）

by Light_az @ 2023-03-11 23:00:26

性感标题党在线求调

by ssytxy2024 @ 2023-03-11 23:13:35

@Light_az 是不是还要加个教育的教

by __cheems__ @ 2023-03-11 23:18:33

怎么感觉代码那么相似

by __cheems__ @ 2023-03-11 23:18:51

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<fstream>
#include<cmath>
#include<cstring>
#include<string>
#include<queue>
using namespace std;
const int N = 1e5+10;
#define int long long
struct node
{
    int l,r,lazy,num;
}tr[N<<2];
int n , m ,a[N];
void push_up(int id)
{
    tr[id].num = tr[id<<1].num + tr[id<<1|1].num;
}
void push_down(int id)
{
    tr[id<<1].num += tr[id].lazy *(tr[id<<1].r - tr[id<<1].l + 1);
    tr[id<<1|1].num += tr[id].lazy *(tr[id<<1|1].r - tr[id<<1|1].l + 1);

    tr[id<<1].lazy += tr[id].lazy;
    tr[id<<1|1].lazy += tr[id].lazy;

    tr[id].lazy = 0;
}
void build(int id , int l , int r)
{
    tr[id].l = l , tr[id].r = r;
    tr[id].lazy = tr[id].num = 0;
    if(l == r)
    {
        tr[id].num = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(id << 1 , l , mid);
    build(id << 1|1 , mid + 1 , r);
    push_up(id);
}
void add(int id , int l , int r , int k)
{
    if(tr[id].l > r || tr[id].r < l) return;

    if(tr[id].l >= l && tr[id].r <= r)
    {
        tr[id].num += k*(tr[id].r - tr[id].l + 1);
        tr[id].lazy += k;
        return;
    }
    if(tr[id].lazy)
        push_down(id);

    add(id << 1 , l , r, k);
    add(id << 1|1 , l , r, k);

    push_up(id);
}
int calc(int id , int l , int r)
{
    if(tr[id].l > r || tr[id].r < l) return 0;
    if(tr[id].l >= l && tr[id].r <= r)
        return tr[id].num;
    push_down(id);
    return calc(id<<1, l , r) + calc(id<<1|1,l , r);
}
signed main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1 ; i<= n ; i++)
        cin >> a[i];
    build(1,1,n);
    while(m--)
    {
        int opt , x, y;
        cin >> opt >> x >> y;
        if(opt&1)
        {
            int k;
            cin >> k;
            add( 1 , x , y , k);
        }
        else 
            cout << calc(1 , x, y) << endl;
    }
    return 0;
}