Slightly improved version of Query sorting using Sqrt Decomposition

Правка en1, от AshrafSustS19, 2023-02-04 17:28:25

For offline queries, we can sort them using sqrt decomposition to minimize query traversal costs. This is very useful especially in situations where query answers can be generated using two pointers method. For this, we first divide the total query range in sqn = sqrt(n) sections. We first sort the queries in order of which section the starting point fell in, than in each section we sort the queries based on the order ending point from large to small or (small to large). I used a slightly altered implementation for this problem. Instead of using large to small or small to large endpoint at section. I sorted them in an altering structure. Therefore, if in section 1, we sort them from large to small, in section 2 we sort them from small to large, then in section 3 we again sort them from large to small. I think this implementation is quite faster on average, and in the problem I tested both the default and customized implementation. The latter proved to be almost twice as fast as the former. The implementation is as follows

struct Qry{
lli l, r, ind;
Qry(lli _l, lli _r, lli _ind){
l = _l, r = _r, ind = _ind;
}
};

bool cmp(Qry &a, Qry &b){
if (a.l / sqn < b.l / sqn) return true;
else if ((a.l / sqn == b.l / sqn)){
if ((a.l / sqn) % 2 == 0){
return a.r < b.r;
}
else {
return a.r > b.r;
}
}
return false;
}


#### История

Правки

Rev. Язык Кто Когда Δ Комментарий
en1 AshrafSustS19 2023-02-04 17:28:25 1525 Initial revision (published)