CF 765 F - Souvenirs
問題
問題概要
長さの数列が与えられる。
とが与えられ、 の最小値 を答えよというクエリが個与えられるので、それらに答えよ。
アイデア
まず、絶対値を考えるのはややこしい。数列をreverseしてindexもreverseして同じクエリに対して答えれば題意の条件を満たすことが出来るので、という条件の部分についての最小値を考えることにする。
クエリの先読みを考えよう。の昇順でクエリを処理していくことにする。今、を固定した状況に対して、ans[i] = 左端がiの時のクエリの答え
としてを右に動かしながら配列を更新し、クエリに答えていく。
さて、今が右に動いてに注目しているという状況で、はどのように更新されるか考えてみる。いま、という条件の部分についてのみ考えるという条件があるので、からスタートしてを少しずつ減少させていき、初めてになるような位置をまずは見つける(とする)。
まず、このようなを見つける事ができれば、について、必ずとを含むことから、ans[k]は以下であることは分かるので、最小値を更新出来る。ここで、ansという配列を遅延segment tree上で管理すれば、区間のupdateなどはで処理出来る。今回は区間のupdateの左端が0で固定なので、普通のsegment treeで良さそう。
その次にこのupdate処理を入れるべき箇所としては、更にを左に動かしていき、となるような箇所である。の方がよりもに近い値を取ることから、について、ans[k]はで最小値を更新出来る。
よって、を右に動かしながら、そのたびにをからに動かしてsegtreeを更新していけばで出来るように見えるけど、これでは不十分なので、更に高速化することを考える。
さて、から次のを見つける部分について考えてみる。このとき、という値で最小値が更新される条件を考えてみると、とを含む区間というのは必ずも含んでいることは、先の操作を考えると明らかであるので、最小値が更新される条件として、となる必要がある。これを式変形するととなる。このの制約によって、1つの固定されたに対して先のようなupdateの処理は高々回となる。これは、十分に速く動作する。この問題を解くためにはこの考察がなければ解けない。言われてみると当たり前のことだが、このように条件を見て式変形することで実際に計算量を落とすことが出来るとても面白い問題だった。
実装(C++)
#include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define all(x) (x).begin(),(x).end() #define pb push_back #define fi first #define se second struct MinSegTree{ int n; vector<ll> dat; //初期化 MinSegTree(int _n){ n=1; while(n<_n) n*=2; dat=vector<ll>(2*n-1,LLONG_MAX); } //k番目(0-indexed)の値をaに変更 void update(int k, ll a){ k+=n-1; dat[k]=min(dat[k],a); //更新 while(k>0){ k=(k-1)/2; dat[k]=min(dat[2*k+1],dat[2*k+2]); } } //内部的に投げられるクエリ ll _query(int a, int b, int k, int l, int r){ if(r<=a || b<=l) return LLONG_MAX; if(a<=l && r<=b) return dat[k]; ll vl=_query(a,b,2*k+1,l,(l+r)/2); ll vr=_query(a,b,2*k+2,(l+r)/2,r); return min(vl,vr); } //[a,b)の最小値 ll query(int a, int b){ return _query(a,b,0,0,n); } }; int main() { int n; scanf(" %d", &n); vector<int> a(n); rep(i,n) scanf(" %d", &a[i]); int m; scanf(" %d", &m); vector<int> l(m),r(m); rep(i,m) { scanf(" %d %d", &l[i], &r[i]); --l[i]; --r[i]; } vector<int> v(a); sort(all(v)); v.erase(unique(all(v)),v.end()); int V = v.size(); vector<ll> ans(m,INT_MAX); rep(_,2) { vector<vector<pair<int,int>>> Q(n); rep(i,m) Q[r[i]].pb({l[i],i}); // 答えを保存 MinSegTree st(n); // 各値が登場した一番右のindexを保存 MinSegTree idxs(V+1); // 区間の右端を右に1つずつずらしながらクエリに答える rep(i,n) { // 最小値を更新 ll y = 1234567890; int idx = lower_bound(all(v),a[i])-v.begin(); while(y>a[i]) { int L = idx, R = lower_bound(all(v),y)-v.begin(); ll j = -idxs.query(L,R); if(j<0) break; st.update(j,a[j]-a[i]); y = (a[i]+y)/2; } idxs.update(idx,-i); // クエリに答える for(auto &p:Q[i]) { int id = p.se; ans[id] = min(ans[id], st.query(p.fi,i+1)); } } // 配列とクエリをreverseして同じ処理をする reverse(all(a)); rep(i,m) { l[i] = n-1-l[i]; r[i] = n-1-r[i]; swap(l[i],r[i]); } } rep(i,m) printf("%lld\n", ans[i]); return 0; }