【题解】HackerRank-Costly Intervals

Posted on In Disqus:

题目

https://www.hackerrank.com/challenges/costly-intervals/problem

题意

给一个数列，对于其中的每一个数，求出包含它的最大区间的长度，使得该区间的区间 OR-AND-MAX+MIN 超过给定的常数 K。

题解

  • 首先观察到 MIN-MAX 是单调减少的，OR-AND 是单调增加的。

  • OR-AND 每次最多改变一位，所以至多有 30 段，每段中都有相同的值。

  • 如果能够求出以每一个数结尾的符合要求的最长区间，那么就能求出包含每一个数的最大区间长度了。

  • 对于每一个结尾的数，处理出前面的不超过 30 段的 OR-AND 和起始结束的位置。首先看能满足条件的最前在哪一段里，然后在那一段里二分出最大的区间。

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
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args << " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) { for (auto x: a) cout << x << ' '; err(args...); }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int maxn = 1E5 + 100;

namespace rmq {
    int f[maxn][20], g[maxn][20];
    inline int highbit(int x) { return 31 - __builtin_clz(x); }
    void init(int* v, int n) {
        FOR (i, 0, n) f[i][0] = g[i][0] = v[i];
        FOR (x, 1, highbit(n) + 1)
            FOR (i, 0, n - (1 << x) + 1) {
                f[i][x] = min(f[i][x - 1], f[i + (1 << (x - 1))][x - 1]);
                g[i][x] = max(g[i][x - 1], g[i + (1 << (x - 1))][x - 1]);
            }
    }
    int get(int l, int r) {
        assert(l <= r);
        int t = highbit(r - l + 1);
        return min(f[l][t], f[r - (1 << t) + 1][t]) -
               max(g[l][t], g[r - (1 << t) + 1][t]);
    }
}

struct P {
   int l, r, o, a;
};
int a[maxn];
vector<int> in[maxn], out[maxn];
int main() {
    int n, K; cin >> n >> K;
    FOR (i, 0, n) scanf("%d", &a[i]);
    rmq::init(a, n);
    vector<P> cur, nxt;
    FOR (i, 0, n) {
        for (P& p: cur) {
            p.o |= a[i];
            p.a &= a[i];
        }
        cur.push_back({i, i, a[i], a[i]});
        nxt.clear();
        for (P& p: cur) {
            if (nxt.empty() || nxt.back().a != p.a || nxt.back().o != p.o)
                nxt.push_back(p);
            else nxt.back().r = p.r;
        }
        cur.swap(nxt);

        for (P& p: cur) {
            auto check = [&](int x) { return rmq::get(x, i) + p.o - p.a >= K; };
            if (check(p.r)) {
                int l = p.l, r = p.r, ans = -1;
                while (l <= r) {
                    int m = l + r >> 1;
                    if (check(m)) { ans = m; r = m - 1; }
                    else l = m + 1;
                }
                int len = i - ans + 1;
                in[ans].push_back(len);
                out[i].push_back(len);
                break;
            }
        }
    }
    multiset<int> S; S.insert(-1);
    FOR (i, 0, n) {
        for (int& x: in[i]) S.insert(x);
        printf("%d\n", *S.rbegin());
        for (int& x: out[i]) S.erase(S.find(x));
    }
}