kmjp's blog

競技プログラミング参加記です

HackerRank 101 Hack 52 : C. Car Show

意外にみんな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じゃないのね。