B. Preparing for Merge Sort

\(考虑的时候，千万不能按照题目意思一组一组去模拟\)

\(要发现每组的最后一个数一定大于下一组的最后一个数\)

\(那我们可以把a中的数一个一个填充到vec中\)

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+9;
vector<int>vec[maxn];
int a[maxn],cnt=1,n;
int find(int x)
{
    int l=1,r=cnt+1,mid,flag=0;//实际上取不到cnt+1,边界问题 
    while(r>l)
    {
        mid=(l+r)/2;
        int len=vec[mid].size();
        if(len!=0&&vec[mid][len-1]<x)    flag=1,r=mid;
        else    l=mid+1;
    }
    if(flag==0) return -1;
    else    return r;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)    cin>>a[i];
    vec[1].push_back(a[1]);
    for(int i=2;i<=n;i++)
    {
        int res=find(a[i]);
        if(res==-1) vec[++cnt].push_back(a[i]);
        else    vec[res].push_back(a[i]);
    }
    for(int i=1;i<=cnt;i++)
    {
        for(int j=0;j<vec[i].size();j++)
            cout<<vec[i][j]<<" ";
        cout<<endl;
    }
}