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
vector<int> answer(q);
sort(queries.begin(), queries.end());
int curl=0, curr=-1;
for(Query query : queries) {
while (curl>query.l) {
curl--;
add(curl);
}
while (curr<query.r) {
curr++;
add(curr);
}
while (curl<query.l) {
remove(curl);
curl++;
}
while (curr>query.r) {
remove(curr);
curr--;
}
answer[query.idx]=get_answer();
}
for(int ans : answer) cout<<ans<<endl;
}
int main() {
solve();
}
Use the add and erase function like this and use an 1e6 size array to store the values instead of using map.
Thanks, never thought $$$\log n$$$ complexity factor can also get TLE
$$$O(n\sqrt{n}\log n)$$$ is an altogether evil complexity and should be avoided at all costs.
https://codeforces.me/blog/entry/100910