Implement a segment tree 20/100

il mio programma funziona per la subtask 2 poi fa molti errori in tutte le altre (stranamente non va in TLE), per scriverlo ho preso spunto da questa guida.
Ecco il codice:

#pragma GCC optimize ("Ofast") 
#pragma GCC optimization ("unroll-loops")
#define valore_di(x) cerr <<"il valore di "<< #x << " è " << x << endl;
#include <bits/stdc++.h>
#define MAXN 1500000
#define INF numeric_limits<int>::max()
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ip;

struct Node{
	ll val;		//the value for leafs and the min for others (si, mi piace scrivere in inglese)
	ll sum;		//only non leafs node need this
	bool same;	//true if every child has the same value
	ll add;		//the quantity to add to childrens
	int childrens;
	int index;
	Node(){
		add=0;
		same=false;
		childrens=1;
	}
};

Node t[4*MAXN];
int n;

void push (int v){
	if (t[v].same) {
		t[v*2].val = t[v*2+1].val = t[v].val;
		t[v*2].sum = t[v].val*t[v*2].childrens;	t[v*2+1].sum = t[v].val*t[v*2+1].childrens;
		t[v*2].same = t[v*2+1].same = true;
		t[v].same = false;
	}
	else {
		t[v*2].add += t[v].add;
		t[v*2+1].add += t[v].add;
		t[v*2].val += t[v].add;
		t[v*2+1].val += t[v].add;
		t[v*2].sum += t[v].add*t[v*2].childrens;
		t[v*2+1].sum += t[v].add*t[v*2+1].childrens;
		t[v].add=0;
	}
	//cout<<v*2<<" "<<t[v*2].sum<<" "<<t[v*2].add<<" "<<t[v*2].val<<" "<<t[v*2].childrens<<endl;
	//cout<<v*2+1<<" "<<t[v*2+1].sum<<" "<<t[v*2+1].add<<" "<<t[v*2+1].val<<" "<<t[v*2+1].childrens<<endl<<endl;
}

void build(vector<ll> &a, int v, int tl, int tr) {
    if (tl == tr) {
        t[v].val = t[v].sum = a[tl];
        t[v].index = tl;
        //cout<<v<<" "<<tl<<" "<<tr<<" "<<a[tl]<<endl;
    } else {
    	//cout<<v<<" "<<tl<<" "<<tr<<endl;
        int tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        t[v].val = min(t[v*2].val , t[v*2+1].val);
		t[v].sum = t[v*2].sum + t[v*2+1].sum;
		t[v].childrens = t[v*2].childrens+t[v*2+1].childrens;
    }
}

void init(vector<ll> a) {
	n=a.size();
	build (a, 1, 0, n-1);
	/*for (int i=0; i<n; i++) t[i+n].val = t[i+n].sum = a[i];
	for (int i=n-1; i>0; i--){
		t[i].val = min(t[i*2].val , t[i*2+1].val);
		t[i].sum = t[i*2].sum + t[i*2+1].sum;
		t[i].childrens = max(t[i*2].childrens, 1)*2;
	}*/
	for(int i=1;i<26;i++) cout<<t[i].sum<<" ";cout<<endl;
}

ll sum(int v, int tl, int tr, int l, int r) {
    if (l > r) return 0;
    if (l == tl && r == tr){
    	if(tl==tr) return t[v].val;		//se v è una foglia rirorna val e non sum
		return t[v].sum;
	}
	push(v);
    int mid = (tl + tr) / 2;
    if(t[v].same)return t[v].val*t[v].childrens;	//(r-l) è il numero di nodi figli
    return sum(v*2, tl, mid, l, min(r, mid)) + sum(v*2+1, mid+1, tr, max(l, mid+1), r) + t[v].add;
}

long long get_sum(int l, int r) {
	return sum(1, 0, n-1, l, r-1);
}

ll addrange(int v, int tl, int tr, int l, int r, int addend) {
    if (l > r) return 0;
    if (l == tl && tr == r) {
    	if (!t[v].same) t[v].add += addend;
        t[v].val += addend;
        t[v].sum += addend*(r-l+1);
        return addend*(r-l+1);
    } else {
        push(v);
        int tm = (tl + tr) / 2;
        ll x = addrange(v*2, tl, tm, l, min(r, tm), addend);
        ll y = addrange(v*2+1, tm+1, tr, max(l, tm+1), r, addend);
        t[v].val = min(t[v*2].val, t[v*2+1].val);
        t[v].sum += x+y;
        //cout<<v<<" "<<x<<" "<<y<<endl;
        return x+y;
    }
}

void add(int l, int r, long long x) {
	addrange(1, 0, n-1, l, r-1, x);
	for(int i=1;i<26;i++) cout<<t[i].sum<<" ";cout<<endl;
}

ip setrange(int v, int tl, int tr, int l, int r, int new_val) {
    if (l > r) return {0,t[v].val};
    //cout<<v<<" "<<tl<<" "<<tr<<" "<<l<<" "<<r<<endl;
    if (l == tl && tr == r) {
    	ll sumT = new_val - t[v].val;
        t[v].val = new_val;
        t[v].sum = new_val*t[v].childrens;
        t[v].same = true;
        return {sumT*t[v].childrens , new_val};		//{differenza da aggiungere a sum , valore minimo}
    } else {
        push(v);
        int mid = (tl + tr) / 2;
        ip x = setrange(v*2, tl, mid, l, min(r, mid), new_val);
        ip y = setrange(v*2+1, mid+1, tr, max(l, mid+1), r, new_val);
        t[v].val = min(x.second,y.second);
        t[v].sum = t[v*2].sum + t[v*2+1].sum;
        //cout<<v<<" "<<x.first<<" "<<y.first<<endl;
        return {x.first+y.first, t[v].val};
    }
}

