意外にみんなEの部分点を取りに来なかったので、余裕をもってTシャツ圏内。
https://www.hackerrank.com/contests/101hack52/challenges/car-show
問題
整数列A[i]が与えられるので、以下のクエリに答えよ。
区間A[L..R]が指定される。このうちの部分区間で同じ数字を2つ以上含まないものは何通りあるか。
解法
Mo's Algorithmで解く。
まず、各区間の左端A[i]に対し、同じ数字を複数含まない最大の右端B[i]を求めておこう。
あとはMo's Algorithmの要領で、左右の端を動かしつつ、内部に含まれる条件を満たす区間の数を求める。
区間内の要素をそれぞれ左端iとする場合、R<B[i]であるなら区間Rを右に動かしたとき、条件を満たす区間は1つ増加する。
この条件をもとに、クエリ区間内に収まらない右端の個数と、条件を満たす部分区間の数をそれぞれ更新していこう。
int N,Q; int A[101010]; int nex[101010]; int L[101010],R[101010]; int nexid[1010101]; ll ret[101010]; const int DI=350; vector<pair<int,int>> ev[350]; int del[101010]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>Q; FOR(i,N) cin>>A[i]; FOR(i,1010100) nexid[i]=N; nex[N]=N-1; for(i=N-1;i>=0;i--) { nex[i]=min(nexid[A[i]]-1,nex[i+1]); nexid[A[i]]=i; } FOR(i,Q) { cin>>L[i]>>R[i]; L[i]--,R[i]--; ev[L[i]/DI].push_back({R[i],i}); } FOR(i,340) if(ev[i].size()) { ZERO(del); sort(ALL(ev[i])); ll tot=0; int num=0; int LL=0,RR=0; FORR(e,ev[i]) { x=e.second; while(RR<=R[x]) { num++; del[nex[RR]]++; tot+=num; num-=del[RR]; RR++; } while(LL<L[x]) { if(nex[LL]<RR) { tot-=(nex[LL]-LL)+1; } else { tot-=RR-LL; del[nex[LL]]--; num--; } LL++; } while(LL>L[x]) { LL--; if(nex[LL]<RR) { tot+=(nex[LL]-LL)+1; } else { tot+=RR-LL; del[nex[LL]]++; num++; } } ret[x]=tot; } } FOR(i,Q) cout<<ret[i]<<endl; }
まとめ
想定解Moじゃないのね。