萌新悬关求调连样例都过不去的线段树板子qwq

fish_love_cat @ 2023-07-13 10:33:15

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int maxn=1e5+10;
ll n,m,a[maxn],w[maxn<<2],lazy[maxn<<2];//w=区间和

void pushup(int u){
    w[u]=w[u<<1]+w[(u<<1)+1];
}

void build(int u,int l,int r){
    if(l==r){
        w[u]=a[l];
    }else{
        int mid=(l+r)>>1;
        build(u<<1,l,mid);
        build((u<<1)+1,mid+1,r);
        pushup(u);
    }
}

ll query0(int u,int l,int r,int x){
    if(l==r) return w[u];
    int mid=(l+r)>>1;
    if(mid>=x) return query0(u<<1,l,mid,x);
    return query0((u<<1)+1,1+mid,r,x);
}

void update0(int u,int l,int r,int p,ll x){
    if(l==r){
        w[u]=x;
        return;
    }
    int mid=(l+r)>>1;
    if(mid>=p) update0(u<<1,l,mid,p,x);
    else update0(1+(u<<1),mid+1,r,p,x);
    pushup(u);
}

bool inrg(int l,int r,int l2,int r2){
    return (l2<=l)&&(r<=r2);
}

bool outrg(int l,int r,int l2,int r2){
    return (l>r2)||(r<l2);
}

void mktag(int u,int l,ll x){
    lazy[u]+=x;
    w[u]+=l*x;
}

void pushdown(int u,int l,int r){
    int mid=(l+r)>>1;
    mktag(u<<1,mid-l+1,lazy[u]);
    mktag((u<<1)+1,r-mid,lazy[u]);
    lazy[u]=0;
}

ll query(int u,int l,int r,int l2,int r2){
    if(inrg(l,r,l2,r2)) return w[u];
    if(!outrg(l,r,l2,r2)){
        int mid=(l+r)>>1;
        pushdown(u,l,r);
        return query(u<<1,l,mid,l2,r2)+query((u<<1)+1,mid+1,r,l2,r2);
    }
    return 0;
}

void update(int u,int l,int r,int l2,int r2,ll x){
    if(inrg(l,r,l2,r2)) mktag(u,r-l+1,x);
    if(!outrg(l,r,l2,r2)){
        int mid=(l+r)>>1;
        pushdown(u,l,r);
        update(u<<1,l,mid,l2,r2,x);update((u<<1)+1,mid+1,r,l2,r2,x);
        pushup(u);
    }
}

signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int op,x,y,k;
        cin>>op>>x>>y;
        if(op==1) cin>>k,update(1,1,n,x,y,k);
        else cout<<query(1,1,n,x,y)<<endl;
    }
    return 0;
}

by fish_love_cat @ 2023-07-13 10:35:14

唔，初学，哪里写错了大佬轻喷

by wo_hen_la @ 2023-07-13 10:41:24

我还不会

dalao%%%

by CNS_5t0_0r2 @ 2023-07-13 10:46:16

@fish_love_cat 你的马蜂我看不下去，代码我直接放了：

#include<bits/stdc++.h>
#define int long long 
#define cal int mid = (l + r) / 2,lchild = root * 2,rchild = root * 2 + 1;
#define upd tree[root].val = tree[lchild].val + tree[rchild].val;
using namespace std;
const int N = 1e6 + 9,ROOT = 1;
int a[N];
struct node {
    int val,add;
} tree[N];
void build(int l,int r,int root) {
    if(l == r) {
        tree[root].val = a[l];
        return;
    }
    cal
    build(l,mid,lchild);
    build(mid + 1,r,rchild);
    upd
}
void add_update(int s,int t,int l,int r,int root,int add) { //[s,t]表示查询区间
    if(s <= l && r <= t) { //当前区间为更新区间的子集，直接返回当前区间和
        tree[root].val += (r - l + 1) * add;
        tree[root].add += add;
        return;
    }
    cal
    if(tree[root].add != 0 && l != r) { // 如果当前节点的懒标记非空,则更新当前节点两个子节点的值和懒标记值
        tree[lchild].val += tree[root].add * (mid - l + 1) ;
        tree[rchild].val += tree[root].add * (r - mid);
        tree[lchild].add += tree[root].add;
        tree[rchild].add += tree[root].add;
        tree[root].add = 0;
    }
    if(s <= mid)
        add_update(s,t,l,mid,lchild,add);
    if(t > mid)
        add_update(s,t,mid + 1,r,rchild,add);
    upd
}
int getsum(int s, int t, int l, int r, int root) {
    if(s <= l && r <= t) //当前区间为求和区间的子集，直接返回当前区间和
        return tree[root].val;
    cal
    if(tree[root].add != 0) { // 如果当前节点的懒标记非空,则更新当前节点两个子节点的值和懒标记值
        tree[lchild].val += tree[root].add * (mid - l + 1) ;
        tree[rchild].val += tree[root].add * (r - mid);
        tree[lchild].add += tree[root].add;
        tree[rchild].add += tree[root].add;
        tree[root].add = 0;
    }
    int sum = 0;
    if(s <= mid)
        sum += getsum(s,t,l,mid,lchild);
    if(t > mid)
        sum += getsum(s,t,mid + 1,r,rchild);
    return sum; 
}

int n,m;
int op,x,y,k;
signed main() {
    scanf("%lld%lld", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    build(1,n,ROOT);
    for(int i = 1; i <= m; i++) {
        scanf("%lld%lld%lld", &op, &x, &y);
        if(op == 1) {
            scanf("%lld" ,&k);
            add_update(x,y,1,n,ROOT,k);
        }
        else
            printf("%lld\n", getsum(x,y,1,n,ROOT));
    }
}

by fish_love_cat @ 2023-07-13 10:49:02

@5t0_0r2 额……

by Hua_Liang @ 2023-07-13 10:53:21

@fish_love_cat 请问您真的不是大佬吗？(如此复杂的程序只有大佬才能照着书打出来[掌声][掌声][掌声])

by RisefromtheAshes @ 2023-07-13 11:09:36

@Hua_Liang 6

by Hua_Liang @ 2023-07-13 11:16:55

@Divinity_MING emm......大佬，我想知道一下您为什么有一个作弊者的标？

by fish_love_cat @ 2023-07-13 11:17:29

@Hua_Liang 被脏了

by fish_love_cat @ 2023-07-13 11:29:58

啊！亿眼顶针，鉴定为 update 少了个 else！

此帖结！

by sto_5k_orz @ 2023-07-13 12:57:17

为啥不用树状数组呢？