欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【Educational Codeforces Round 80(div2)】E-Messenger Simulator (树状数组)

程序员文章站 2022-06-04 18:14:55
...

一、题目链接

https://codeforces.com/contest/1288/problem/E

二、题意

读入整数n、m以及m次操作。

起初,数列中为整数1~n按升序排列,对应位置1~n。每次操作读入aia_i,将数列中的aia_i移动到数列最前面,更新数列内所有数位置。求执行完所有操作后,1~n每个整数在操作过程中位置的最大值和最小值。

三、数据范围

1 ≤ n, m ≤ 3 * 10510^5

1 ≤ aia_i ≤ n

四、解题思路

首先,对每次操作,暴力循环更新位置肯定是行不通的。如何对这一步进行优化?

怎么把指定数字向前移动?

很容易想到在原数列前增加m个空位,每次操作把aia_i从后往前放到那m个空位里,更新aia_i的最小位置为1,把aia_i原位置清除。

怎么更新其他数字的位置?

没有被操作的数不必移动。开一个长m+n的数列e,把有元素的位置记为1,没有元素的位置记为0,(初始e[1]~e[m]=0,e[m+1]~e[m+n]=1)每次操作进行两个修改:原位置变成0,新位置变成1,那么每个数的位置其实就是求该位置前有多少个”1“,即该位置的前缀和。

怎么快捷地修改、查询前缀和?

树状数组。:happy: (←这是俺新学的Typora表达式~)​

二进制索引数,可以在O(lognlog_n)时间轻松搞定~~其存储思路如下:
【Educational Codeforces Round 80(div2)】E-Messenger Simulator (树状数组)
(百度百科偷的图,A为需要求前缀和的数列,C为树状数组的储存思路)

代码中,lowbit、add、sum函数均源于树状数组模板,在此不做赘述。

五、AC代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 7e5 + 10; //是m+n,maxn要开两倍!!!
 
int n, m, pos[MAXN], e[MAXN], maxx[MAXN], minx[MAXN];
 
int lowbit(int x) //x的二进制表达式中最低位的1所对应的值
{
    return x & (-x);
}
int add(int x, int v) //修改前缀和
{
    while(x < MAXN)
    {
        e[x] += v;
        x += lowbit(x);
    }
}
int sum(int x) //查询前缀和
{
    int re = 0;
    while(x > 0)
    {
        re += e[x];
        x -= lowbit(x);
    }
    return re;
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) //初始化
    {
        pos[i] = i + m; //在数列前腾出m个空格,所以位置暂时往后移m个
        add(pos[i], 1); //此位置上元素+1
        maxx[i] = i;  //初始化i的最大、最小位置
        minx[i] = i;
    }
    for (int i = 1; i <= m; i++)
    {
        int x;
        cin >> x;
        maxx[x] = max(maxx[x], sum(pos[x])); //更新位置最大值
        minx[x] = 1; //更新位置最小值
        add(pos[x], -1); //删除原位置上的数
        pos[x] = m - i + 1; //把x放到前面的空格中
        add(pos[x], 1); //新位置上元素+1
    }
    for (int i = 1; i <= n; i++)
    {
        maxx[i] = max(maxx[i], sum(pos[i])); 
        //操作中没有移动的数位置肯定越来越大,所以在所有结束后统一更新
        cout << minx[i] << ' ' << maxx[i] << endl;
    }
    return 0;
}
相关标签: 题解