C - 茶碗と豆 AtCoder Regular Contest 038

C: 茶碗と豆 - AtCoder Regular Contest 038 | AtCoder

豆一つをnimの山として考えられる。
よって、全ての茶碗についてgrundy数を求め、A[i]回xorを取った物たちをxorすればいい。

難しいのはgrundy数を求める方法。
区間 [ i - c[i] , i ) に含まれない最小の非負整数を10^5回求める必要がある。

上を言い換えると[i]のgrundy数は、以下の条件を満たす最大のKである。
[ i - c[i] , i )にgrundy数が0 ~ k-1となる物が含まれる。
↑条件１

これは、RMQのセグメント木で
[i] := grundy数がiとなる最大のインデックス（iを0から順に見ており、区間は右にズレていくため、最大のほうが得だから）
[l r):= [ [l] [r]) で最小のインデックスとすれば

grundy数が[0 k)の物の内、最小のインデックスが分かる。
この数は必ずi未満のため、i-c[i]以上なら、[i-c[i] , i) で条件１を満たす。

条件1を満たす数はoooooooxxxxxのようになるため、二分探索で解ける。

よって、O(N log n log n)で解けた
Submission #3889989 - AtCoder Regular Contest 038 | AtCoder

struct Monoid {
    ll i, v;
    Monoid(ll i, ll v) : i(i), v(v) {}
};
#define segMinl [](Monoid a,Monoid b){return a.v <= b.v ? a : b;} , Monoid(-1,MAX(ll))
#define segMinr [](Monoid a,Monoid b){return a.v < b.v ? a : b;} , Monoid(-1,MAX(ll))
#define segMaxl [](Monoid a,Monoid b){return a.v >= b.v ? a : b;} , Monoid(-1,MIN(ll))
#define segMaxr [](Monoid a,Monoid b){return a.v > b.v ? a : b;} , Monoid(-1,MIN(ll))
#define segSum  [](Monoid a,Monoid b){return Monoid(a.i+b.i,a.v+b.v);} , Monoid(0,0)

struct SegmentTree {
    using func=function<Monoid(Monoid, Monoid)>;
    int n;
    vector<Monoid> seg;
    const func f;
    const Monoid e;
    SegmentTree(int len, func f, const Monoid e) : f(f), e(e) {
        n = 1;
        while (n < len)n *= 2;
        seg.assign(2 * n - 1, e);
    }
    SegmentTree(vi dat, const func f, const Monoid e) : f(f), e(e) {
        n = 1;
        int asz = dat.size();
        while (n < asz)n *= 2;
        seg.assign(2 * n - 1, e);
        rep(i, asz) seg[i + n - 1] = Monoid(i, dat[i]);
        rer(i, n - 2)seg[i] = f(seg[i * 2 + 1], seg[i * 2 + 2]);
    }
    void update(int k, int v) {
        seg[k + n - 1] = Monoid(k, v);
        k += n - 1;
        while (k) {
            k = (k - 1) / 2;
            seg[k] = f(seg[k * 2 + 1], seg[k * 2 + 2]);
        }
    }
    void add(int k, int v) {
        update(k, v + seg[k + n - 1].v);
    }
    Monoid query(int a, int b, int k = 0, int l = 0, int r = -1) {
        if (r == -1)r = n;
        if (r <= a || b <= l)return e;
        else if (a <= l && r <= b)return seg[k];
        else {
            Monoid sl = query(a, b, k * 2 + 1, l, (l + r) / 2);
            Monoid sr = query(a, b, k * 2 + 2, (l + r) / 2, r);
            return f(sl, sr);
        }
    }
    int geti(int a, int b) {
        return query(a, b).i;
    }
    ll getv(int a, int b) {
        return query(a, b).v;
    }
    Monoid operator[](int k) const {
        return seg[k + n];
    }
};
int N, K, M, H, W, X, Y, q, Q, r;
vi A, B, C;
signed main() {
    cin >> N;
    add2(C, A, N - 1);
    //[i] grundy数が0~k-1となる者たちのインデックス　の最小値
    //[l r) のインデックスのうちの最小
    SegmentTree st(vi(k5, -1), segMinr);
    st.update(0, 0);
    int gr;
    int grgr = 0;
    //iのgrundy数を求めたい
    rep(i, 1, N) {
        //seg[0 K) >= i-c[i] となる最大のK
        int ok = 0, ng = k6;
        while (abs(ok - ng) > 1) {
            int mid = (ok + ng) / 2;
            if (st.getv(0, mid) >= i - C[i - 1])ok = mid;
            else ng = mid;
        }
        gr = ok;
        st.update(gr, i);
        if (A[i - 1] % 2)grgr ^= gr;
    }
    if (grgr)cout << "First" << endl;
    else cout << "Second" << endl;

    return 0;
}