[COCI2006-2007#3] LISTA

· · 题解

原题链接

首先，发现找不到操作序列可以利用的性质，我们直接按照题意写一个双向链表，把最后的序列处理出来。

然后发现实际上就是要求一个最短的插入排序操作序列。

容易想到求出这个序列的最长上升子序列，对于最长上升子序列中的数，我们无需操作。对于其以外的数，我们找到它需要插入的位置即可。

其最优性显然：

那些不需要操作的元素一定满足单调递增，剩下的元素一定需要操作。

实现细节

设最长上升子序列中的最大元素为 k。

对于比 k 大的值，一个个插入在 k 后面即可。

对于比 k 小的值，开一个 set 来找到后继并将其插入 set 即可。

时间复杂度 O(n\log n)。

Code

#include<cstdio>
#include<set>
using namespace std;
const int SIZE=5e5+10;
inline int read()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=(x*10)+(ch^48),ch=getchar();
    return x;
}
inline char readch(){char ch=getchar();while(ch<'A'||ch>'B')ch=getchar();return ch;}
inline int max(int x,int y){return x>y?x:y;}
inline int lowbit(int x){return x&-x;}
int n,k,v[SIZE],pre[SIZE],suf[SIZE],dp[SIZE],t[SIZE],maxdp,maxp,top;
bool vst[SIZE];
char type;
set<int>bin;
struct answer{char type;int x,y;}ans[SIZE];
inline void modify(int x,int val){while(x<SIZE)t[x]=max(t[x],val),x+=lowbit(x);}
inline int query(int x){int res=0;while(x)res=max(res,t[x]),x-=lowbit(x);return res;}
int main()
{
    n=read(),k=read(),suf[0]=1,pre[n+1]=n;
    for(int i=1;i<=n;i++)pre[i]=i-1,suf[i]=i+1;
    for(int i=1,x,y,tmp;i<=k;i++)
    {
        type=readch(),x=read(),y=read();
        if(type=='A')pre[suf[x]]=pre[x],suf[pre[x]]=suf[x],pre[x]=pre[y],suf[x]=y,suf[pre[y]]=x,pre[y]=x;
        else pre[suf[x]]=pre[x],suf[pre[x]]=suf[x],pre[x]=y,suf[x]=suf[y],pre[suf[y]]=x,suf[y]=x;
    }
    for(int ths=suf[0],cnt=0;ths!=n+1;ths=suf[ths])v[++cnt]=ths;
    for(int i=1;i<=n;i++)dp[i]=query(v[i])+1,modify(v[i],dp[i]);
    for(int i=1;i<=n;i++)if(dp[i]>maxdp)maxdp=dp[i],maxp=i;
    for(int i=maxp,ths=maxdp;i;i--)if(dp[i]==maxdp)vst[v[i]]=true,bin.insert(v[i]),maxdp--;
    for(int i=v[maxp]-1;i;i--)if(!vst[i])ans[++top]={'A',i,*bin.lower_bound(i)},bin.insert(i);
    for(int i=v[maxp]+1;i<=n;i++)ans[++top]={'B',i,i-1};
    printf("%d\n",top);
    for(int i=1;i<=top;i++)putchar(ans[i].type),putchar(' '),printf("%d %d\n",ans[i].x,ans[i].y);
    return 0;
}