AtCoder ABC #174 : F - Range Set Query

こりゃ想定解法じゃないだろうなという気がする。
https://atcoder.jp/contests/abc174/tasks/abc174_f

問題

整数列とクエリが与えられる。
各クエリは、整数列中の区間を示す。
区間中に現れるユニークな値は何通りか。

解法

以下では、Mo's Algorithmで解いている。
区間内における各値の登場を数え上げ、1回以上登場した値の種類を適宜更新している。
ただこれはO(N√N+Q)程度必要で効率が悪い。
実際ACはできるものの2秒近くかかっている。

別解としてはBITによる区間和を使ったものかな。
ある値が初めて登場する位置に1を足しこむことで、右端が決まったときにそこまでに現れる値の種類をO(N)で数え上げられるようにする。
左端を走査しつつ各クエリを捌いていき、左端からはみ出た値については次にその値が出る位置に1を足すようにする。

以下はMo's Algorithmの重いコードなので注意。

int N,Q;
int C[505050];
int L[505050],R[505050];
const int DI=800;
vector<pair<int,int>> ev[DI];
int ret[505050];
int num[505050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) cin>>C[i];
	FOR(i,Q) {
		cin>>L[i]>>R[i];
		L[i]--;
		ev[L[i]/DI].push_back({R[i],i});
	}
	
	FOR(i,DI) {
		ZERO(num);
		int c=0;
		sort(ALL(ev[i]));
		int CL=0,CR=0;
		FORR(e,ev[i]) {
			x=e.second;
			while(CR<R[x]) {
				if(num[C[CR]]==0) c++;
				num[C[CR]]++;
				CR++;
			}
			while(CL<L[x]) {
				num[C[CL]]--;
				if(num[C[CL]]==0) c--;
				CL++;
			}
			while(L[x]<CL) {
				CL--;
				if(num[C[CL]]==0) c++;
				num[C[CL]]++;
			}
			ret[x]=c;
		}
		
	}
	FOR(i,Q) cout<<ret[i]<<endl;
}

まとめ

いや、本番中N,Qの上限が5*10^5なのにO(N√N)なんて出すかな？と思いつつそのままSubmitしてしまった。