题目简介：每次在数组中插入数字，如果该位置已经有了元素，就把后面的所有元素一次往后移动

分析： 一开始我用块状链表搞，但是因为每个位置有一个初始值0，因此第一次插入的时候会有覆盖操作

我就在想，可不可以第一次插入的时候先删除，后插入 但是这样会出现一个问题： 如果在一个位置插入了过多元素，后边的位置就会有元素了，这样在后面的位置插入的时候就不用删除了 于是我又开了一个数组，表示每个位置插入了多少元素，插入元素个数会影响之后的位置 但是这样产生了另一个问题：两个相隔不远的位置插入的元素元素过多，那么互相就会影响（反正后果就是WA。。。） 这道题的正解是：并查集+块状链表

#include <cstdio>
#include <algorithm>
#include <cstring>
#define MX 666
using namespace std;

struct node
{
    int s[888], suf, pre, sz;
}P[666];

int n, m, cnt, ans, que[333333], f[333333];

void get (int &x)
{
    char c = getchar(); x = 0;
    while (c < '0' || c > '9') c = getchar();
    while (c <= '9' && c >= '0') x = x*10+c-48, c = getchar();
}

void put (int x)
{
    if (!x) putchar ('0');
    char s[15]; int len = 0;
    while (x) s[++len] = x%10+48, x /= 10;
    while (len) putchar (s[len--]);
    putchar (' ');
}

void Initialize()
{
    scanf ("%d %d", &n, &m);
    cnt = 0, ans = m; 
    for (int i = 1; i <= max(m+n,m*2); i++) f[i] = i;
    while (m > MX) m -= MX, cnt++, P[cnt].pre = cnt-1, P[cnt-1].suf = cnt, P[cnt].sz = MX;
    cnt++; P[cnt].pre = cnt-1, P[cnt-1].suf = cnt, P[cnt].sz = m;
}

void find (int pos, int &pce, int &num)
{
    int sum = 0; pce = 1;
    while (sum + P[pce].sz < pos && P[pce].suf) sum += P[pce].sz, pce = P[pce].suf;
    num = pos - sum;
}

int Find (int x) {return f[x] = x == f[x] ? x : Find (f[x]);}

void Change (int pos, int who)
{
    int pce, num; find (pos, pce, num);
    P[pce].s[num] = who;
}

void Delete (int pos)
{
    int pce, num; find (pos, pce, num);
    for (int i = num; i <= P[pce].sz; i++) P[pce].s[i] = P[pce].s[i+1];
    P[pce].sz--;
}

void Insert (int pos, int who)
{
    int pce, num; find (pos, pce, num);
    if (P[pce].sz == MX)
    {
        cnt++;
        P[cnt].pre = pce, P[cnt].suf = P[pce].suf, P[cnt].sz = P[pce].sz-num+1;
        P[P[pce].suf].pre = cnt, P[pce].suf = cnt;
        for (int i = num; i <= P[pce].sz; i++) P[cnt].s[i-num+1] = P[pce].s[i];
        P[pce].sz = num - 1;
        if (P[pce].sz > P[cnt].sz) num = 1, pce = cnt;
    }
    for (int i = P[pce].sz; i >= num; i--) P[pce].s[i+1] = P[pce].s[i];
    P[pce].s[num] = who, P[pce].sz++;
}

void Print()
{
    int t = 1, tn = n;
    while (t && tn)
    {
        for (int i = 1; i <= P[t].sz && tn; i++) 
        {
            que[++que[0]] = P[t].s[i];
            if (que[que[0]]) tn--;
        }
        t = P[t].suf;
    }
    printf ("%d\n", que[0]);
    for (int i = 1; i < que[0]; i++) put (que[i]);
    printf ("%d\n", que[que[0]]);
}

void Work()
{
    for (int i = 1; i <= n; i++)
    {
        int cmd; get (cmd);
        int pos = Find (cmd);
        if (pos == cmd) Change(pos, i); 
        else 
        {
            if (pos <= ans) Delete (pos); else ans++;
            Insert (cmd, i);
        }
        f[pos] = f[pos+1];
    }
    Print();
}

int main()
{
    Initialize();
    Work();
    return 0;
}