写了一个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表示:都对,但是空中楼阁