裏紙

ほぼ競プロ、たまに日記

CF 765 F - Souvenirs

問題

Problem - F - Codeforces

問題概要

長さnの数列aが与えられる。

l_ir_iが与えられ、 |a_s - a_t | (l_i \le s \lt t \le r_i) の最小値 を答えよというクエリがm個与えられるので、それらに答えよ。

  •  2 \le n \le 100000
  •  0 \le a_i \le 10^9
  •  1 \le m \le 300000
  •  1 \le l_i \lt r_i \le n

イデア

まず、絶対値を考えるのはややこしい。数列をreverseしてindexもreverseして同じクエリに対して答えれば題意の条件を満たすことが出来るので、a_s \ge a_t (s \lt t)という条件の部分についての最小値を考えることにする。

クエリの先読みを考えよう。rの昇順でクエリを処理していくことにする。今、rを固定した状況に対して、ans[i] = 左端がiの時のクエリの答えとしてrを右に動かしながら配列を更新し、クエリに答えていく。

さて、今rが右に動いてx( = a_r)に注目しているという状況で、ansはどのように更新されるか考えてみる。いま、a_s \ge a_t (s \lt t)という条件の部分についてのみ考えるという条件があるので、j = rからスタートしてjを少しずつ減少させていき、初めてa_j \ge xになるような位置jをまずは見つける(a_j = yとする)。

まず、このようなjを見つける事ができれば、k \in [ 0,j ] について、必ずyxを含むことから、ans[k]はy-x以下であることは分かるので、最小値を更新出来る。ここで、ansという配列を遅延segment tree上で管理すれば、区間のupdateなどはO( \log n)で処理出来る。今回は区間のupdateの左端が0で固定なので、普通のsegment treeで良さそう。

その次にこのupdate処理を入れるべき箇所としては、更にjを左に動かしていき、 x \le a_{j'} = y' \lt yとなるような箇所j'である。y'の方がyよりもxに近い値を取ることから、k \in [ 0,j' ] について、ans[k]はy' -xで最小値を更新出来る。

よって、rを右に動かしながら、そのたびにjrから0に動かしてsegtreeを更新していけばO(n^2 \log n)で出来るように見えるけど、これでは不十分なので、更に高速化することを考える。

さて、yから次のy'を見つける部分について考えてみる。このとき、y' -xという値で最小値が更新される条件を考えてみると、y'xを含む区間というのは必ずyも含んでいることは、先の操作を考えると明らかであるので、最小値が更新される条件として、y' - x \lt y - y'となる必要がある。これを式変形するとy' \lt \frac{x+y}{2}となる。このy'の制約によって、1つの固定されたrに対して先のようなupdateの処理は高々 \log 10^9回となる。これは、十分に速く動作する。この問題を解くためにはこの考察がなければ解けない。言われてみると当たり前のことだが、このように条件を見て式変形することで実際に計算量を落とすことが出来るとても面白い問題だった。

実装(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;
}