Polycarp is a frequent user of the very popular messenger. He's chatting with his friends all the time. He has 𝑛 friends, numbered from 1 to 𝑛.

Recall that a permutation of size 𝑛 is an array of size 𝑛 such that each integer from 1 to 𝑛 occurs exactly once in this array.

So his recent chat list can be represented with a permutation 𝑝 of size 𝑛. 𝑝1 is the most recent friend Polycarp talked to, 𝑝2 is the second most recent and so on.

Initially, Polycarp's recent chat list 𝑝 looks like 1,2,…,𝑛 (in other words, it is an identity permutation).

After that he receives 𝑚 messages, the 𝑗-th message comes from the friend 𝑎𝑗. And that causes friend 𝑎𝑗 to move to the first position in a permutation, shifting everyone between the first position and the current position of 𝑎𝑗 by 1. Note that if the friend 𝑎𝑗 is in the first position already then nothing happens.

For example, let the recent chat list be 𝑝=[4,1,5,3,2]:

if he gets messaged by friend 3, then 𝑝 becomes [3,4,1,5,2];
if he gets messaged by friend 4, then 𝑝 doesn't change [4,1,5,3,2];
if he gets messaged by friend 2, then 𝑝 becomes [2,4,1,5,3].
For each friend consider all position he has been at in the beginning and after receiving each message. Polycarp wants to know what were the minimum and the maximum positions.

大致题意 📖

给你一个长度为 nn的数组aa, 开始时ai=ia_i = i
然后给你一个长度为mm 的操作序列bbbib_i 表示将在第ii步的时候,将

链接 🔗

「CodeForces 1288E」 Messenger Simulator

题解 ❓

因为最多挪动mm次,因此初始数组长度为n+mn+m ,这样每次都往前添加即可,不会整体移动数组
然后树状数组维护前面有多少个数即可

代码

ll tree[maxd<<2];
ll a[maxd<<1],pos[maxd<<1],l[maxd],r[maxd];
void add(ll x, ll v)
{
    for(;x<(maxd<<2); x += (x& (-x))) tree[x] +=v;
}
ll query(ll x)
{
    ll ans = 0ll;
    for(;x; x -= (x & (-x))) ans += tree[x];
    return ans;
}
int main()
{
//    __IN;__OUT;
    ll n,m;RLL2(n ,m);
    FOR(i,1,n)
    {
        pos[i] = i+m;
        add(i+m,1);
        l[i] = r[i] = query(i+m);
    }
    F(m)
    {
        ll x;RLL(x); l[x] = 1;
        r[x] = max(query(pos[x]),r[x]);
        add(pos[x],-1);
        pos[x] = m-i;
        add(pos[x],1);
    }
    FOR(i,1,n)
    {
        r[i] = max(query(pos[i]),r[i]);
        PLN2(l[i],r[i]);
    }
    return 0;
}