题解 CF1288E 【Messenger Simulator】

YLWang · 2020-01-16 12:08:50 · 题解

正解是个很有创造力的做法，感觉自己get了不少。两个月没碰OI水平果然大幅度下降了。

首先我们一看，这是个把数往数组开头怼的序列问题。因为移动数组中元素是个非常麻烦的事情，我们在数组的左端添加 m 个虚点，用来存放移动过去的东西。

我们把实际上没有放数的点设为0，实际上放了数的点设为1。

这样我们只需要查询在一个点前面有多少个1就可以确定它在原数组中的位置。容易发现可以使用树状数组或者线段树维护。

因为最小值只可能是1或者这个数原来的位置，最大值只可能在一个数移动之前或者在完成所有操作后出现，所以我们只需要m + n次查询。（每次操作查询一次，最后查询n次）

然后我们就很愉快地解决了这个问题。

代码非常好写，自认为思路比楼下小哥清晰不少。

const int MAXN = 600005;
int n, m, mini[MAXN], maxi[MAXN], c[MAXN], pos[MAXN];
void update(int x, int v) {for(; x <= n+m; x += (x&-x)) c[x] += v;}
int query(int x) {int ans = 0;for(; x; x -= (x&-x)) ans += c[x];return ans;}
signed main()
{
    cin >> n >> m;
    For(i, 1, n) mini[i] = maxi[i] = i, pos[i] = m+i, update(pos[i], 1);
    int now = m;
    For(k, 1, m) {
        int i = read(); mini[i] = 1;
        ckmax(maxi[i], query(pos[i]));
        update(pos[i], -1); 
        pos[i] = now--;
        update(pos[i], 1);
    }
    For(i, 1, n) ckmax(maxi[i], query(pos[i]));
    For(i, 1, n) printf("%d %d\n", mini[i], maxi[i]);
    return 0;
}