CodeForces - 1288E Messenger Simulator(树状数组)

题目

CodeForces - 1288E Messenger Simulator

思路

开二倍空间，数状数组左侧表示靠后面的数字，右侧为靠前的数字。

每次操作，都把数字往树状数组右侧丢，维护相对位置。

通过树状数组的区间查询作差，即可求得某个数字前面有多少个数字。

参考来源

https://blog.csdn.net/qq_45458915/article/details/103993107

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 6e5 + 10;
int c[maxn], mmin[maxn], mmax[maxn], pos[maxn];

int lowbit(int x)
{
    return x & (-x);
}

void update(int pos, int val)
{
    while(pos <= maxn)
    {
        c[pos] += val;
        pos += lowbit(pos);
    }
}

int query(int pos)
{
    int ans = 0;
    while(pos){
        ans += c[pos];
        pos -= lowbit(pos);
    }
    return ans;
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++)
    {
        pos[i] = n - i + 1;
        mmin[i] = mmax[i] = i;
        update(pos[i], 1);
    }
    for(int i = n + 1; i <= n + m; i++)
    {
        int x;
        scanf("%d", &x);
        mmin[x] = 1;
        mmax[x] = max(mmax[x], query(maxn) - query(pos[x] - 1) );
        update(pos[x], -1);
        pos[x] = i;
        update(pos[x], 1);
    }

    for(int i = 1; i <= n; i++)
    {
        mmax[i] = max(mmax[i], query(maxn) - query(pos[i] - 1) );
    }
    for(int i = 1; i <= n; i++)
    {
        printf("%d %d\n", mmin[i], mmax[i]);
    }
    return 0;
}