Seletiva IOI 2015

pedrasonline.cpp

// Ivan Carvalho
// Pedras - Seletiva IOI - OBI 2015
// Alternative Solution - O(n*sqrt(n))
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
const int BUCKET = 318;
vector<int> ida;
int freq[BUCKET][MAXN],tempfreq[MAXN],versao[MAXN],divisao[MAXN],vetor[MAXN],iteracao,N,Q;
int precalc[BUCKET][BUCKET];
void build(int id){
	for(int i = 0;i<min((id+1)*BUCKET,N);i++){
		int j = vetor[i];
		freq[id][j]++;
	}
	memset(tempfreq,0,sizeof(tempfreq));
	int best = 0;
	for(int i = id*BUCKET;i<N;i++){
		int j = vetor[i];
		tempfreq[j]++;
		best = max(best, tempfreq[j] );
		precalc[id][divisao[i]] = best;	
	}
}
int main(){
	scanf("%d %d",&N,&Q);
	for(int i = 0;i<N;i++){
		scanf("%d",&vetor[i]);
		divisao[i] = i/BUCKET;
		ida.push_back(vetor[i]);
	}
	sort(ida.begin(),ida.end());
	ida.erase(unique(ida.begin(),ida.end()),ida.end());
	for(int i = 0;i<N;i++){
		vetor[i] = lower_bound(ida.begin(),ida.end(),vetor[i]) - ida.begin();
	}
	int tot_baldes = (N-1)/BUCKET;
	for(int i = 0;i<=tot_baldes;i++){
		build(i);
	}
	for(int q = 1;q<=Q;q++){
		int l,r;
		scanf("%d %d",&l,&r);
		l--;r--;
		int resp = 0;
		iteracao++;
		int l_bucket = divisao[l];
		int r_bucket = divisao[r];
		if(l_bucket == r_bucket){
			for(int i = l;i<=r;i++){
				int j = vetor[i];
				if(versao[j] != iteracao){
					versao[j] = iteracao;
					tempfreq[j] = 0;
				}
				tempfreq[j]++;
				resp = max(resp, tempfreq[j] );
			}
		}
		else{
			resp = precalc[l_bucket+1][r_bucket-1];
			for(int i = l;i < (l_bucket+1)*BUCKET;i++){
				int j = vetor[i];
				if(versao[j] != iteracao){
					versao[j] = iteracao;
					tempfreq[j] = freq[r_bucket-1][j] - freq[l_bucket][j];
				}
				tempfreq[j]++;
				resp = max(resp, tempfreq[j] );
			}
			for(int i = r_bucket*BUCKET;i<=r;i++){
				int j = vetor[i];
				if(versao[j] != iteracao){
					versao[j] = iteracao;
					tempfreq[j] = freq[r_bucket-1][j] - freq[l_bucket][j];
				}
				tempfreq[j]++;
				resp = max(resp, tempfreq[j] );
			}
		}
		printf("%d\n",resp);
	}
	return 0;
}