请求加强数据

这题本蒟蒻让每一个数输进来后用二分判断它所在的位置并一个一个交换。

虽然二分插入是严格 O(log n) ，但交换是 O((n-1)/2) 的。

总时间复杂度约等于 O(n^2) ,完全不符合堆优化的O(n \log n)。

可它却过了...

#include<bits/stdc++.h>
using namespace std;
int n,a[100001];
inline void zzy(int x,int i)
{
    a[i]=x;
    int l=1,r=i;
    while(l<r)
    {
        int mid=l+r>>1;
        if(a[mid]>a[i]) r=mid;
        else l=mid+1;
    }
    for(register int j=i;j>=l;j--) a[j]=a[j-1];
    a[l]=x;
}
inline int read()
{
    int x=0;
    char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9')
    {
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x;
}
signed main()
{
    n=read();
    for(register int x,i=1;i<=n;++i)
    {
        x=read();
        zzy(x,i);
        if(i&1) printf("%d\n",a[1+i>>1]);
    }
    return 0;
}

似乎跑得还挺快（评测记录）

可以用以下程序生成的数据hack：

#include<bits/stdc++.h>
using namespace std;
signed main()
{
    int n=100000;
    cout<<n<<endl;
    for(int i=n;i>=1;i--)
    {
        cout<<i<<endl;
        /*
        这样每次都可以将数值更新到队首。 
        */
    }
    return 0;
}

则我的算法在此数据下复杂度为：

=O((10^5/2)^2/2+10^5*17)

=O(10^5*21517)

=O(2151700000)

我们知道Luogu的评测机在1s内就多只能进行