E. Messenger Simulator

题意:Polycarp是一个频繁交流的受欢迎的送信人,他与朋友们一直交流,他有n个朋友,从1到n编号。一开始,n个朋友的编号是从1、2、3、4....n编号的,如果交流了3,那么3的位置就会移动到最前面,变成3、1、2、4...n。

分析:这道题目让我们求每个朋友的编号所能达到的最大位置和最小位置,只要他处于联系列表里,那么他的最小位置就是1,如果不处于联系列表中,那么它的最小位置就是它的初始位置,它的最大位置会受到其它数的影响后移,因此,如果要统计一个数的位置的化,我们可以用树状数组求它之前出现过的数的个数,这样,时间复杂度就会变成\(O(logn)\),那么怎么去模拟数字的移动呢?我们可以用树状数组统计一个数字之前出现数的个数,用1来表示有,0表示无,因为有m次操作,把一个数移动到前面的化,我们要提前开辟好m个空间,每次移动,都会把一个数的位置改变,所以我们需要开一个pos数组来记录一个数字的位置。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 300005;

//树状数组
int tr[N * 2];
int minpos[N], maxpos[N];
int a[N];
int pos[2 * N];

//n个朋友,m次联系
int n, m;
int bound;
int lowbit(int x)
{
    return x & (-x);
}

void add(int pos, int d)
{
    for (int i = pos; i <= bound; i += lowbit(i))
        tr[i] += d;
}

int query(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i))
        res += tr[i];
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);

    bound = n + m;

    //读入联系
    for (int i = 1; i <= m; ++i)
    {
        scanf("%d", &a[i]);
    }

    for (int i = 1; i <= n; ++i)
    {
        minpos[i] = i, maxpos[i] = i;
        add(i + m, 1);
        //i所在的位置
        pos[i] = i + m;
    }

    for (int i = 1; i <= m; ++i)
    {
        int now = a[i];
        minpos[now] = 1;
        maxpos[now] = max(maxpos[now], query(pos[now]));
        add(pos[now], -1);
        pos[now] = m - i + 1;
        add(pos[now], 1);
    }

    for (int i = 1; i <= n; ++i) maxpos[i] = max(maxpos[i], query(pos[i]));
    for (int i = 1; i <= n; ++i) printf("%d %d\n", minpos[i], maxpos[i]);

    return 0;
}


上一篇:cf1288e Messenger Simulator - 树状数组


下一篇:simulator相关