Aiuto Paletta Sort

Aiuto
#1

Sto cercando di risolvere paletta usando un segment tree.
Al momento faccio 22.6 su 100 (riesco a distinguere quando esiste una soluzione ma non sempre risulta corretta e nell’ultimo subtask 4 su 5 vanno in tle).
La mia idea era di dividere l’array in 2 sub-array di numeri pari e dispari (affinche’ sia risolvibile il problema, ogni elemento deve essere pari/dispari come il suo indice(0-based)).
Successivamente contare il numero di swap che bisogna fare per ordinarli.
Avevo in mente di farlo con un segment tree e quindi conto per ogni numero quanti numeri prima di lui sono piu’ grandi.
Ma non so perche’ non funziona, some help?

EDIT:
trovato l’errore ed ora mi fa 94/100 ma mi hanno detto che con segment tree non si riesce a risolvere questo problema.

Codice:

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimization ("unroll-loops")
using namespace std;

#define PB push_back
typedef vector<int> vi;

const int mxN = 1500000;  
int n;
vi t(mxN*4,0);

void upd( int l1, long long x, int i=1, int l2=0, int r2=n-1)
{
    if(l2==r2){
        t[i] = x;
    	return;
    }
    
    int m2 = (l2+r2)/2;
        
    if(l1 >= l2 && l1 <= m2)
        upd(l1, x, 2*i, l2, m2);
    else
        upd(l1, x, 2*i+1, m2+1, r2);
            
    t[i] = t[2*i] + t[2*i+1];
    
}

int qry(int l1, int r1, int i=1, int l2=0, int r2=n-1){
	
	if (l1 > r2 || r1 < l2)
        return 0;
	
    if(l1 <= l2 && r2 <= r1)
        return t[i];
    
    int m2 = (l2+r2)/2; 
    
	int q1 = qry(l1, r1, 2*i, l2, m2);
	int q2 = qry(l1, r1, 2*i+1, m2+1, r2);
    
	return q1 + q2;
}

long long paletta_sort(int N, int V[]){

	long long ris=0;
	vi p,d;
	
	n=N;
	
	for (int i = 0; i < n; ++i){
		
		if(i%2!=V[i]%2)
			return -1;	
		
		if(V[i]%2==1)
			d.PB(V[i]);
		else
			p.PB(V[i]);
	}
	

	
	for(int i=0; i<d.size(); ++i){
    	ris += qry(d[i]+1, n-1);
    	upd(d[i], 1);
	}
	

	fill(t.begin(), t.end(), 0);
	
	for(int i=0; i<p.size(); ++i){
    	ris += qry(p[i]+1, n-1);
    	upd(p[i], 1);
	}

	return ris;
}
#2

C’è una struttura dati molto simile al Segment che fa tutte le operazioni che ti servono per il problema, sempre con O(logN) a query ma con un fattore costante abbastanza migliore. (Fenwick Tree).
Poi implementi il segment ricorsivamente, facendolo iterativamente credo diventi abbastanza veloce per fare 100.

#3

sto cercando di risoverlo con Fenwick tree usando lo stesso ragionamento (dato che non ho esperienza con i Fenwick tree ) sto avendo problemi

#4

sono riuscito a ridurre il problema di spazio (riducendo anche la comlessita’ del Fenwick tree) facendo si che al posto di avere i 2 array contenenti i numeri dispari e pari, ciascuno conterra’ il numero della posizione sortata (1-based) che rappresenterebbe quel numero se l’array fosse soltanto fatto di numeri pari/dispari.
Esempio:
2 3 0 5 4 1 diventa un array solo pari e uno sono dispari:
il subarray pari poi diventa:
2 0 4 -> 2 1 3
il subarray dispari poi diventa:
3 5 1 -> 2 3 1
e quindi conto quanti numeri piu grandi prima del numero che sto puntando ci sono
ma non riesco ancora a risolverlo usando un segment tree.

#5

Puoi usare un ragionamento analogo a quello che usi con il segment tree. Quello che stai facendo al memento è una query (somma di elementi in un suffisso) ed un update (modifica di un elemento). Con il fenwick non puoi fare lo stesso identico ragionamento ma quasi, l’update puoi farlo senza problemi, mentre le query si posso fare solo su prefissi. Quindi devi, invece di effettuare una query sul suffisso, effettuarla sul prefisso e poi ottenere il valore che cercavi: diciamo che se sei in posizione i con x elementi minori di v[i] nel prefisso [0,i-1] allora ci saranno i-x elementi più grandi di v[i] nel prefisso [0,i-1].

#6

quindi devo fare semplicemente
ris += i - query(V[i]-1) ? Si.