Jzoj1310 生日礼物

生日礼物"/>

Jzoj1310 生日礼物

Alice收到一份来自美国的生日礼物：一个崭新的双链火车，火车有N节车厢，依次编号为1到N，你可以在该玩具上进行两种操作：
　　A：把X号车厢移到Y号车厢前面；
　　B：把X号车厢移到Y号车厢后面。
　　Alice收到礼物后很兴奋，玩了数小时，记录下每一步的操作以至于他能还原到最初的状态（从左到右，按照1到N的顺序排列）。

　　当他要进行还原的时候，Alice发现无法进行反操作恢复原貌，只能请你帮忙写一个程序计算出最少需要多少次操作才能回到原始状态。

先模拟，这个是双向链表的工作，让后将移动过后的序列取出来，在序列上面作LIS，那么答案就是n-LIS

为什么？很简单LIS上的数不用动其他的都一次移动搞定就好了

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 500010
using namespace std;
char c[3]; int inf=0x7f7f7f7f;
int l[N],r[N],s[N],f[N],n,m,A=0; 
int main(){scanf("%d%d",&n,&m);for(int i=0;i<=n;++i) l[i]=i-1,r[i]=i+1;l[0]=n; r[n]=0; for(int a,b,i=0;i<m;++i){scanf("%s%d%d",c,&a,&b);if(*c=='A'){l[r[a]]=l[a]; r[l[a]]=r[a];l[a]=l[b]; r[l[b]]=a; l[b]=a; r[a]=b;} else {l[r[a]]=l[a]; r[l[a]]=r[a];r[a]=r[b]; l[r[b]]=a; r[b]=a; l[a]=b;}}for(int i=r[0],j=0;i;i=r[i]) s[++j]=i;memset(f,127,sizeof f);for(int i=1;i<=n;++i) *lower_bound(f,f+n,s[i])=s[i];printf("%d\n",n-(lower_bound(f,f+n,inf)-f));
}