Ciao a tutti, sto avendo problemi a implementare un segment tree con lazy propagation nel problema segtree. In particolare il mio codice è corretto in tutti i casi del subtask 2, tranne 1, e quasi sempre scorretto negli altri subtask.
Qualcuno potrebbe aiutarmi a trovare eventuali bug nel mio codice?
#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
struct Node {
long long sum;
long long min;
long long lazyset;
long long lazyadd;
Node() : sum(0), min(INT_MAX), lazyset(0), lazyadd(0) {};
};
vector<Node> tree;
int reals=1; // size of the tree
void init(vector<long long> a) {
int size = a.size();
while(reals<a.size()) {
reals*=2;
}
tree.resize(2*reals);
for(int i=0;i<a.size();i++) {
tree[reals+i].min=a[i];
tree[reals+i].sum=a[i];
}
for(int i=reals-1;i>0;i--) {
tree[i].sum=tree[2*i].sum+tree[2*i+1].sum;
tree[i].min=min(tree[2*i].min, tree[2*i+1].min);
}
}
void uplset(int k, int x, int y, long long rx) { // lazy set update
int d = y-x;
int lazy = tree[k].lazyset;
tree[k].sum=d*rx;
if(k<reals) {
tree[k*2].lazyset=lazy;
tree[k*2+1].lazyset=lazy;
}
tree[k].lazyset=0;
}
void upladd(int k, int x, int y, long long rx) { // lazy add update
int d = y-x;
int lazy = tree[k].lazyadd;
tree[k].sum+=d*rx;
if(k<reals) {
tree[k*2].lazyadd=lazy;
tree[k*2+1].lazyadd=lazy;
}
tree[k].lazyadd=0;
}
long long rsum(int a, int b, int k, int x, int y) {
if(tree[k].lazyadd!=0) {
upladd(k,x,y,tree[k].lazyadd);
}
if(tree[k].lazyset!=0) {
uplset(k,x,y,tree[k].lazyset);
}
if(b<=x||a>=y) return 0;
if(a<=x&&b>=y) return tree[k].sum;
int d = (x+y)/2;
return rsum(a, b, 2*k, x, d) + rsum(a, b, 2*k+1, d, y);
}
long long get_sum(int l, int r) {
return rsum(l, r, 1, 0, reals);
}
void rladd(int a, int b, int k, int x, int y, long long rx) {
if(tree[k].lazyadd!=0) {
upladd(k,x,y,tree[k].lazyadd);
}
if(tree[k].lazyset!=0) {
uplset(k,x,y,tree[k].lazyset);
}
if(y<=a||x>=b) return;
if(x>=a&&y<=b) {
tree[k].lazyadd=rx;
} else {
int d=(x+y)/2;
rladd(a,b,2*k,x, d,rx);
rladd(a,b,2*k+1,d, y,rx);
long long uno = tree[k*2].lazyadd ? tree[k*2].sum+tree[k*2].lazyadd*(d-x) : tree[k*2].sum;
long long due = tree[k*2+1].lazyadd ? tree[k*2].sum+tree[k*2+1].lazyadd*(d-x) : tree[k*2+1].sum;
tree[k].sum=uno+due;
}
}
void add(int l, int r, long long x) {
return rladd(l,r,1,0,reals, x);
}
void rlset(int a, int b, int k, int x, int y, long long rx) {
if(tree[k].lazyadd!=0) {
upladd(k,x,y,tree[k].lazyadd);
}
if(tree[k].lazyset!=0) {
uplset(k,x,y,tree[k].lazyset);
}
if(y<=a||x>=b) return;
if(x>=a&&y<=b) {
tree[k].lazyset=rx;
} else {
int d=(x+y)/2;
rlset(a,b,2*k,x, d,rx);
rlset(a,b,2*k+1,d, y,rx);
long long uno = tree[k*2].lazyset ? tree[k*2].lazyset*(d-x) : tree[k*2].sum;
long long due = tree[k*2+1].lazyset ? tree[k*2+1].lazyset*(d-x) : tree[k*2+1].sum;
tree[k].sum=uno+due;
}
}
void set_range(int l, int r, long long x) {
rlset(l,r,1,0,reals,x);
}