本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-18 13:33:43

这道题我记得原题是图灵杯（CF 也有），并且洛谷上有，这道题应该是个 well-known。
当时爆零，没补题
这次奋战 4h（晚了 0.5h 参赛，算到赛后 0.5h）通过了这道题，写题解记录一下。

为了迎接寒冬，Farer John 准备了 堆木材用来修补他牛圈的围栏！其中第 块木材的长度为 $a_i$。虽然木材的长度参差不齐，但是 Farer John 不想把围栏修补坑坑洼洼的形状，而且要修建的围栏有两条。因此 Farer John 决定把这 堆木材分成两排，每排的木材的长度依次能构成一个公差非负的的等差序列。但是堆积的木材实在是太多了！Farer John 感到无从下手，于是奶牛 Bassie 邀请了你来制订方案，或是判断不存在合法的方案。

设 $1$ 号点在第一个等差序列，枚举第一个等差数列的第二个点。

由此计算出第一个等差数列的公差 $d$。

然后不断跳转到第 $3$ 个点，第 $4$ 个点，$\cdots$

怎么跳转到下一个符合要求的点是个关键。

假设当前点 $a_i$，那么下一点应该选择 $a_j = a_i +d$，使得 $j \gt i$
也就是说，我们需要对于 $1$ 到 $n$ 每个点，维护从这个点开始，每种可能的权值下一次出现的位置。

容易想到 $O(n^2)$ 做法，即从第 $n$ 个到第 $1$ 个倒叙枚举，转移显然。

但是显然过不去，于是想到主席树。可以发现每个点 $i$ 都保存一个 $i$ 开始的线段树版本就可以，然后这个问题解决了。

那么第二序列如何判断呢？

可以预处理出每个点向前（延伸到 $j \le i$） 最多延伸多少。

然后在第一序列跳转过程中分情况讨论，判断第二序列合法性。

另外我们每跳转到一个点，都判断如果第一序列以此结尾，那么是否合法。
只要我们找出一个方案合法，那么立刻退出，如果当前方案一旦判断不合法，也立刻退出。

那么复杂度看上去似乎不对啊。

简单推导可得复杂度是 $\log n $ 乘 $1$ 序列跳转总次数。

我能想到的让跳转总次数最长的构造方式：$1,2,3,4,5,6,7,8,9,\cdots$
这样跳转总次数是 $O(n+\frac{n}{2}+\frac{n}{4}+\cdots) = O(2n) = O(n)$

总复杂度 $O(n \log n)$

如果错了，请大佬们指出。

