小风的冒险者任务调度

tag

数据结构（树状数组，线段树），模拟

题意简述

对于一个长度为 $n$ 的自然排列，执行 $m$ 次操作，每次操作可以选择一个数，将他移动到排列的最前方。求每个数在排列中出现过的最靠前位置和最靠后位置。

fun fact

赛时看到这题，第一时间想到了平衡树，然后打了一个无旋treap，但是发现treap只能按排名分裂，而本题是找到数本身再操作，然后又想了好久的如何维护排名，最后想到了树状数组维护排名，然后就打了一个树状数组维护每个数的排名+无旋treap维护每个数的最前和最后位置。把题打完之后，突然意识到，树状数组维护排名，答案不就可以直接统计了吗？直接更新就行，为什么要用treap呢？QAQ

题解思路

首先，需要注意到一点：每个数的最小排名只会有两种情况：1或者它本身，对于每次操作，如果对象是这个数，那么它的最小排名就会变成 $1$ ，否则他的排名一定不会变得更优。所以，最小排名只需要看他是否被操作过就行，没操作就是它本身，操作过就是 $1$。难点在于如何维护最大排名。我们思考排名的本质：有多少个数的位置在他的前面。也就是我们可以用权值树状数组维护每个数的位置，一个数的排名就是 $pos_i$ 的前缀和。

然后再来考虑处理操作，想到权值树状数组维护维护位置，每次操作本质上是把一个数的位置移动到所有数的前面，我们可以在权值树状数组的前面预留出 $m$ 个位置，每次操作就把数的权值移动到前面的位置，然后更新答案即可。

参考代码

vector<pii> ans(N + 1);
int bit[N * 2];

void add(int pos, int x)
{
    for(; pos < N * 2; pos += (pos & -pos)) bit[pos] += x;
}

int query(int pos)
{
    int res = 0;
    for(; pos; pos -= (pos & -pos)) res += bit[pos];
    return res;
}

signed main()
{
    IOS;
    int n, m;
    cin >> n >> m;
    vector<int> pos(n + m + 1);
    for(int i = 1; i <= n; i ++)
    {
        // 预留出前面 m 个位置，所有数往后偏移 m
        pos[i] = m + i;
        add(pos[i], 1);
        ans[i].first = ans[i].second = i;
    }
    // 倒着放前面预留的位置
    for(int i = m; i >= 1; i --)
    {
        int p;
        cin >> p;
        ans[p].first = 1;
        int rk = query(pos[p]);
        // 一个数被提前，他原来的排名可能会成为最大排名，更新答案
        ans[p].second = max(ans[p].second, rk);
        add(pos[p], -1);
        pos[p] = i;
        add(pos[p], 1);
    }
    for(int i = 1; i <= n; i ++)
    {
        // 最后所有数确定好之后再更新一次答案
        ans[i].second = max(ans[i].second, query(pos[i]));
        cout << ans[i].first << ' ' << ans[i].second << '\n';
    }
}

赛时写的抽象东西（逃）

ps：不要这样做QAQ

vector<pii> ans(N + 1);

