Ja to radim ovako..Ponekad se moze prilagoditi da bude optimalnije od Kum. Tab.
kao recimo u zadatku "reli" sa saveznog ove godine..
Sa kum.tab. treba obaviti n*2*log(n) a na "moj" nacin n*log(n) + n
//INACE!
Code:
void set(int x){
l=1,r=n;
do{
m=(l+r)>>1; // m=(l+r)/2;
if(x<=m){
A[m]++;
r=m-1;
}else
l=m+1;
}while(l<=r && m!=x);
}
int get(int x){
l=1,r=n,tr=0;
do{
m=(l+r)>>1; // m=(l+r)/2;
if(x>=m){
tr+=A[m];
l=m+1;
}else
r=m-1;
}while(l<=r && m!=x);
return tr;
}
//U Reli-ju
Code:
int getset(int x){
l=1,r=n,tr=0;
do{
m=(l+r)>>1;
if(x<=m){
A[m]++;
r=m-1;
}else{
tr+=A[m];
l=m+1;
}
}while(l<=r && m!=x);
return tr;
}
Ljubav je kad ja prdnem a njoj ne smrdi.
Logaritamska struktura
