Sto provando a implementare il problema segtree. In pratica implemento un segment tree con lazy propagation, purtroppo però non riesco a capire dove sbaglio, ho provato con alcuni input inventati e mi sembra funzionare. Comunque ottengo soltanto 40/100 e i primi due testcase in tutti i subtasks risultano corretti.
Se qualcuno riesce a dare un occhiata ne sarei felice, grazie in anticipo.
P.s. Se avete degli input scriveteli che li testo.
#include <bits/stdc++.h>
#include <climits>
using namespace std;
static long long MAX = LLONG_MAX;
struct Node{
long long mi;
long long val;
long long lazy_set;
long long lazy_add;
Node() : mi(MAX), val(0), lazy_add(0), lazy_set(LLONG_MIN) {};
void join(Node &l, Node &r) { //aggiorno il nodo dopo aver cambiato i figli (in caso di partial overlap)
mi = min(l.mi, r.mi);
val = l.val + r.val;
}
};
int n, real_size; // real_size è anche l'indice del primo nodo dell'ultimo livello
vector<Node> nodes;
void is_lazy(int u, int l, int r) {
if(nodes[u].lazy_add == 0 and nodes[u].lazy_set == LLONG_MIN) return; //già aggiornato
if(nodes[u].lazy_add != 0) { //devo aggiungere, non c'è quindi il set
nodes[u].mi += nodes[u].lazy_add; // aumento direttamente il nodo
nodes[u].val += nodes[u].lazy_add*(r-l); //aumento il valore
if(2*u+1 < nodes.size()) { //non sono in una foglia
if(nodes[2*u].lazy_set != LLONG_MIN) { //set presente sul figlio, aggiungo direttamente al set
nodes[2*u].lazy_set += nodes[u].lazy_add;
nodes[2*u].lazy_add = 0;
}
else {
nodes[2*u].lazy_add += nodes[u].lazy_add; //set assente, aggiungo all'addizione
}
if(nodes[2*u+1].lazy_set != LLONG_MIN) { //set presente sul figlio, aggiungo direttamente al set
nodes[2*u+1].lazy_set += nodes[u].lazy_add;
nodes[2*u+1].lazy_add = 0;
}
else {
nodes[2*u+1].lazy_add += nodes[u].lazy_add; //set assente, aggiungo all'addizione
}
}
nodes[u].lazy_add = 0;
return;
}
nodes[u].mi = nodes[u].lazy_set; //setto
nodes[u].val = nodes[u].lazy_set*(r-l); // la somma dei numeri sarà il numero di nodi incluso nel range * n
if(2*u+1 < nodes.size()) {
nodes[2*u].lazy_add = 0; //rimuovo addizioni precedenti
nodes[2*u+1].lazy_add = 0;
nodes[2*u].lazy_set = nodes[u].lazy_set; //prpago il set
nodes[2*u+1].lazy_set = nodes[u].lazy_set;
}
nodes[u].lazy_set = LLONG_MIN; //azzero il set sul nodo corrente
return;
}
void build(int u, int l, int r, vector<long long> &a) {
if(r-l <= 1) { // sono in una foglia
if(l<a.size()) { // il numero esiste, lo imposto
nodes[u].mi = a[l];
nodes[u].val = a[l];
}
}
else { // non sono in una foglia calcolo ricorsivamente
build(u*2, l, (l+r)/2, a);
build(u*2+1, (l+r)/2, r, a);
nodes[u].join(nodes[2*u], nodes[2*u+1]); //aggiorno il nodo in base ai figli
}
}
void init(vector<long long> a) {
// n è la lunghezza della sequenza di numeri, realsize la potenza di due maggiore più vicina
n = a.size();
real_size = 1;
while(real_size < n) {
real_size *= 2; //trovo realsize
}
nodes.assign(2*real_size, Node()); //inizializzo l'albero
build(1, 0, real_size, a); //costruisco l'albero
}
long long get_sum(int u, int l, int r, int x, int y) {
is_lazy(u, l, r); //aggiorno il nodo
if(l >= y or r <= x) return 0; //no overlap
if(l>=x and r<=y) return nodes[u].val; //total overlap
return (get_sum(2*u, l, (r+l)/2, x, y) + get_sum(2*u+1, (l+r)/2, r, x, y)); // parzialmente incluso, somma dei due figli
}
long long get_sum(int l, int r) {
return get_sum(1, 0, real_size, l, r);
}
void add(int u, int l, int r, int x, int y, long long n) {
is_lazy(u, l, r); //aggiorno il nodo
if(l >= y or r <= x) return; // no overlap
if(l >= x and r <= y) { // full overlap, update node & lazy children
nodes[u].mi += n; // aumento direttamente il nodo
nodes[u].val += n*(r-l); // il singolo nodo aumenta di n*range
if(2*u+1 < nodes.size()) { //ci sono dei figli, propago
if(nodes[2*u].lazy_set != LLONG_MIN) { // Se aggiungo dopo un set, posso aggiungere al set
nodes[2*u].lazy_set +=n;
nodes[2*u].lazy_add = 0;
}
else {
nodes[2*u].lazy_add += n; //altrimenti aggiungo alla somma precedente
}
if(nodes[2*u+1].lazy_set != LLONG_MIN) { // Se aggiungo dopo un set, posso aggiungere al set
nodes[2*u+1].lazy_set += n;
nodes[2*u+1].lazy_add = 0;
}
else {
nodes[2*u+1].lazy_add += n; //altrimenti aggiungo alla somma precedente
}
}
return;
}
// partial overlap
add(2*u, l, (l+r)/2, x, y, n);
add(2*u+1, (l+r)/2, r, x, y, n);
nodes[u].join(nodes[2*u], nodes[2*u+1]);
return;
}
void add(int l, int r, long long x) {
add(1, 0, real_size, l, r, x);
}
void set_range(int u, int l, int r, int x, int y, int n) {
is_lazy(u, l, r); //aggiorno nodo
if(l >= y or r <= x) return; // no overlap
if(l >= x and r <= y) { // full overlap, update nodo e figli
nodes[u].mi = n; // cambio direttamente il nodo
nodes[u].val = n*(r-l); //la somma dei numeri sarà il numero di nodi incluso nel range * n
if(2*u+1 < nodes.size()) { //ci sono figli, attuo la lazy progapation
nodes[2*u].lazy_add = 0; //posso rimuovere le altre lazy propagation
nodes[2*u+1].lazy_add = 0;
nodes[2*u].lazy_set = n;
nodes[2*u+1].lazy_set = n;
}
return;
}
set_range(2*u, l, (l+r)/2, x, y, n); // partial overlap
set_range(2*u+1, (l+r)/2, r, x, y, n);
nodes[u].join(nodes[2*u], nodes[2*u+1]);
return;
}
void set_range(int l, int r, long long x) {
set_range(1, 0, real_size, l, r, x);
}
long long get_min(int u, int l, int r, int x, int y) {
is_lazy(u, l, r);// aggiorno il nodo
if(l >= y or r <= x) return MAX; //no overlap
if(l >= x and r <= y) return nodes[u].mi; // total overlap, il nodo è la soluzione
//partial overlap, procedo nei figli
return min(
get_min(2*u, l, (l+r)/2, x, y),
get_min(2*u+1, (l+r)/2, r, x, y)
);
}
long long get_min(int l, int r) {
return get_min(1, 0, real_size, l, r);
}
int lower_bound(int u, int l, int r, int x, int y, long long bound) {
is_lazy(u, l, r); //aggiorno il nodo
if(l >= y or r <= x) return -1; //no overlap
if(nodes[u].mi <= bound) { //partial overlap, il valore attuale soddisfa le condizioni
if(r-l<=1) return l; // sono una foglia, l'indice sarà la soluzione
//ci sono dei figli, li controllo partendo da sinistra (leftmost)
int sx = lower_bound(2*u, l, (l+r)/2, x, y, bound);
if(sx != -1) return sx; //ho trovato la soluzione, altrimenti controllo a destra
return lower_bound(2*u+1, (l+r)/2, r, x, y, bound);
}
return -1; //il valore del nodo non soddisfa le condizioni, quindi non c'è la soluzione
}
int lower_bound(int l, int r, long long x) {
// returns the index to the left most element <= x
return lower_bound(1, 0, real_size, l, r, x);
}