Facebook Hacker Cup 2016 Round 2 Snakes and Ladders

問題

https://www.facebook.com/hackercup/problem/1640119959603837/

解法

まず, はしごを座標順にソートして, よくある stack のアレを使います。
mayokoex.hatenablog.com
この記事のテクニックを使えば, O(N) であるハシゴからどこまで蛇が繋がれるのかがわかります。

dp[i] = (i 番目のはしごと, i 番目のはしごと高さの等しい, 蛇がつながることの出来る i 番目未満のはしごの間における, 蛇の長さの二乗の和) とします。例えば問題文の Case #3 だと,
dp[0] = 0
dp[1] = 0
dp[2] = 1
dp[3] = 9
dp[4] = 0
です。答えはこの dp の値から sum(dp[i]) = 10 と求められます。

dp を求められるとハッピーなのですが, dp の情報だけからは dp を高速で求めることが出来ません。
そこで, dp2[i] = (i 番目のはしごと, i 番目のはしごと高さの等しい, 蛇がつながることの出来るはしご の間の距離の和, およびそのようなはしごの数の合計) という変数を考えます。

i 番目のはしごと高さの等しい, 一つ前のはしごを prev とし, prev と i の距離が w であるとします。prev より前にも高さの等しいはしごが 3 つあって, prev とそれらのはしごとの距離が x, y, z であったとすると, はしご i と prev を含めた 4 つのはしごとの距離の二乗和は,
w^2 + (x+w)^2 + (y+w)^2 + (z+w)^2 = (x^2+y^2+z^2) + 2*w*(x+y+z) + 4*w^2
となります。右辺の第一項は dp[prev] からわかり, 第二項, 第三項は dp2[prev] からわかります。よって, これらの値を更新するように dp をしていけば良いです。

const int MAXN = 200200;
const int MOD = 1e9+7;
int range[MAXN];
int N;
ll dp[MAXN];
pii dp2[MAXN];
pii P[MAXN];

void calc() {
    stack<pii> S;
    int cur = N-1;
    while (cur >= 0) {
        S.push(pii(P[cur].second, cur));
        int i = cur-1;
        while (S.top().first >= P[i].second && i >= 0) {
            S.push(pii(P[i].second, i));
            i--;
        }
        while (!S.empty() && S.top().first < P[i].second) {
            auto p = S.top();
            range[p.second] = i;
            S.pop();
        }
        cur = i;
    }
    while (!S.empty()) {
        auto p = S.top();
        range[p.second] = 0;
        S.pop();
    }
}

void solve(int T) {
    cin >> N;
    map<int, vector<pii> > mp;
    for (int i = 0; i < N; i++) {
        cin >> P[i].first >> P[i].second;
    }
    sort(P, P+N);
    calc();
    for (int i = 0; i < N; i++) {
        mp[P[i].second].push_back(pii(P[i].first, i));
    }
    for (int i = 1; i < N; i++) {
        const vector<pii>& v = mp[P[i].second];
        int index = lower_bound(v.begin(), v.end(), pii(P[i].first, i)) - v.begin();
        if (index > 0) {
            int prev = v[index-1].second;
            int now = v[index].second;
            if (range[now] > prev) {
                dp2[i] = pii(0, 0);
                dp[i] = 0;
                continue;
            }
            dp2[now] = dp2[prev];
            ll x = P[now].first-P[prev].first;
            x %= MOD;
            dp2[now].second++;
            (dp2[now].first += (dp2[now].second*x)%MOD) %= MOD;
            dp[now] = ((ll)(dp2[now].second) * ((x*x)%MOD)) % MOD;
            (dp[now] += dp[prev]) %= MOD;
            (dp[now] += (((2*x)%MOD)*(ll)(dp2[prev].first))%MOD) %= MOD;
        } else {
            dp2[i] = pii(0, 0);
            dp[i] = 0;
        }
    }
    ll ans = 0;
    for (int i = 0; i < N; i++) {
        (ans += dp[i]) %= MOD;
    }
    cout << "Case #" << T << ": " << ans << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        solve(t);
    }
    return 0;
}