HackerRank University CodeSprint 4 : E. Unique Art

本番TLEすると思ったのが通ってびっくりした。
https://www.hackerrank.com/contests/university-codesprint-4/challenges/unique-art

問題

N要素の数列Aが与えられる。
以下のクエリQ個に答えよ。
各クエリは区間[L,R]で構成される。A[L..R]のうち1回だけ登場する値の数を答えよ。

解法

同じ要素の手前と後ろの位置を覚えておけば、あとはMo's Algorithmで平方分割するだけ。
O(N^1.5)程度のになるので、Nの上限10^6では通らないかと思ったら通ってしまった。

想定解法はBITを使う方法だそうで。

int N;
int nex[1010101];
int pre[1010101];
int Q,L[1010101],R[1010101],ret[1010101];
vector<pair<int,int>> E[1015];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	map<int,int> p;
	cin>>N;
	for(i=1;i<=N;i++) {
		cin>>x;
		if(p.count(x)) {
			nex[p[x]]=i;
			pre[i]=p[x];
		}
		else {
			pre[i]=-1;
		}
		nex[i]=N+1;
		p[x]=i;
	}
	
	cin>>Q;
	FOR(i,Q) {
		cin>>L[i]>>R[i];
		E[L[i]/1000].push_back({R[i],i});
	}
	FOR(i,1010) if(E[i].size()) {
		int LL,RR;
		LL=RR=i*1000;
		int cnt=0;
		sort(ALL(E[i]));
		FORR(r,E[i]) {
			x=r.second;
			while(RR<=R[x]) {
				if(pre[RR]<LL) cnt++;
				else if(pre[pre[RR]]<LL) cnt--;
				RR++;
			}
			while(L[x]<LL) {
				LL--;
				if(nex[LL]>=RR) cnt++;
				else if(nex[nex[LL]]>=RR) cnt--;
			}
			while(LL<L[x]) {
				if(nex[LL]<RR) {
					if(nex[nex[LL]]>=RR) cnt++;
				}
				else cnt--;
				LL++;
			}
			ret[x]=cnt;
		}
		
		
	}
	FOR(i,Q) _P("%d\n",ret[i]);
	
}

まとめ

これ70pt？と思ったらやっぱり想定解じゃなかったか。