Help needed in optimising Mo's algorithm

Revision en1, by harsh-apcr, 2023-12-10 21:28:29

I just learned about Mo's algorithm and went to solve some problems.

here is the problem link where I'm stuck : https://www.spoj.com/problems/DQUERY/

I used the standard implementation of Mo's algorithm from cp-algorithms here : https://cp-algorithms.com/data_structures/sqrt_decomposition.html

My solution is giving TLE (I'm pasting my code here)

map<int, int> mp;
vector<int> a;
int sz;
class Query {
public:
int l, r, idx;

bool operator<(const Query &other) {
return make_pair(this->l/sz, this->r) < make_pair(other.l/sz, other.r);
}
};
inline void remove(int idx) {
int x=a[idx];
mp[x]-=1;
if (mp[x]==0) mp.erase(x);
}
inline void add(int idx) {
mp[a[idx]]+=1;
}
inline int get_answer() {
return mp.size();
}

void solve() {
int n;cin>>n;
a.assign(n, 0);
for(int i=0;i<n;i++) cin>>a[i];
sz=(int)ceil(sqrt(n));
int q;cin>>q;
vector<Query> queries;
for(int j=0;j<q;j++) {
int l, r;cin>>l>>r;
--l, --r;
queries.push_back({l, r, j});
}
// Mo's algorithm
sort(queries.begin(), queries.end());
int curl=0, curr=-1;
for(Query query : queries) {
while (curl>query.l) {
curl--;
}
while (curr<query.r) {
curr++;
}
while (curl<query.l) {
remove(curl);
curl++;
}
while (curr>query.r) {
remove(curr);
curr--;
}
}
for(int ans : answer) cout<<ans<<endl;
}

int main() {
solve();
}


#### History

Revisions

Rev. Lang. By When Δ Comment
en1 harsh-apcr 2023-12-10 21:28:29 1569 Initial revision (published)