题解：P9292 [ROI 2018] Robomarathon

· · 题解

求最优排名是简单的。\ 假设求 x 的最优排名，一定只让 x 先走，f_{i} = a_{i}+|i-x|，分讨左右拆绝对值，前后扫一遍就可以维护出排名。

考虑求最劣排名。\ 假设求 x 的最劣排名。\ 发现，一定是让一个前后缀的人先走。比如 ... a ... b ... x，如果让 b 先走了，那 [1,b-1] 的所有点也先走才优，因为这样不仅不会使向 x 的蔓延时间改变，也让非 x 的位置先走，x 更可能排名靠后。

对于下图， 可以发现，对称的 y 的 [1,y] 的前缀也可以先走，因为蔓延到 x 的时间不变。\ 那么 O(n^{2}) 做法就有了。\ 对于每个 x，枚举 d\in[1,\min(x-1,n-x)]，让 [1,x-d]\cup[x+d,n] 的人先走。

注意到，d 越大越优。假设 [x-d+1,x+d-1] 内的点的集合是 X，剩下的点的集合是 Y。\ 考虑 d 增加 1 的变化，从 Y 中取两个点（橙色位置）加入 X。\ 原本 X 内部点的相对排名不变，X 和橙色位置的相对排名不变，X 与剩下的 Y 之间的点的相对时间增加 1。\ 发现 d 增大完全不劣。\ 于是最优情况只有 O(1) 种：让 1 先走、让 n 先走、让 [1,x-\min(x-1,n-x)]\cup[x+\min(x-1,n-x),n] 先走。\ 前两种容易求出。\ 第三种，因为 [1,x-\min(x-1,n-x)],[x-\min(x-1,n-x)+1,x-1],[x+1,x+\min(x-1,n-x)-1],[x+\min(x-1,n-x),n] 这四种区间，x 单增，左右单点分别单调不降，所以可以双指针维护每种区间。\ 这四种区间分别维护的是 a_{i}, a_{i}+i,a_{i}-i,a_{i}。\

O(n\log{n}) 
const int N = 4e5 + 5;
int n, tp, a[N];
int bx[N * 4], bxn;
int Find(int x) {
    return lower_bound(bx + 1, bx + bxn + 1, x) - bx;
}

template<int SZ>
struct BIT {
    int t[SZ];
    void add(int x, int k) {
        while (x <= bxn) {
            t[x] += k;
            x += x & -x;
        }
    }
    int ask(int x) {
        int ret = 0;

        while (x) {
            ret += t[x];
            x -= x & -x;
        }

        return ret;
    }
    void clr() {
        rep(i, 1, bxn)t[i] = 0;
    }
};
BIT<N * 4> t2, t3;

namespace Sol1 {
int ans[N];
BIT<N> t1;
void Sol() {
    rep(i, 1, n)bx[i] = a[i] - i;
    sort(bx + 1, bx + n + 1);
    bxn = unique(bx + 1, bx + n + 1) - bx - 1;
    rep(i, 1, n) {
        int val = Find(a[i] - i);
        ans[i] += t1.ask(val - 1);
        t1.add(val, 1);
    }
    t1.clr();
    rep(i, 1, n)bx[i] = a[i] + i;
    sort(bx + 1, bx + n + 1);
    bxn = unique(bx + 1, bx + n + 1) - bx - 1;
    per(i, n, 1) {
        int val = Find(a[i] + i);
        ans[i] += t1.ask(val - 1);
        t1.add(val, 1);
    }
    rep(i, 1, n)printf("%d\n", ans[i] + 1);
}
}
pii b[N];
int ans[N], A[N], B[N], C[N], D[N], res[N];
bool M2;
int main() {
    read(n), read(tp);
    rep(i, 1, n) read(a[i]);
    if (tp == 1) return Sol1::Sol(), 0;
    rep(i, 1, n)b[i].fi = a[i] + i - 1, b[i].se = i;
    sort(b + 1, b + n + 1);
    for (int i = 1, j = 1; i <= n; ++i) {
        while (j < i && b[j].fi < b[i].fi) ++j;
        ans[b[i].se] = max(ans[b[i].se], j - 1);
    }
    rep(i, 1, n)b[i].fi = a[i] + n - i, b[i].se = i;
    sort(b + 1, b + n + 1);
    for (int i = 1, j = 1; i <= n; ++i) {
        while (j < i && b[j].fi < b[i].fi)
            ++j;

        ans[b[i].se] = max(ans[b[i].se], j - 1);
    }
    bxn = 0;
    rep(i, 1, n) {
        bx[++bxn] = a[i];
        bx[++bxn] = a[i] - i;
        bx[++bxn] = a[i] + i;
        bx[++bxn] = a[i] + min(i - 1, n - i);
    }
    sort(bx + 1, bx + bxn + 1);
    bxn = unique(bx + 1, bx + bxn + 1) - bx - 1;
    rep(i, 1, n) {
        A[i] = Find(a[i]);
        B[i] = Find(a[i] - i);
        C[i] = Find(a[i] + i);
        D[i] = Find(a[i] + min(i - 1, n - i));
    }
    for (int i = 2, l = 0, r = n + 1, al, ar; i < n; ++i) {
        al = i - min(i - 1, n - i), ar = i + min(i - 1, n - i);
        while (l < al) ++l, t2.add(A[l], 1);
        while (l > al) t2.add(A[l], -1), --l;
        while (r > ar) --r, t2.add(A[r], 1);
        while (r < ar) t2.add(A[r], -1), ++r;
        res[i] += t2.ask(D[i] - 1);
    }
    t2.clr();
    for (int i = 2, bl, br, al = 2, ar = 1; i < n; ++i) {
        bl = al, br = ar;
        al = i - min(i - 1, n - i) + 1, ar = i + min(i - 1, n - i) - 1;
        while (bl < al) t2.add(C[bl], -1), ++bl;
        t2.add(C[i], 1);
        while (br < ar) ++br, t3.add(B[br], 1);
        t3.add(B[i], -1);
        res[i] += t2.ask(C[i] - 1) + t3.ask(B[i] - 1);
        ans[i] = max(ans[i], res[i]);
    }
    rep(i, 1, n)write(ans[i] + 1), pc('\n');
    return flush(), 0;
}