SRM 681 div1 med: LimitedMemorySeries2

問題

TopCoder Statistics - Problem Statement

解法

愚直にやって普通に解が得られます。

配列 X の最大値を xmax とすると, xmax 未満の値は xmax を超えて半径が飛んでいくことはないので, xmax で配列が分割されることになります。

xmax が真ん中にあるときが一番最悪(quick sort みたいな感じで xmax が端っこにあると再帰の深さが N になって一番嫌なんじゃないかと思うかもしれませんが, 端っこにある場合は xmax の半径を計算するのにかかる計算量が O(1) なのでむしろありがたいです)で, この場合のすべての半径を求めるのにかかる時間 T は, 配列のサイズを N を用いて, 最悪でも
T(N) = N/2 + 2*T(N/2)
となるので, T(N) の計算量は O(N log N) です。今まで「大きい順に配列の値を取る」と考えてましたが, 普通に計算しようとしても配列で見る範囲が制限されるので, 愚直に計算しても最悪計算量は O(N log N) です。

普通に O(N) でやろうと考えると stack になるのかな？

class LimitedMemorySeries2 {
public:
    ll next(ll x, ll a, ll b) {
        return ((x^a)+b) & ((1ll<<50)-1);
    }
    ll prev(ll x, ll a, ll b) {
        return ((x-b)^a) & ((1ll<<50)-1);
    }
    int getSum(int n, long long x0, long long a, long long b) {
        const int MOD = 1e9+7;
        int ans = MOD;
        ll x = x0;
        for (int i = 0; i < n; i++) {
            int k = 0;
            ll px = x, fx = x;
            while (i-k >= 0 && i+k < n) {
                if (k!=0 && (px >= x || fx >= x)) break;
                k++;
                px = prev(px, a, b);
                fx = next(fx, a, b);
            }
            k--;
            (ans += k) %= MOD;
            x = next(x, a, b);
        }
        return ans;
    }
};