GCJ 2019 R1B Fair Fight - ferinの競プロ帳

解法

部分点は $O(N^{3})$ で取りうる区間を全探索すればよい。
満点では $O(N^{2})$ 個の区間を全部見ているのでは間に合わない。 $c \lbrack i \rbrack$ が最大になり、 $\max (d \lbrack i \rbrack)$ についても条件を満たすような区間がそれぞれ何個あるか？を各 $c \lbrack i \rbrack$ に対して求めることで答えを求める。この各区間に課される条件を3つに分割することで数えやすくする。
(1) $\max (c \lbrack l \rbrack, \ldots, c \lbrack r \rbrack) = c \lbrack i \rbrack$ となるような最大の区間の $l,r$
(2) $\max (c \lbrack l \rbrack, \ldots, c \lbrack r \rbrack) \leq c \lbrack i \rbrack + k$ となるような最大の区間 $l,r$
(3) $\max (c \lbrack l \rbrack, \ldots, c \lbrack r \rbrack) \lt c \lbrack i \rbrack - k$ となるような最大の区間 $l,r$

(1)~(3)のそれぞれについて最大の区間に内包される全ての区間についても条件を満たす。よって条件を満たす区間は $(i-l+1) \times (r-i+1)$ 個となる。また、(1)について同じ区間を複数回数えないようにするため区間の最大値が複数ある場合は最も左の $c \lbrack i \rbrack$ を選ぶとする。

答えは ((1)と(2)を両方を満たすような区間の数)-((1)と(3)の両方を満たすような区間の数) となる。よってこれらの区間の数を高速に求めることができればよい。(1)を満たすような区間が $l_1, r_1$ で(2)を満たすような区間が $l_2, r_2$ であるとき、これら両方を満たすような区間は $\max (l_1, l_2)$ から $\min (r_1, r_2)$ となる。したがって(1)~(3)を求めることができれば答えがわかる。

(1)の $l$ を求めることを考える。 $r=i$ として $\max (c \lbrack j \rbrack, \ldots, c \lbrack r \rbrack) = c \lbrack i \rbrack$ を満たすような最大の $j$ が求まればよい。これは区間の最大値が単調増加することから二分探索を使って求めることができる。sparse table等の $O(1)$ でRMQができるデータ構造を用いることで $O(N \log N)$ で各 $i$ について $l$ を求めることができる。その他の $l,r$ についても同様に二分探索を行うことで求めることができ $O(N \log N)$ で解くことができた。

(1)で重複して数えないようにするため $c \lbrack i \rbrack$ と $i$ のpairの区間minを求めるとした。(2)(3)の区間が空の場合に注意。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()

template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
    out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;

template <typename S>
struct sparseTable {
    using T = typename S::T;
    int n;
    vector<int> log2;
    vector<vector<T>> t;

    sparseTable(int nn) {
        n = nn;
        log2.assign(n+1, 0);
        for(int i=2; i<=n; ++i) log2[i] = log2[i >> 1] + 1;
        t = vector<vector<T>>(log2[n]+1, vector<T>(n));
    }
    void init(vector<T> v) {
        for(int i=0; i<n; ++i) t[0][i] = v[i];
        for(int j=1; j<=log2[n]; ++j) {
            int w = 1LL<<(j-1);
            for (int i = 0; i+(w<<1) <= n; ++i) {
                t[j][i] = S::op(t[j-1][i], t[j-1][i+w]);
            }
        }
    }
    // [l, r]
    T query(int l, int r) {
        int j = log2[r - l];
        return S::op(t[j][l], t[j][r-(1 << j)+1]);
    }
};

// 集合T、結合則・可換・冪等律が成り立つ二項演算op
struct maximum {
    using T = ll;
    static T op(const T& a, const T& b) { return max(a, b); }
};
struct maximum_P {
    using T = PII;
    static T op(const T& a, const T& b) { return max(a, b); }
};

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll test;
    cin >> test;
    REP(tes, test) {
        ll n, k;
        cin >> n >> k;
        vector<ll> c(n), d(n);
        REP(i, n) cin >> c[i];
        REP(i, n) cin >> d[i];

        vector<PII> cc(n);
        REP(i, n) cc[i] = {c[i], i};
        sparseTable<maximum_P> seg1(n);
        seg1.init(cc);

        sparseTable<maximum> seg2(n);
        seg2.init(d);

        ll ret = 0;
        REP(i, n) {
            // max(c[l],…,c[r]) = c[i] となるようなl,r
            ll l1, r1;
            ll lb=-1, ub=i;
            while(ub-lb>1) {
                ll mid = (lb+ub)/2;
                if(seg1.query(mid, i) <= cc[i]) ub = mid;
                else lb = mid;
            }
            l1 = ub;
            lb=i, ub=n;
            while(ub-lb>1) {
                ll mid = (lb+ub)/2;
                if(seg1.query(i, mid) <= cc[i]) lb = mid;
                else ub = mid;
            }
            r1 = lb;

            // max(d[l],…,d[r]) <= c[i]+k となるようなl,r
            if(d[i] > c[i]+k) continue;
            ll l2, r2;
            lb=-1, ub=i;
            while(ub-lb>1) {
                ll mid = (lb+ub)/2;
                if(seg2.query(mid, i) <= c[i]+k) ub = mid;
                else lb = mid;
            }
            l2 = ub;
            lb=i, ub=n;
            while(ub-lb>1) {
                ll mid = (lb+ub)/2;
                if(seg2.query(i, mid) <= c[i]+k) lb = mid;
                else ub = mid;
            }
            r2 = lb;

            // max(d[l],…,d[r]) < c[i]-k となるようなl,r
            ll l3, r3;
            lb=-1, ub=i;
            while(ub-lb>1) {
                ll mid = (lb+ub)/2;
                if(seg2.query(mid, i) < c[i]-k) ub = mid;
                else lb = mid;
            }
            l3 = ub;
            lb=i, ub=n;
            while(ub-lb>1) {
                ll mid = (lb+ub)/2;
                if(seg2.query(i, mid) < c[i]-k) lb = mid;
                else ub = mid;
            }
            r3 = lb;

            // max(c[l],…,c[r])=c[i] かつ max(d[l],…,d[r])<=c[i]+k
            ll l = max(l1, l2), r = min(r1, r2);
            ret += (i-l+1) * (r-i+1);
            // max(c[l],…,c[r])=c[i] かつ max(d[l],…,d[r])<c[i]-k
            if(d[i] < c[i]-k) {
                l = max(l1, l3), r = min(r1, r3);
                ret -= (i-l+1) * (r-i+1);
            }
        }

        cout << "Case #" << tes+1 << ": ";
        cout << ret << endl;
    }

    return 0;
}