\/\/ By __vector__ (luoguid = 507348) , real name = liumonong
#include <bits\/stdc++.h>
using namespace std;
const int inf=INT_MAX;
const int maxn=1e5+5;
int n;
int a[maxn];
struct Node{
    int ls,rs,l,r,val;
};
struct HJT{
    Node node[maxn*25];
    int nodecnt=0;
    int rt[maxn];
    inline int ls(int pos){
        return node[pos].ls;
    }
    inline int rs(int pos){
        return node[pos].rs;
    }
    int build(int l,int r){
        int now=++nodecnt;
        node[now].l=l,node[now].r=r;
        if(l==r){
            node[now].val=inf;
            return now;
        }
        int mid=(l+r)\/2;
        node[now].ls=build(l,mid);
        node[now].rs=build(mid+1,r);
        return now;
    }
    int chg(int oldnode,int x,int val){
        int nwnode=++nodecnt;
        node[nwnode]=node[oldnode];
        if(node[oldnode].l==node[oldnode].r){
            node[nwnode].val=val;
            return nwnode;
        }
        int mid=(node[oldnode].l+node[oldnode].r)\/2;
        if(mid>=x)node[nwnode].ls=chg(ls(oldnode),x,val);
        else node[nwnode].rs=chg(rs(oldnode),x,val);
        return nwnode;
    }
    int query(int pos,int x){
        if(node[pos].l==node[pos].r){
            return node[pos].val;
        }
        int mid=(node[pos].l+node[pos].r)\/2;
        if(mid>=x)return query(ls(pos),x);
        return query(rs(pos),x);
    }
}hjt;
struct Disc{
    int disc[maxn];
    int top;
    void init(int* a,int n){
        for(int i=1;i<=n;i++){
            disc[i]=a[i];
        }
        sort(disc+1,disc+n+1);
        top=unique(disc+1,disc+n+1)-disc-1;
    }
    int rank(int val){
        int pos=lower_bound(disc+1,disc+top+1,val)-disc;
        if(pos==top+1)return -1;
        if(disc[pos]!=val)return -1;
        return pos;
    }
    int rktoval(int rk){
        return disc[rk];
    }
}disc;
int len[maxn];
bool tag[maxn];
int main(){
   \/\/ freopen("fence.in","r",stdin);
    \/\/freopen("fence.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    if(n==2){
        printf("1\n%d\n1\n%d\n",a[1],a[2]);
        return 0;
    }
    sort(a+1,a+n+1);
    disc.init(a,n);
    for(int i=1;i<=n;i++){
 \/\/       printf("i = %d val = %d\n",i,a[i]);
        a[i]=disc.rank(a[i]);
    }
    hjt.rt[n]=hjt.build(1,n);
    for(int i=n-1;i>=1;i--){
        hjt.rt[i]=hjt.chg(hjt.rt[i+1],a[i+1],i+1);
    }
    for(int i=1;i<=n;i++){
        if(i==1){
            len[i]=1;
        }else{
            if(i==2){
                len[i]=2;
            }else{
                len[i]=2;
                if(disc.rktoval(a[i])-disc.rktoval(a[i-1])==disc.rktoval(a[i-1])-disc.rktoval(a[i-2])){
                    len[i]=len[i-1]+1;
                }
            }
        }
    }
    for(int sec=2;sec<=n;sec++){
          \/\/  printf("sec2 = %d\n",sec);
        if(sec-2>=1){
            if(len[sec-1]<sec-2){
                break;
            }
        }
        bool ok=1;
        int now=sec;
        int d=disc.rktoval(a[sec])-disc.rktoval(a[1]);\/\/ 1 序列公差
        int d2=-1;\/\/ 2 序列公差
        if(sec>=4)d2=disc.rktoval(a[sec-1])-disc.rktoval(a[sec-2]);
        int lst2=-1;
        if(sec>=3)lst2=a[sec-1];\/\/ 2 序列目前遍历到的最后一个数

        vector<int> seq1;
       \/\/ printf("i = %d\n",sec);
        seq1.emplace_back(1);
        while(now<n){

           \/\/ printf("now = %d d = %d\n",now,d);
            seq1.emplace_back(now);
            int _new=disc.rank(disc.rktoval(a[now])+d);
            if(_new==-1||hjt.query(hjt.rt[now],_new)==inf){
             \/\/   printf("fail can't find %d + %d = %d\n",disc.rktoval(a[now]),d,disc.rktoval(a[now])+d);
                \/\/ 不存在 _new，所以 now 是最后一个
                \/\/ 应该判断之后是否合法
                if(len[n]<n-(now+1)+1)ok=0;
                if(now==n-1){
                    \/\/ 2 序列最后一个单位只有一个数
                    if(d2!=-1){\/\/ 2 序列存在公差
                        if(lst2!=-1&&disc.rktoval(a[n])-disc.rktoval(lst2)!=d2){
                            ok=0;
                        }
                    }
                }else{
                    if(d2==-1){\/\/ 没有公差，先设定
                        d2=disc.rktoval(a[n])-disc.rktoval(a[n-1]);
                    }else{
                        if(disc.rktoval(a[n])-disc.rktoval(a[n-1])!=d2){
                            ok=0;\/\/ 判断最后一段是否满足公差
                        }
                    }
                    if(lst2!=-1&&disc.rktoval(a[now+1])-disc.rktoval(lst2)!=d2){
                        ok=0;\/\/ 连接处是否满足公差
                    }
                }
                break;
            }
            if(1){
                \/\/ 假设从 now 截止
                int oldd2=d2;
                bool ok2=1;
                if(len[n]<n-(now+1)+1)ok2=0;
                if(now==n-1){
                    \/\/ 2 序列最后一个单位只有一个数
                    if(d2!=-1){\/\/ 2 序列存在公差
                        if(lst2!=-1&&disc.rktoval(a[n])-disc.rktoval(lst2)!=d2){
                            ok2=0;
                        }
                    }
                }else{
                    if(d2==-1){\/\/ 没有公差，先设定
                        d2=disc.rktoval(a[n])-disc.rktoval(a[n-1]);
                    }else{
                        if(disc.rktoval(a[n])-disc.rktoval(a[n-1])!=d2){
                            ok2=0;\/\/ 判断最后一段是否满足公差
                        }
                    }
                    if(lst2!=-1&&disc.rktoval(a[now+1])-disc.rktoval(lst2)!=d2){
                        ok2=0;\/\/ 连接处是否满足公差
                    }
                }
                if(ok2){
              \/\/      printf("stop = %d\n",now);
               \/\/     printf("stop  = %d\n",now);
                    break;
                }else{
                \/\/    printf("failstopping = %d\n",now);
                    d2=oldd2;
                }
            }
            \/\/ 记得更新 lst2

                _new=hjt.query(hjt.rt[now],_new);
               \/\/ printf("_new = %d\n",_new);
                if(_new-now-1==1){
                    \/\/ 中间一个数
                    if(lst2==-1){
                        lst2=a[now+1];
                        now=_new;
                        continue;
                    }
                    if(d2==-1){
                        \/\/ 2没有公差，建立
                        d2=disc.rktoval(a[now+1])-disc.rktoval(lst2);
                    }else{
                        if(lst2!=-1&&disc.rktoval(a[now+1])-disc.rktoval(lst2)!=d2){
                            ok=0;
                            break;
                        }
                    }
                }else if(_new-now-1>=2){
                    \/\/ 中间超过两个数
                    if(len[_new-1]<_new-now-1)ok=0;
                    if(d2==-1){
                        d2=disc.rktoval(a[_new-1])-disc.rktoval(a[_new-2]);
                    }else{
                        if(disc.rktoval(a[_new-1])-disc.rktoval(a[_new-2])!=d2){
                            ok=0;
                        }
                    }
                    if(lst2!=-1&&disc.rktoval(a[now+1])-disc.rktoval(lst2)!=d2){
                        ok=0;
                    }
                }
                if(_new-now-1>=1)lst2=a[_new-1];
                now=_new;
                if(!ok)break;

        }
        if(ok){
            seq1.emplace_back(now);
        \/\/    printf("seq1.size() = %d\n",seq1.size());
            int cnt1=1;
            tag[seq1[0]]=1;
            for(int i=1;i<seq1.size();i++){
                if(seq1[i]!=seq1[i-1])tag[seq1[i]]=1,cnt1++;
            }
            printf("%d\n",cnt1);
            for(int i=1;i<=n;i++){
                if(tag[i])printf("%d ",disc.rktoval(a[i]));
            }
            printf("\n");
            printf("%d\n",n-cnt1);
            for(int i=1;i<=n;i++){
                if(!tag[i])printf("%d ",disc.rktoval(a[i]));
            }
            return 0;
        }
    }
    puts("-1");
    return 0;
}