题解：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})

CPP

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;
}

题解：P9292 [ROI 2018] Robomarathon

文章操作

相关推荐

评论

题解：P9292 [ROI 2018] Robomarathon