void set_range(int l, int r, long long x) {
	setrange(1, 0, n-1, l, r-1, x);
	//for(int i=1;i<26;i++) cout<<t[i].sum<<" ";cout<<endl;
}

ll getmin(int v, int ll, int rr, int l, int r){
	//cout<<v<<" "<<ll<<" "<<rr<<" "<<l<<" "<<r<<endl;
    if (l > r) return INF;
    //if (l <= ll && rr <= r)cout<<t[v].val<<endl;
	if (l <= ll && rr <= r) return t[v].val;
	push(v);
	int mid = (ll+rr)/2;
	return min(getmin(v*2,ll,mid,l,min(r,mid)),getmin(v*2+1,mid+1,rr,max(l,mid+1),r));
}

long long get_min(int l, int r) {
    return getmin (1,0,n-1,l,r-1);				//controllare n-1
}

int find(int v, int tl, int tr, int l, int r, ll x){	//copia incollata
	if(tl > r || tr < l) return -1;
    if(l <= tl && tr <= r) {
        if(t[v].val >= x) return -1;
        while(tl != tr) {
            int mid = tl + (tr-tl)/2;
            if(t[2*v].val <= x) {
                v = 2*v;
                tr = mid;
            }else {
                v = 2*v+1;
                tl = mid+1;
            }
        }
        return tl;
    }

    int mid = tl + (tr-tl)/2;
    int rs = find(2*v, tl, mid, l, r, x);
    if(rs != -1) return rs;
    return find(2*v+1, mid+1, tr, l ,r, x);
}

int lower_bound(int l, int r, long long x) {
	return find (1, 0,n-1,l, r, x);
}

il codice funziona per il caso d’esempio e per altri che ho creato io quindi non sono riuscito a trovare l’errore.

Ciao, dovresti rivedere la struct del nodo: molte delle variabili che hai messo non servono e ne mancano altre. Ti serve innanzitutto una variabile per la somma e una per il minimo, che in ciascun nodo si riferisce al range. Stessa cosa per ciascun tipo di update. Se ti può essere utile, ti lascio sotto un esempio di come potrebbe essere definita la struct nodo secondo le richieste dell’esercizio che stai facendo.

typedef long long ll;

struct node {
    ll sum,min,lazy_add,lazy_set;

    node() : sum(0),min(LLONG_MAX),lazy_add(0),lazy_set(LLONG_MIN) {};
};

Come avrai notato dal codice sopra, per gli update su range serve utilizzare una tecnica chiamata lazy propagation, che permette di apportare la modifica solo quando effettivamente ti serve conoscere il valore di un determinato nodo (range).

Se ti fosse utile, posso condividere il codice per delle particolari query o update, se non riuscisti a implementarle.

Spero di essere stato d’aiuto, se così non fosse chiedi pure.

è vero molte sono superflue ma le ho scritte per semplificarmi un po’ il resto, comunque quelle 4 che hai messo tu dovrebbero esserci tutte a parte lazy_set: val è il valore minimo, sum il totale, add è il valore che va aggiunto a tutti i nodi sottostanti (penso sia il tuo lazy_add), mentre le altre sono
-same: mi serve per verificare se tutti le foglie di quel nodo abbiano lo stesso valore
-childrens: lo uso per modificare il valore sum con un add o un set range
-index: non lo uso, mi sono dimenticato di eliminarlo
il tuo lazy_set lo ottengo attraverso il bool same e la variabile val che contiene il valore che nel tuo codice è contenuto da lazy_set
per il codice di particolari query o update il problema è che non so cosa non funzioni nel mio, per tutti gli input che ho provato funziona tuttavia dalla subtask 3 fallisce moltissimi testcase

Dovresti controllare questo valore per le variabili long long!

1 Mi Piace

ok sistemato, però mi da comunque output errato negli stessi testcase

Anche nelle seguenti funzioni devi mantenere lo stesso tipo per i valori passati:

1 Mi Piace

così fa 40/100.
nelle subtask 4-5-6 fallisce ancora gli stessi testcase (tutti a parte il primo per ogni subtask)

Verifica il codice con questo input:
10 5
17 -15 13 27 -29 -6 -15 -29 1 -9
2 3 8 -10
3 1 9 10
1 4 7
4 0 4
5 1 9 0

1 Mi Piace

grazie a questo input ho sistemato 2 cose: il lower_bound che considerava l’estremo ( chiamava [l,r] al posto di [l,r) ) e ho aggiunto
t[v].add = 0; a setrange, poi mi sono accorto che la funzione push era “completamente” sbagliata e l’ho riscritta da 0, quindi ora sono riuscito a prendere 80/100 questo vuol dire che c’è qualche problema con la funzione lower bound, ora provo a sistemarla (l’avevo copiata da internet quest’ultima)

edit: non avevo messo il push ora faccio 100/100