为什么输入不进去
查看原帖
为什么输入不进去
767779
BD_AZZR_CN楼主2024/8/9 09:08

写了一个dbg,发现操作都对,但是开始的时候全是全是0

#include <bits/stdc++.h>
using namespace std;
constexpr long long MAXN = 50000;
enum operations{
    MULTI = 1,
    ADD = 2
};
class lineTree{
    public:
    long long a[MAXN+1];
    long long d[MAXN+1];//真值
    long long b[MAXN+1];//懒惰标记
    long long k[MAXN+1];//懒惰标记
    inline long long ls(long long n){
        return (n<<1);
    }
    inline long long rs(long long n){
        return ((n<<1)|1);
    }
    void build(long long l,long long r,long long p){//左区间,右区间,当前节点编号
        if(l==r){
            d[p]=a[l];
            b[p]=0;
            k[p]=1;
            return;
        }
        long long mid = (l+r)>>1;
        build(l,mid,ls(p));
        build(mid+1,r,rs(p));
        d[p] = d[ls(p)] + d[rs(p)];
    }
    void make_b_mark(long long p,long long l,long long r){
        long long m = (l + r)/2;
        d[ls(p)] += b[p] * (m-l+1);
        d[rs(p)] += b[p] * (r-m);
        b[ls(p)] += b[p];
        b[rs(p)] += b[p];
        b[p] = 0;
    }
    void make_k_mark(long long p){
        d[ls(p)] *= k[p];
        d[rs(p)] *= k[p];
        k[ls(p)] *= k[p];
        k[rs(p)] *= k[p];
        b[ls(p)] *= k[p];
        b[rs(p)] *= k[p];
        k[p] = 1;
    }
    void update(long long l,long long r,long long c,long long s,long long t,long long p,int opt){
        if(l <= s && t <= r){
            if(opt == ADD){
                d[p] += (t - s + 1) * c;
                b[p] += c;
            }
            else{
                d[p] *= c;
                k[p] *= c;
                b[p] *= c;
            }
            return;
        }
        long long m = (s + t) >> 1;
        make_k_mark(p);
        make_b_mark(p,s,t);
        if(l <= m) update(l,r,c,s,m,ls(p),opt);
        if(r > m) update(l,r,c,m+1,t,rs(p),opt);
        d[p] = d[ls(p)] + d[rs(p)];
    }
    long long sum(long long l,long long r,long long s,long long t,long long p){
        if(l <= s && t<=r)return d[p];
        long long m = ((s + t) >> 1);
        make_k_mark(p);
        make_b_mark(p,s,t);
        long long ret = 0;
        if(l <= m) ret += sum(l,r,s,m,ls(p));
        if(m < r)  ret += sum(l,r,m+1,t,rs(p));
        return ret;
    }
    lineTree(){;};
};
lineTree t;
long long n,m,mod;
void dbg(){
    cout << "DBG:";
    for(int j = 1; j <= n; j++){
        cout << t.sum(j,j,1,n,1) << " ";
    }
    cout << endl;
}
int main(){
    cin >> n >> m >> mod;
    for(long long i = 1; i <= n; i++){
        cin >> t.a[i];
    }
    t.build(1,n,1);
    dbg();
    long long opt,a,b,c;
    for(long long i = 1; i <=m ;i++){
        cin >> opt;
        if(opt == ADD || opt == MULTI){
            cin >> a >> b >> c;
            t.update(a,b,c,1,n,1,opt);
        }
        else{
            cin >> a >> b;
            cout << t.sum(a,b,1,n,1)%mod << endl;
        }
        dbg();
    }
}

dbg表示:都对,但是空中楼阁

2024/8/9 09:08
加载中...