Codeforces ECR #080 : E. Messenger Simulator

EまでとFの難易度差が大きい。
https://codeforces.com/contest/1288/problem/E

問題

初期状態で1～Nの順に値が並んだ数列がある。
ここでM個のクエリが与えられる。

クエリXは1つの1～Nの値のいずれかを取る。
この時、数列中のXを抜き出し先頭に動かすということを行う。

一連のクエリをこなす上で、各値が置かれる数列中の最小・最大インデックスを答えよ。

解法

最小値となるのは、最初かクエリで自身が呼ばれた場合である。
反対に最大値を更新するタイミングとしては、クエリで呼ばれる直前または最終的な位置だけ覚えておけばよい。

よってこれらのタイミングで、各値が数列中何番目にいるか求めよう。
初期状態で数列の1～N番目が埋まっているとしたら、各クエリで呼ばれた値は0,-1,-2…と手前の位置に移動したと考えよう。
そうすると途中移動によって抜けができるが、BITを用いて各位置の抜けの数を覚えておけば、数列内での位置を高速に求めることができる。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<int,22> bt;

int N,M;
int A[303030];
int ret[303030];
int pos[303030];
int mi[303030],ma[303030];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	for(i=1;i<=N;i++) {
		pos[i]=(1<<20)+i;
		mi[i]=ma[i]=i;
		bt.add(pos[i],1);
	}
	FOR(i,M) {
		cin>>x;
		mi[x]=1;
		ma[x]=max(ma[x],bt(pos[x]));
		bt.add(pos[x],-1);
		pos[x]=(1<<20)-i;
		bt.add(pos[x],1);
	}
	for(i=1;i<=N;i++) {
		ma[i]=max(ma[i],bt(pos[i]));
		cout<<mi[i]<<" "<<ma[i]<<endl;
	}
	
}

まとめ

ECR、それも6問回のEにしては簡単。