harsh-apcr's blog

By harsh-apcr, history, 12 months ago, In English

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();
}
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
12 months ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Use the add and erase function like this and use an 1e6 size array to store the values instead of using map.

Add and Erase Function
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Thanks, never thought $$$\log n$$$ complexity factor can also get TLE

»
12 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

$$$O(n\sqrt{n}\log n)$$$ is an altogether evil complexity and should be avoided at all costs.

https://codeforces.me/blog/entry/100910