Codeforces #781 : Div2 E. MinimizOR

割と簡単だったっぽい回。
https://codeforces.com/contest/1665/problem/E

問題

整数列Aのコストとは、2要素A[i] or A[j]の最小値とする。

入力として、整数列Aが与えられる。
クエリとして部分列が指定されるので、その部分列のコストを求めよ。

解法

Aのコストにかかわる値は、Aのうち小さい順にO(logN)個程度である。
よってSegTreeなど使って入力に対し小さい順に31個の要素を抽出し、総当たりでコストを求めればよい。

int T;
int N;
int A[101010];
int Q;
int L[101010],R[202020];

template<class V,int NV> class SegTree_Pair {
public:
	vector<pair<V,int> > val;
	static V const def=(1<<30);
	pair<V,int> comp(pair<V,int> l,pair<V,int> r){ return min(l,r);}
	SegTree_Pair(){
		val.resize(NV*2);
		int i;
		FOR(i,NV) val[i+NV]=make_pair(def,i);
		for(i=NV-1;i>=1;i--) val[i]=comp(val[2*i],val[2*i+1]);
	};
	pair<V,int> getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return make_pair(def,NV);
		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]=make_pair(v,entry-NV);
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_Pair<int,1<<20> st;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) {
			cin>>A[i];
			st.update(i,A[i]);
		}
		cin>>Q;
		FOR(i,Q) {
			cin>>L[i]>>R[i];
			L[i]--;
			vector<pair<int,int>> V;
			FOR(j,31) {
				auto p=st.getval(L[i],R[i]);
				V.push_back(p);
				st.update(p.second,(1<<30)-1);
			}
			int ret=(1<<30);
			FOR(x,V.size()) FOR(y,x) ret=min(ret,V[x].first|V[y].first);
			reverse(ALL(V));
			FORR2(a,b,V) st.update(b,a);
			cout<<ret<<endl;
		}
	}
}

まとめ

これも考察重視の問題だったな。