CF 1208D Restore Permutation 線段樹

現在藏起來一個1到n(2e5)的排列, 對于每個位置i, 給出a[1]到a[i-1]中小于a[i]的數的和s[i], 讓我們求這個排列a.

首先我們找找1的位置.

因為沒有數比1小, 是以不論1在哪裡, 它的s肯定是0;

而如果s中有多個0, 1一定在最後一個0—因為如果1在其他0的位置, 最後一個0沒法解釋—不論最後一個數是什麼, 它肯定比1大, 前面的1一定會對這個數産生貢獻, 這樣我們就證明了1肯定在最後一個0的位置.

自然我們想到把1到n每個數按照這樣的方式一個個歸位.

一開始我的思路是這樣的:

1的位置已經确定, 2的位置要麼在1前面, 要麼在1後面. 如果在1前, 那麼它一定是1前最後一個0; 如果在1後, 它一定是1後面最後一個1. 然後一個個确定.

但是這樣是不行的. 且不說程式難以實作, 單是判斷在前在後就無從下手.

換一個思路(zl666):

每當将一個數歸位, 我們就将它産生的貢獻去除, 這樣我們每次隻須去數組中找最後一個0就好.

具體地, 找到1的位置pos, s數組從pos開始後面全減1; 最後一個0就是2的位置pos2, s從pos2後面全減2; 最後一個0就是3的位置pos3, s從pos3後面全減3······

我們可能要問, 如果2在1前, 那麼1的的位置會不會再被用到? 是以我們要在确定1的位置後把1的位置剔除考慮範圍, 具體操作其實可以把s[1]賦為INF, 保證它在所有可能的-2/-3/-4/···中不會減到0就好了.

那麼這個題就轉化為求s數組最後一個0的位置就是i的位置, 然後把它改成INF, 它後面所有的數-i, 再找最後一個0的位置···

這個過程可以用線段樹解決:

維護區間最小值, 如果右區間最小值是0, 那麼往右走; 否則往左走. 這樣就能log(n)找到最後一個0的位置.

改成INF就是單點更新, pos+1到n減i就是區間更新. lazy維護減了多少.

代碼:

ll n, a[M];
struct node {
    ll lz, mx;
} tree[M * 4];

void build(int pos, int l, int r) {
    if (l == r) {
        tree[pos].mx = tree[pos].lz = read();
        return;
    }
    int mid = (l + r) / 2;
    build(pos * 2, l, mid);
    build(pos * 2 + 1, mid + 1, r);
    tree[pos].mx = sml(tree[pos * 2].mx, tree[pos * 2 + 1].mx);
}

void pushDown(int pos) {
    tree[pos * 2].lz += tree[pos].lz;
    tree[pos * 2 + 1].lz += tree[pos].lz;
    tree[pos * 2].mx += tree[pos].lz;
    tree[pos * 2 + 1].mx += tree[pos].lz;
    tree[pos].lz = 0;
}

void pushUp(int pos) {
    tree[pos].mx = sml(tree[pos * 2].mx, tree[pos * 2 + 1].mx);
}

int query(int pos, int l, int r) {
    if (l == r)return l;
    pushDown(pos);
    int mid = (l + r) / 2;
    if (tree[pos * 2 + 1].mx == 0)query(pos * 2 + 1, mid + 1, r);
    else query(pos * 2, l, mid);
}

void update1(int pos, int l, int r, int p) {
    if (l == r && l == p) {
        tree[pos].mx = INF;
        return;
    }
    pushDown(pos);
    int mid = (l + r) / 2;
    if (p <= mid)update1(pos * 2, l, mid, p);
    else update1(pos * 2 + 1, mid + 1, r, p);
    pushUp(pos);
}

void update2(int pos, int l, int r, int ul, int ur, int v) {
    if (ul <= l && ur >= r) {
        tree[pos].mx -= v;
        tree[pos].lz -= v;
        return;
    }
    pushDown(pos);
    int mid = (l + r) / 2;
    if (ul <= mid)update2(pos * 2, l, mid, ul, ur, v);
    if (ur > mid)update2(pos * 2 + 1, mid + 1, r, ul, ur, v);
    pushUp(pos);
}


void init() {
    n = read();
    build(1, 1, n);
    for (int i = 1; i <= n; ++i) {
        int pos = query(1, 1, n);
        a[pos] = i;
        update1(1, 1, n, pos);
        update2(1, 1, n, pos, n, i);
    }
    for (int i = 1; i <= n; ++i)write(a[i]), space;
    enter;
}