RochesterSequence [SRM474 Div1 Hard]

https://community.topcoder.com/stat?c=problem_statement&pm=15288

N要素の配列Aがある。
この配列からいくつかの要素を取り除いて、validな配列を作る。
validな数列の最大長と、それを作るために取り除く方法の組み合わせを求めよ。

※validな配列

• 要素数が偶数個
• 順番に先頭と末尾から数を取り出して和を求める操作を行ってできる数列が非減少列となる

N≦10^3, 数≦10^9+6

前提知識

• 3次元LIS

解説

この問題は3次元LISに帰着できる。
snukeさんの解説で分かった

状態として、(A[L]+A[R],L,R)を考える。
Rは左からではなく、右から考える。
このように状態を定めたときの3次元LISが答え。
ただし、A[L]+A[R]は等しくてもいい。
　
3次元LISをどのように解くかという問題がある。
自分は2次元セグメントツリーを使って殴った。
削除の組み合わせもセグメントツリーのマージのときに長さが最長であれば、まとめる処理を入れればいい。
以下のコードで3.8sとかなので、かなりギリギリである。

using T = tuple<int, int, int>;
struct RochesterSequence {
    vector <int> solve(vector <int> Sprefix, int n, int a, int b, int m) {
        int sn = Sprefix.size();
        rep(i, sn, n) Sprefix.push_back((1LL * Sprefix.back() * a + b) % m);

        vector<int> dic;
        rep(L, 0, n) rep(R, L + 1, n) dic.push_back(Sprefix[L] + Sprefix[R]);
        sort(all(dic));
        dic.erase(unique(all(dic)), dic.end());

        vector<T> points;
        vector<vector<int>> idx(n);
        rep(L, 0, n) rep(R, L + 1, n) {
            int x = lower_bound(all(dic), Sprefix[L] + Sprefix[R]) - dic.begin();
            int y = L;
            int z = n - R - 1;
            
            points.push_back(make_tuple(x, y, z));
            idx[y].push_back(z);
        }
        sort(all(points));

        Healthy2DSegTreeVer2 st;
        st.init(idx);

        int ans1 = -1;
        int ans2 = 0;
        fore(t, points) {
            int x, y, z; tie(x, y, z) = t;
            auto opt = st.get(0, y, 0, z);
            
            int ma = opt.first + 1;
            int cm = opt.second;

            if (ma == 1) cm = 1;

            auto cur = st.get(y, y + 1, z, z + 1);
            if (cur.first < ma) {
                if (ans1 < ma) {
                    ans1 = ma;
                    ans2 = cm;
                }
                else if (ans1 == ma) ans2 = (ans2 + cm) % mod;
                st.update(y, z, make_pair(ma, cm));
            }
            else if (cur.first == ma) {
                if (ans1 < ma) {
                    ans1 = ma;
                    ans2 = cm;
                }
                else if (ans1 == ma) ans2 = (ans2 + cm) % mod;
                st.update(y, z, make_pair(ma, (cm+cur.second)%mod));
            }
        }

        ans1 *= 2;
        return { ans1, ans2 };
    }
};