yukicoder : No.2935 Division Into 3 (Mex Edition)

この形のSegTreeの構築は初めて見たかも。
https://yukicoder.me/problems/no/2935

問題

整数列Aが与えられる。
部分列が指定されるので、以下を答えよ。

• 指定された部分列を、連続でなくても良いので、空でない3つの数列に分ける。
• その時、それぞれの数列のmexの和の最大値を求めよ。

解法

部分列について、

• 1個以上存在しない最小の非負整数a
• 2個以上存在しない最小の非負整数b
• 3個以上存在しない最小の非負整数c

を求められればよい。

これらをSegTreeで求める。
SegTreeの各ノードには、[x,y)の区間の整数がC個以上あるようなAの部分列A[L,R]の始点・終点の対(L,R)の集合を置く。
なお各ノードには、A[L]が[x,y)に含まれるもののみ置くようにする。
そうするとSegTree上で探索することで、[0,R)がC個以上ない最小のRを求めることができる。

int N,A[101010];
int Q;
ll L,R,ret;
int cnt[101010];

template<int C,int NV> class SegTree_1 {
public:
	vector<vector<pair<int,int>>> val;
	
	SegTree_1(){val.resize(NV*2);};
	int getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		int pos=lower_bound(ALL(val[k]),make_pair(x,0))-val[k].begin();
		pair<int,int> p=val[k][pos];
		if(p.second<y) return r;
		if(r-l==1) return l;
		
		int m=(l+r)/2;
		int ret=getval(x,y,l,m,2*k);
		if(ret<m) return ret;
		return getval(x,y,m,r,2*k+1);
	}
	void build(vector<int> V, int l=0,int r=NV,int k=1) {
		int m=(l+r)/2;
		
		int VL=V.size();
		int i,c=0,CR=0;
		FOR(i,VL) {
			while(CR<VL&&c<r-l) {
				cnt[A[V[CR]]]++;
				if(cnt[A[V[CR]]]==C) c++;
				CR++;
			}
			if(c==r-l) val[k].push_back({V[i],V[CR-1]});
			if(cnt[A[V[i]]]==C) c--;
			cnt[A[V[i]]]--;
		}
		val[k].push_back({NV,NV});
		
		if(r-l>1) {
			vector<int> LV,RV;
			FORR(v,V) {
				if(A[v]<m) LV.push_back(v);
				else RV.push_back(v);
			}
			build(LV,l,m,k*2);
			build(RV,m,r,k*2+1);
		}
		
	}
};
SegTree_1<1,1<<20> st1;
SegTree_1<2,1<<20> st2;
SegTree_1<3,1<<20> st3;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	vector<int> V;
	FOR(i,N) {
		cin>>A[i];
		V.push_back(i);
	}
	st1.build(V);
	st2.build(V);
	st3.build(V);

	cin>>Q;
	while(Q--) {
		cin>>L>>R;
		L=(L^ret)-1;
		R=(R^ret);
		
		int a=st1.getval(L,R);
		int b=st2.getval(L,R);
		int c=st3.getval(L,R);
		
		ret=min(a+b+c,(int)(R-L-(a==0)-(b==0)-(c==0)));
		
		cout<<ret<<endl;
	}
	
}

まとめ

Aの添え字順じゃなく、現れる値でノードを区切っていくの珍しいな。