ARC085 F : NRE(1000)
作成日：2017.11.12
最終更新日：2017.11.12
問題概要
全ての要素が$0$の数列$\{a\}$と、$0$と$1$からなる数列$\{b\}$があり、それぞれ長さは$N$である。
$Q$個の操作「数列$\{a\}$の$l_i$番目から$r_i$番目の要素を$1$にする」が可能である。
操作のうちいくつかを行い、$a_k \neq b_k$となる$k$の数を最小化する。
この最小値を求めよ。
制約
$1 \leq N,Q \leq 2 \times 10^5$
$b_i = 0,1$
$1 \leq l_i \leq r_i \leq N$
$i \neq j$ならば$(l_i,r_i) \neq (l_j,r_j)$
考え方
数列$\{a\}$を先頭から決めていくDPを考える。
2つの組$(l_i,r_i)$,$(l_j,r_j)$が$l_i$$\leq l_j$$\leq r_i$を満たしている時、$(l_i,r_j)$の組があるとして操作ができる。
このことを考慮して組を独立に見ることができるようにするためにDPで持つべき状態は、最後に$0$が現れたのが$i$番目の要素で$j$番目の要素まで決めた時の答え($X_{i,j}$とする)である。
$X_{i,j}$は、$i=j$の時$X_{k,i-1}+b_i$の$k < i$での最小値、そうでない時$l_k > i$,$r_k = j$を満たす$k$において$X_{i,l_k - 1}$$+ \sum_{l_k \leq z \leq r_k}{1-b_z}$の最小値である。
$X_{i,j}$をそのまま求めると、累積和を用いても$O(N^2)$かかり間に合わないので工夫する。
より複雑な2つ目の遷移を扱いやすくするために$i$が小さい方から順に見ていくことにする。
$j$の値ごとにこれまで見た$i$で$X_{i,j}$が最小となるものを保持していれば1つ目の遷移は簡単に行える。
また2つ目の遷移は、$(l_i,r_i)$の組を$l_i$の小さいものから順に見ていくと区間minを取るのに近い操作である。
これを真に区間minを取る操作に変えるには$\sum$が消えれば良いが、これは$X_{i,j}$に$\sum_{z > j}{1-b_z}$を加えたものを考えることで達成できる。
以上より各$(l_i,r_i)$の組につき$O(log \: N)$、$i$の値ごとに$O(log \: N)$で遷移を反映できる。
全体の計算量は$O((N+Q)log \: N)$なので十分高速である。
ソースコード
マクロ等はこちら
Segment_Tree<T>
各要素は十分大きな値($10^9+7$)で初期化
void put(int a , T b)
$a$番目の要素が$b$より大きければ$b$にする
int get(int s , int f)
区間$[s,f)$における最小値を取得
const int MC = 200010;
int N,Q;
int b[MC];
int s[MC];
P2 p[MC];
Segment_Tree<int> st;
int main(){
cin >> N;
repp(i,1,N+1){
cin >> b[i];
s[i] = s[i-1] + !b[i];
}
cin >> Q;
repp(i,0,Q){
cin >> p[i].first >> p[i].second;
}
sort(p,p+Q);
int ans = 0; //X_{i,i}を保持
int it = 0;
repp(i,1,N+1){
while(it < Q && p[it].first == i){
int z = st.get(i,p[it].second);
st.put(p[it].second,min(z,ans+s[N]-s[i-1]));
++it;
}
ans = min(ans+b[i],st.get(i,i+1)-s[N]+s[i]);
}
cout << ans << endl;
return 0;
}解法まとめ
Segment Treeで$X_{i,j}$$+\sum_{z>j}{1-b_z}$の最小値を保持し、$i$を1ずつ大きくしていくことを考える。
$l_k = i$であるものに対して、$j=r_k$の値を区間$[i,r_k]$での最小値に更新する。(22-26行)
また、$X_{i,i}$の値も更新する。(27行)
最終的な答えは$X_{N,N}$である。(29行)