/ ALGORITHM

北京师范大学第十五届ACM决赛

Contest Information

source: It’s from the nowcoder

Problem H

定义ACM竞赛中 荣誉提名奖 颁给总排名 $>0.6*n$ 的队伍

现在有 $n$ 支队伍参加比赛,第 $i$ 支队伍的排名是 $p_i$, 接下来发送 $q$ 个事件,分为两种

  1. 给定 $ x, y(1≤x,y≤n) $,表示第 $x$ 支队伍的排名上升到 $y$ 。
  2. 给定 $ x, y(1≤x,y≤n) $,查询 $[x,y]$ 区间内获得荣誉提名的队伍的数量。

数据范围:$ T ≤ 500, 1 ≤n≤50000, 1≤q≤50000$

Solution

首先,如果不考虑修改,只查询区间内荣誉提名队伍数量,我们很容易想到的是以队伍序号为下标,如果被荣誉提名则标记为 $1$,然后用前缀和来做区间查询。

现在加入修改后,我们考虑修改产生的影响,因为队伍排名只会被直接往上提,那么只有在原来排名 $>0.6*n$ 的队伍被直接提升到 $<=0.6*n$ 时,才会改变荣誉提名的队伍:排名为 $x$ 的队伍会从荣誉提名的队伍中删除,排名在 $0.6*n$ 的队伍会被加入到 荣誉提名的队伍。

单点修改+区间查询,显然是用树状数组来实现了。接下来我们只需要解决对于给定的一个队伍序号,如何查询其排名,对于给定的一个排名,我们如何查询其队伍序号,这部分就可以用各种平衡树来实现。

下面简单说一下 $treap$ 的做法:

  • 首先,我们按照排名排序,将 $n$ 支队伍按序合并建立 $treap$,由于二叉树的性质,$treap$ 的中序遍历就是排名顺序。

  • 在建立节点的过程中,我们保存下来每支队伍的序号和它在 $treap$ 中结点的序号,这样我们就可以直接通过队伍序号找到它在 $treap$ 中的位置了。

  • 查询操作:

    • 给定队伍序号,查询队伍排名:通过序号找到该队伍在 $treap$ 中的位置。由于二叉树的中序遍历即排名顺序,那么从该节点处一直往上回溯,同时累加左子树的大小,直到根节点。最后结果就是该队伍的排名。
    • 给定队伍排名,查询队伍序号:同样利用中序遍历,从根节点往下搜索,找到对应排名的节点,节点处存储的就是队伍序号。
  • 修改操作:

    • 将序号为 $x$ 的队伍提升到排名为 $y$:先查询对应序号的队伍的排名,然后在 $treap$ 中提出 $rank_x$ 的节点,把它拎到 $y$ 处即可。

AC code

//bit 树状数组
//t 平衡树
int main()
{
    int Case,rk;
    scanf("%d", &Case);
    while(Case--)
    {
        scanf("%d", &n);
        t.init();
        bit.init(n);       
        int limit = n*3/5;
        for(int i=1;i<=n;i++)
        {
            scanf("%d", &rk);
            o[i].id = i, o[i].rk = rk;
        }
        sort(o+1, o+1+n);
        for(int i=1;i<=n;i++)
        {
            int id = o[i].id;
            b[id] = t.newNode(id);
            t.merge(t.root, t.root, b[id]);
        }
        for(int i=limit+1;i<=n;i++) bit.update(o[i].id, 1);
        int q,op,x,y;
        scanf("%d", &q);
        while(q--)
        {
            scanf("%d%d%d", &op, &x, &y);
            if(op == 1)
            {
                int rank = t.id_to_rank(b[x]);
                if(rank > limit &&  y <= limit)
                {
                    int id = t.rank_to_id(limit-1);
                    bit.update(id,1);
                    bit.update(x,-1);
                }
                t.diverse(rank, y);
            }
            else
            {
                int ans = bit.sum(y)-bit.sum(x-1);
                printf("%d\n", ans);
            }
        }
    }
}