Harbour.Space Scholarship Contest 2023-2024 : F. Exotic Queries

若干問題文が読みにくいな…。
https://codeforces.com/contest/1864/problem/F

問題

整数列Aが与えられる。
以下のクエリに順次答えよ。

• クエリは2値L,Rで与えられる。Aのうち、[L,R]の範囲に含まれる値だけを抽出した数列Bを考える。
• Bのうち区間を選び、同じ値を引く、ということを繰り返す。ただし途中Bが負になってはならない。また、2つの選択した区間が部分的に共通部分を持つことがあってはならない。
• Bを0にするための最小選択回数を求めよ。

解法

Rを走査することを考える。
今B[x]=B[y]=Rだとする。xとyを常に同じ区間に入れられるなら、B[x]を0にするのと同時にB[y]=0となり、B[y]を0にするための追加の区間選択が要らない。
この条件は、L＜min(B[x...y])である。
よって、Rを走査しながら「B[y]が追加されることで区間選択回数が1回増える。しかしLがこれ以上ならその1回をなかったことにできる」という処理をSegTreeやBITを用いて行えばよい。

int N,Q;
int A[1010101];
vector<int> add[1010101],Qs[1010101];

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,20> bt;

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=-1;
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v; //上書きかチェック
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<int,1<<20> st;
int L[1010101],R[1010101],ret[1010101];
int NV[1010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&N,&Q);
	FOR(i,N) {
		scanf("%d",&x);
		add[x].push_back(i);
	}
	FOR(i,Q) {
		scanf("%d%d",&L[i],&R[i]);
		Qs[R[i]].push_back(i);
	}
	int tnum=0;
	for(i=1;i<=N;i++) {
		for(j=1;j<add[i].size();j++) {
			x=add[i][j-1];
			y=add[i][j];
			k=st.getval(x,y);
			bt.add(k+1,-1);
		}
		NV[i]=NV[i-1];
		if(add[i].size()) NV[i]++;
		tnum+=add[i].size();
		FORR(v,add[i]) {
			st.update(v,i);
		}
		FORR(q,Qs[i]) {
			ret[q]=tnum-NV[L[q]-1]+bt(L[q]);
		}
	}
	FOR(i,Q) _P("%d\n",ret[i]);
		
	
}

まとめ

問題文を見て、Aの部分列の抜き出し方を最初混乱した。