Codeforcesっぽい問題。
https://codeforces.com/contest/1217/problem/E
問題
ある整数の集合がbalancedであるとは、その和の各桁において、それと同じ値を持つ要素が1個ある状態をいう。
整数列Aに対し、以下のクエリに順次答えよ。
- 数列の内容を1つ変更する
- A[L...R]のsubsetのうち、unbalancedなものの和の最小値を求めよ。
解法
unbalancedであるsetを作るには、同じ桁が1以上のものを2つ準備すればよい。
そこで、各桁毎に、区間においてその桁が1以上であるものの上位2位までを管理するSegTreeを作ろう。
各桁においてこのSegTreeを探索することで、上位2位の和の最小のものを求められる。
int N,M; int A[202020]; pair<int,int> def={1000000001,1000000001}; template<class V,int NV> class SegTree_Pair { public: vector<pair<int,int> > val; pair<int,int> comp(pair<int,int> l,pair<int,int> r){ if(l.second<=r.first) return l; if(r.second<=l.first) return r; if(l.first<=r.first) return {l.first,r.first}; return {r.first,l.first}; } SegTree_Pair(){ val.resize(NV*2,def); }; pair<V,int> getval(int x,int y,int l=0,int r=NV,int k=1) { 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,1000000001}; while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]); } }; SegTree_Pair<int,1<<18> st[12]; void update(int cur) { int i; int v=A[cur]; FOR(i,10) { if(v%10) { st[i].update(cur,A[cur]); } else { st[i].update(cur,1000000000); } v/=10; } } void solve() { int i,j,k,l,r,x,y; string s; scanf("%d%d",&N,&M); FOR(i,N) { scanf("%d",&A[i]); update(i); } while(M--) { int L,R; scanf("%d%d%d",&i,&L,&R); if(i==1) { L--; A[L]=R; update(L); } else { L--; int ret=2000000001; FOR(i,10) { auto p=st[i].getval(L,R); if(p.second<1000000000) ret=min(ret,p.first+p.second); } if(ret>=2000000000) ret=-1; _P("%d\n",ret); } } }
まとめ
若干面倒だけどアプローチ自体は難しくない。