백준26613 수열과 구간과 구간과 구간과 쿼리

작성일 | In

문제 링크

  • http://icpc.me/26613

사용 알고리즘

  • CHT
  • 파라메트릭 서치

시간복잡도

  • $O(N \log N \log X + Q \log N \log^2 X)$

풀이

최적화 문제 대신 결정 문제를 해결합시다. 즉, 상수 $k$가 주어졌을 때 $(S_r-S_l)/(r-l) \geq k$를 만족하는 $a \leq l \leq b \leq c \leq r \leq d$가 존재하는지 판별하는 문제를 해결합시다.

부등식을 전개하면 $rx-S_r \leq lx-S_l$이 됩니다. 즉, $a \leq l \leq b$에서는 $lx-S_l$을 최대화해야 하고, $c \leq r \leq d$에서는 $rx-S_r$을 최소화해야 합니다. 일차 함수가 여러 개 있을 때 특정 $x$좌표에서 최대/최소를 빠르게 구하는 방법은 Convex Hull Trick이라는 이름으로 잘 알려져 있습니다.
하지만 이 문제에서는 전체 직선이 아닌 구간에 있는 직선만 고려해야 한다는 점이 조금 다릅니다. 이런 경우에는 세그먼트 트리의 각 정점마다 CHT를 관리하는 것으로 해결할 수 있습니다. 일반적인 CHT의 시간 복잡도에 $log$가 하나 붙게 됩니다.

만약 CHT를 Li Chao Tree를 이용해 구현했다면 세그먼트 트리를 만드는 것은 $O(N \log N \log X)$, 쿼리의 정답을 구하는 것은 매번 $O(N \log N \log^2 X)$가 됩니다. 따라서 전체 시간 복잡도는 $O(N \log N \log X + Q \log N \log^2 X)$가 되고, $N, Q$가 별로 크지 않고 시간 제한이 5초나 되기 때문에 문제를 해결할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int RANGE = 1 << 27;
constexpr int SZ = 1 << 17;
constexpr ll INF = 0xc0c0c0c0c0c0c0c0;

struct Line{
    ll a, b;
    Line() : Line(0, INF) {}
    Line(ll a, ll b) : a(a), b(b) {}
    ll f(ll x) const { return a * x + b; }
};

struct LiChaoTree{
    struct Node{
        int l, r; Line v;
        Node() : l(-1), r(-1), v() {}
    };
    vector<Node> T;
    LiChaoTree(){ clear(); }
    void clear(){ T.clear(); T.emplace_back(); }
    void update(Line v, int node=0, int s=0, int e=RANGE-1){
        Line lo = T[node].v, hi = v;
        if(lo.f(s) > hi.f(s)) swap(lo, hi);
        if(lo.f(e) <= hi.f(e)){ T[node].v = hi; return; }
        int m = (s + e) / 2;
        if(lo.f(m) < hi.f(m)){
            T[node].v = hi;
            if(T[node].r == -1) T[node].r = T.size(), T.emplace_back();
            update(lo, T[node].r, m+1, e);
        }
        else{
            T[node].v = lo;
            if(T[node].l == -1) T[node].l = T.size(), T.emplace_back();
            update(hi, T[node].l, s, m);
        }
    }
    void add(ll a, ll b){ update(Line(a, b)); }
    ll query(ll x, int node=0, int s=0, int e=RANGE-1) const {
        ll res = node != -1 ? T[node].v.f(x) : INF;
        if(node == -1 || s == e) return res;
        int m = (s + e) / 2;
        if(x <= m) res = max(res, query(x, T[node].l, s, m));
        else res = max(res, query(x, T[node].r, m+1, e));
        return res;
    }
};

struct SegmentTree{
    vector<LiChaoTree> T;
    SegmentTree() : T(SZ*2) {}
    void insert(int x, ll a, ll b){ for(x|=SZ; x; x>>=1) T[x].add(a, b); }
    ll query(int l, int r, ll x) const {
        l |= SZ; r |= SZ; ll res = 0xc0c0c0c0c0c0c0c0;
        while(l <= r){
            if(l & 1) res = max(res, T[l++].query(x));
            if(~r & 1) res = max(res, T[r--].query(x));
            l >>= 1; r >>= 1;
        }
        return res;
    }
};

ll N, Q, A[101010];
SegmentTree T1, T2;

bool Check(int a, int b, int c, int d, int x){
    return T2.query(c, d, x) + T1.query(a-1, b-1, x) >= 0;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> Q;
    for(int i=1; i<=N; i++) cin >> A[i], A[i] += A[i-1];
    for(int i=0; i<=N; i++) T1.insert(i, i, -A[i]), T2.insert(i, -i, A[i]);
    for(int q=1; q<=Q; q++){
        int a, b, c, d; cin >> a >> b >> c >> d;
        int l = 0, r = 1e8;
        while(l < r){
            int m = (l + r + 1) / 2;
            if(Check(a, b, c, d, m)) l = m; else r = m - 1;
        }
        cout << l << "\n";
    }
}