Codeforces #1052 : Div2. E. Yet Another MEX Problem

ライブラリ部分を除くとかなり単純。
https://codeforces.com/contest/2146/problem/E

問題

数列Bの重さとは、Bの要素のうちmex(B)より大きなものの個数をいう。

数列Aが与えられる。
w(L,R)をA[L...R]の重さとしたとき、Rを徐々に動かしたときにw(L,R)の最大値を求めよ。

解法

mexが扱いにくいので言い換える。
B中にない整数値xがあるとき、B[i]＞xとなるiの数の最大値が解となる。

区間加算・区間最大値を取るSegTreeを使い、Rをずらしながら以下のようにしよう。

• xが0～A[R]-1の場合、A[R]が数列の末尾に来ることで回が１つ増える
• 以後、x=A[R]となるときの重さは0となる。

static ll const def=-1<<20;
template<class V,int NV> class SegTree_3 {
public:
	vector<V> val, ma;
	SegTree_3(){
		int i;
		val.resize(NV*2,0); ma.resize(NV*2,0);
		FOR(i,NV) val[i+NV]=ma[i+NV]=def;
		for(i=NV-1;i>=1;i--) ma[i]=max(ma[2*i],ma[2*i+1]);
	};
	
	V getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l || y<=x) return def;
		if(x<=l && r<=y) return ma[k];
		return val[k]+max(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r||y<=x) return;
		if(x<=l && r<=y) {
			val[k]+=v;
			ma[k]+=v;
		}
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			ma[k]=val[k]+max(ma[k*2],ma[k*2+1]);
		}
	}
};
SegTree_3<int,1<<20> st;

int T,N;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N+1) st.update(i,i+1,-st.getval(i,i+1));
		FOR(i,N) {
			cin>>x;
			st.update(0,x,1);
			st.update(x,x+1,-st.getval(x,x+1));
			cout<<st.getval(0,N+1)<<" ";
		}
		cout<<endl;
	}
}

まとめ

解法はシンプルなんだけどそこにすんなりたどり着けず…。