#424 Div2 E

#424 Div2 E

题意

给出一个 n 个数的数列，从前往后取数，如果第一个数是当前数列的最小值，则取出，否则将它放到数列尾端，问使数列为空需要多少步操作。

分析

用数据结构去模拟。

线段树维护区间最小值及取得最小值的位置。树状数组维护仍存在的数的个数（ 1 表示未取，0 表示已取）。

首先寻找全局最小值，那么答案加上它前面的存在的数的个数，然后删掉这个值，（在线段树中将这个值置为无穷大等价于删除掉它）。

设这个前面删掉的最小值位置为 idx，那么再从 idx+1 往后找，是否存在全局最小值。

如果存在下标为 pos ，那么答案加上区间 (idx, pos] 仍然存在的数的个数（使用树状数组计算），再把 idx 置为 pos。

如果不存在，答案加上 (idx, n] 仍然存在的数的个数，退出当前循环，从头开始找（即把 idx 置为 0）。

code

#include<bits/stdc++.h>

#define lson l, m, rt * 2

#define rson m + 1, r, rt * 2 + 1

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 5;

const int INF = 2e9 + 1;

int a[MAXN];

struct BIT {

    int f[MAXN];

    void add(int p, int c) {

        while(p <= MAXN) {

            f[p] += c;

            p += (p & -p);

        }

    }

    int query(int p) {

        int s = 0;

        while(p) {

            s += f[p];

            p -= (p & -p);

        }

        return s;

    }

} bit;

struct ST {

    struct node {

        int id, val;

        node() {}

        node(int id_, int val_):id(id_), val(val_) {}

    } ary[MAXN << 2];

    node pushUp(node& nd, int rt) {

        if(ary[2 * rt].val <= ary[2 * rt + 1].val) {

            nd.id = ary[2 * rt].id;

            nd.val = ary[2 * rt].val;

        } else {

            nd.id = ary[2 * rt + 1].id;

            nd.val = ary[2 * rt + 1].val;

        }

    }

    void build(int l, int r, int rt) {

        if(l == r) {

            ary[rt].id = l;

            ary[rt].val = a[l];

            return;

        }

        int m = (l + r) / 2;

        build(lson);

        build(rson);

        pushUp(ary[rt], rt);

    }

    void query(int L, int R, int& pos, int& res, int l, int r, int rt) {

        if(L <= l && R >= r) {

            if(ary[rt].val < res) {

                res = ary[rt].val;

                pos = ary[rt].id;

            }

            return;

        }

        int m = (l + r) / 2;

        if(L <= m) query(L, R, pos, res, lson);

        if(R > m)  query(L, R, pos, res, rson);

    }

    void update(int p, int val, int l, int r, int rt) {

        if(l == r) {

            ary[rt].val = val;

            return;

        }

        int m = (l + r) / 2;

        if(m < p) update(p, val, rson);

        else update(p, val, lson);

        pushUp(ary[rt], rt);

    }

} st;

int main() {

    int n;

    cin >> n;

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

        cin >> a[i];

        bit.add(i, 1);

    }

    st.build(1, n, 1);

    ll ans = 0;

    for(int T = 0; T < n;) {

        for(int idx = 0; idx < n && T < n;) {

            int minV = INF, minv = INF, posV, posv;

            st.query(1, n, posV, minV, 1, n, 1);

            st.query(idx + 1, n, posv, minv, 1, n, 1);

            if(minv != minV) {

                ans += bit.query(n) - bit.query(idx);

                break;

            }

            ans += bit.query(posv) - bit.query(idx);

            st.update(posv, INF, 1, n, 1);

            bit.add(posv, -1);

            T++;

            idx = posv;

        }

    }

    cout << ans << endl;

    return 0;

}