[CF1208D] Restore Permutation

题意：有一个长为\(n\)的排列\(p\)，设\(S_i=\sum_{j=1}^{i-1}p_j\cdot[p_j<p_i]\)，给出\(S\)，要求还原出\(p\)。保证有解，\(n\leq 2\times 10^5\)。

考虑倒序将\(S\)还原为全\(0\)的序列，从小到大依次考虑插入每个数的影响。假设在位置\(x\)插入\(i\)，显然此时\(S_x=0\)，且会使得位置\(x\)右侧的每一个未插入数字的\(S_y\)都减去\(i\)。因此对于第\(i\)个数，唯一合法的位置就是所有\(S_x=0\)的位置中最右侧的那个。由于保证有解，维护最小值，在线段树上二分即可。

Code：

#include <cstdio>

#include <cctype>

#include <cassert>

#include <cstring>

#include <iostream>

#include <algorithm>

#define R register

#define ll long long

using namespace std;

const int N = 210000, K = N << 2;

const ll inf = 1e18;

int n, lt[K], rt[K], p[N];

ll a[N], minVal[K], tag[K];

inline void pushdown(int);

template <class T> inline void read(T &x) {

    x = 0;

    char ch = getchar(), w = 0;

    while (!isdigit(ch))

        w = (ch == '-'), ch = getchar();

    while (isdigit(ch))

        x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();

    x = w ? -x : x;

    return;

}

void build(int k) {

    if (lt[k] == rt[k]) {

        minVal[k] = a[lt[k]];

        return;

    }

    int mid = (lt[k] + rt[k]) >> 1, l = k << 1, r = (k << 1) + 1;

    lt[l] = lt[k], rt[l] = mid, lt[r] = mid + 1, rt[r] = rt[k];

    build(l), build(r), minVal[k] = min(minVal[l], minVal[r]);

    return;

}

void modify(int k, int x, int y, ll w) {

    if (lt[k] >= x && rt[k] <= y) {

        minVal[k] += w, tag[k] += w;

        return;

    }

    pushdown(k);

    int mid = (lt[k] + rt[k]) >> 1, l = k << 1, r = (k << 1) + 1;

    if (x <= mid) modify(l, x, y, w);

    if (y > mid) modify(r, x, y, w);

    minVal[k] = min(minVal[l], minVal[r]);

    return;

}

int query(int k) {

    if (lt[k] == rt[k]) {

        minVal[k] = inf;

        return lt[k];

    }

    int l = k << 1, r = (k << 1) + 1, ret;

    pushdown(k), ret = query(minVal[r] ? l : r);

    minVal[k] = min(minVal[l], minVal[r]);

    return ret;

}

inline void pushdown(int k) {

    int l = k << 1, r = (k << 1) + 1;

    if (tag[k]) {

        modify(l, lt[k], rt[k], tag[k]);

        modify(r, lt[k], rt[k], tag[k]);

        tag[k] = 0;

    }

    return;

}

int main() {

    read(n);

    for (R int i = 1; i <= n; ++i)

        read(a[i]);

    lt[1] = 1, rt[1] = n, build(1);

    for (R int i = 1; i <= n; ++i) {

        int pos = query(1);

        p[pos] = i, modify(1, pos, n, -i);

    }

    for (R int i = 1; i <= n; ++i)

        printf("%d ", p[i]);

    return 0;

}

巴特西

[CF1208D] Restore Permutation

最新文章

热门文章