离奇WA,求助
查看原帖
离奇WA,求助
420129
Nt_Tsumiki楼主2022/1/7 16:22

这两份封装线段树(本题树剖需要用到)有什么区别

//1
namespace segment_tree{
    // int new_val[400001*3],lazy[400001*3];
    // int tree[400001*3];
    int tree[400001*3],lazy[400001*3];
    int new_val[400001*3];

    il void pushdown(int root,int len) {
        lazy[root<<1]+=lazy[root];
        lazy[root<<1|1]+=lazy[root];
        tree[root<<1]+=lazy[root]*(len-(len>>1));
        tree[root<<1|1]+=lazy[root]*(len>>1);
        lazy[root]=0;
    }

    il void upd(int root,int l,int r,int L,int R,int k) {
        if (L<=l and r<=R) {
            lazy[root]+=k;
            tree[root]+=k*(r-l+1);
        } else {
            if (lazy[root]) pushdown(root,(r-l+1));
            if (L<=((l+r)>>1)) upd(root<<1,l,(l+r)>>1,L,R,k);
            if (R>((l+r)>>1)) upd(root<<1|1,((l+r)>>1)+1,r,L,R,k);
            tree[root]=tree[root<<1]+tree[root<<1|1];
        }
    }

    il void ask(int root,int l,int r,int L,int R) {
        if (L<=l and r<=R) {
            res+=tree[root];
            return;
        } else {
            if (lazy[root]) pushdown(root,(r-l+1));
            if (L<=((l+r)>>1)) ask(root<<1,l,(l+r)>>1,L,R);
            if (R>((l+r)>>1)) ask(root<<1|1,((l+r)>>1)+1,r,L,R);
        }
    }
}
using namespace segment_tree;
//2
namespace segment_tree{
    int new_val[400001*3],lazy[400001*3];
    int tree[400001*3];
    // int tree[400001*3],lazy[400001*3];
    // int new_val[400001*3];

    il void pushdown(int root,int len) {
        lazy[root<<1]+=lazy[root];
        lazy[root<<1|1]+=lazy[root];
        tree[root<<1]+=lazy[root]*(len-(len>>1));
        tree[root<<1|1]+=lazy[root]*(len>>1);
        lazy[root]=0;
    }

    il void upd(int root,int l,int r,int L,int R,int k) {
        if (L<=l and r<=R) {
            lazy[root]+=k;
            tree[root]+=k*(r-l+1);
        } else {
            if (lazy[root]) pushdown(root,(r-l+1));
            if (L<=((l+r)>>1)) upd(root<<1,l,(l+r)>>1,L,R,k);
            if (R>((l+r)>>1)) upd(root<<1|1,((l+r)>>1)+1,r,L,R,k);
            tree[root]=tree[root<<1]+tree[root<<1|1];
        }
    }

    il void ask(int root,int l,int r,int L,int R) {
        if (L<=l and r<=R) {
            res+=tree[root];
            return;
        } else {
            if (lazy[root]) pushdown(root,(r-l+1));
            if (L<=((l+r)>>1)) ask(root<<1,l,(l+r)>>1,L,R);
            if (R>((l+r)>>1)) ask(root<<1|1,((l+r)>>1)+1,r,L,R);
        }
    }
}
using namespace segment_tree;
2022/1/7 16:22
加载中...