Help needed in optimising Mo's algorithm

Правка en1, от 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
	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();
}

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский harsh-apcr 2023-12-10 21:28:29 1569 Initial revision (published)