struct fhq_treap
{
    struct node
    {
        int l, r;
        int size;
        unsigned key;
        int val;
        int min, max;
        int tag;
        node() {tag = val = size = key = l = r = 0;}
        node(int val, int size,int key) : val(val), size(size), key(key), min(val), max(val) {tag = l = r = 0;}
    };
    vector<node> tr;
    random_device rd;
    mt19937 rng;
    int root;
    fhq_treap()
    {
        root = 0;
        tr.resize(1);
        rng = mt19937(rd());
    }
    int create(int v)
    {
        int u = tr.size();
        tr.push_back(node(v, 1, rng()));
        return u;
    }
    void pushup(int u)
    {
        tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + 1;
        tr[u].max = max(tr[u].max, tr[u].val);
    }
    void pushdown(int u)
    {
        if (tr[u].tag)
        {
            tr[tr[u].l].val += tr[u].tag;
            tr[tr[u].l].tag += tr[u].tag;
            tr[tr[u].r].val += tr[u].tag;
            tr[tr[u].r].tag += tr[u].tag;
            tr[u].tag = 0;
        }
    }
    void split_by_val(int u, int val, int &x, int &y)
    {
        if (!u)
        {
            x = y = 0;
            return;
        }
        if (tr[u].val <= val)
        {
            x = u;
            split_by_val(tr[x].r, val, tr[u].r, y);
        }
        else
        {
            y = u;
            split_by_val(tr[u].l, val, x, tr[u].l);
        }
        pushup(u);
    }
    void split_by_rank(int u, int rank, int &x, int &y)
    {
        if (!u)
        {
            x = y = 0;
            return;
        }
        pushdown(u);
        if (rank > tr[tr[u].l].size)
        {
            rank -= tr[tr[u].l].size + 1;
            x = u;
            split_by_rank(tr[u].r, rank, tr[u].r, y);
        }
        else
        {
            y = u;
            split_by_rank(tr[u].l, rank, x, tr[u].l);
        }
        pushup(u);
    }
    int merge(int x, int y)
    {
        if (!x || !y)
            return x + y;
        if (tr[x].key < tr[y].key)
        {
            pushdown(x);
            tr[x].r = merge(tr[x].r, y);
            pushup(x);
            return x;
        }
        else
        {
            pushdown(y);
            tr[y].l = merge(x, tr[y].l);
            pushup(y);
            return y;
        }
    }
    void insert(int val)
    {
        int z = create(val);
        int x, y;
        split_by_val(root, val, x, y);
        root = merge(merge(x, z), y);
    }
    void del(int val)
    {
        int x, y, z;
        split_by_val(root, val, x, z);
        split_by_val(x, val - 1, x, y);
        y = merge(tr[y].l, tr[y].r);
        root = merge(merge(x, y), z);
    }
    int get_rank(int u, int k) // 获取排名为k的树
    {
        if (k <= tr[tr[u].l].size)
            return get_rank(tr[u].l, k);
        else if (k == tr[tr[u].l].size + 1)
            return tr[u].val;
        else
            return get_rank(tr[u].r, k - tr[tr[u].l].size - 1);
    }
    int rank(int val) // 获取val的排名
    {
        int x, y;
        split_by_val(root, val - 1, x, y);
        int res = tr[x].size + 1;
        merge(x, y);
        return res;
    }
    int pre(int val)
    {
        int x, y;
        split_by_val(root, val - 1, x, y);
        int res = get_rank(x, tr[x].size);
        root = merge(x, y);
        return res;
    }
    int suc(int val)
    {
        int x, y;
        split_by_val(root, val, x, y);
        int res = get_rank(y, 1);
        root = merge(x, y);
        return res;
    }
    node &operator[](int idx)
    {
        return tr[idx];
    }
    void inorder(int u)
    {
        pushdown(u);
        if(tr[u].l != 0) inorder(tr[u].l);
        if(tr[u].r != 0) inorder(tr[u].r);
        pushup(u);
        ans[u] = {tr[u].min, tr[u].max};
    }
};

int bit[N * 2];

void add(int pos, int x)
{
    for(; pos < N * 2; pos += (pos & -pos)) bit[pos] += x;
}

int query(int pos)
{
    int res = 0;
    for(; pos; pos -= (pos & -pos)) res += bit[pos];
    return res;
}

signed main()
{
    IOS;
    int n, k;
    cin >> n >> k;
    fhq_treap fhq;
    vector<int> pos(n + k + 1);
    for(int i = 1; i <= n; i ++)
        fhq.insert(i), pos[i] = n - i + 1, add(pos[i], 1);
    for(int i = 1; i <= k; i ++)
    {
        int p;
        cin >> p;
        int rk = query(n + k + 1) - query(pos[p] - 1);
        add(pos[p], -1);
        pos[p] = n + i;
        add(pos[p], 1);
        int x = 0, y = 0, z = 0;
        fhq.split_by_rank(fhq.root, rk, x, y);
        fhq.split_by_rank(x, rk - 1, x, z);
        fhq[x].val += 1;
        fhq[x].tag += 1;
        fhq[z].val = fhq[z].min = 1;
        fhq.root = fhq.merge(z, fhq.merge(x, y));
    }
    fhq.inorder(fhq.root);
    for(int i = 1; i <= n; i ++)
    {
        cout << ans[i].first << ' ' << ans[i].second << '\n';
    }
}