呃。。。由于cin的速度。。我又挂了。。

你们可以看看用scanf和cin两次不同的结果，测评记录是78861和78862.。。。

怎么这么多大牛都喜欢用cin，我个人比较喜欢scanf。。

习惯难改啊。。。。

不过你比我好，昨天晚上242交了4次3次挂蛋，晕，一看快排写错了。。。

242 需要快排吗？。。。。

不解

要二分查找不是得先排个序么？

额。。。。。。。。。。。。。。。。。。

试问 LIS 问题里会出现排序吗。。。

这一题的优化基本可以照搬 LIS。。。

其实未必是 cin 慢

是 Windows 和 FAT32/NTFS 慢

我在 ReiserFS 3.6 上 cin 一千万个数才用6s

这个题目最大就20W 个数，基本可以忽略不计

大概做法不一样，我是这样实现的，记得以前做到过这样的题目：

已知艾尔里斯和弟弟艾尔里亚的基因基本相同，由于基因表达起来不方便，所以就用n个数字来表示。(因为至今共发现100000种基因，所以每个数字都<=100000)兄弟之间的基因个数是相同的，就是说他们都有n个数字。且对于每个人，这n个数字互不相同。现在要求兄弟之间基因的最长公共部分。可以不连续。”

Input 文件LCS.IN第1行，为n(1<=n<=100000) 下面2行，每行n个数字，表示了一个人的所有基因。

Output文件LCS.OUT一行，为他们两人基因的最长公共部分的长度。

=========================================

这题我记得那时候我读入数据以后快排了，这里我就把以前写的程序从脑子里copy了一遍稍微改了下。。

8F：额。。这题和第二题不是一模一样么。。。。

所以说我直接把以前写的copy了：

var n,i,j:longint；

a,b,numa,numb:array[1..100000]of longint；

procedure qsrta(h,t:longint)；

var i,j,k,x,y:longint；

begin

if h>=t then exit；

k:=random(t-h+1)+h；

x:=a[k]；a[k]:=a[h]；a[h]:=x；

y:=numa[k]；numa[k]:=numa[h]；numa[h]:=y；

i:=h；j:=t；

while i<j do begin

while (i<j) and (a[j]>x) do dec(j)；

if i<j then begin a[i]:=a[j]；numa[i]:=numa[j]；inc(i)；end；

while (i<j) and (a[i]<x) do inc(i)；

if i<j then begin a[j]:=a[i]；numa[j]:=numa[i]；dec(j)；end；

end；

a[i]:=x；numa[i]:=y；

qsrta(h,i-1)；qsrta(i+1,t)；

end；

procedure qsrtb(h,t:longint)；

var i,j,k,x,y:longint；

begin

if h>=t then exit；

k:=random(t-h+1)+h；

x:=b[k]；b[k]:=b[h]；b[h]:=x；

y:=numb[k]；numb[k]:=numb[h]；numb[h]:=y；

i:=h；j:=t；

while i<j do begin

while (i<j) and (b[j]>x) do dec(j)；

if i<j then begin b[i]:=b[j]；numb[i]:=numb[j]；inc(i)；end；

while (i<j) and (b[i]<x) do inc(i)；

if i<j then begin b[j]:=b[i]；numb[j]:=numb[i]；dec(j)；end；

end；

b[i]:=x；numb[i]:=y；

qsrtb(h,i-1)；qsrtb(i+1,t)；

end；

procedure qsrtnumab(h,t:longint)；

var i,j,k,x,y:longint；

begin

if h>=t then exit；

k:=random(t-h+1)+h；

x:=numa[k]；numa[k]:=numa[h]；numa[h]:=x；

y:=numb[k]；numb[k]:=numb[h]；numb[h]:=y；

i:=h；j:=t；

while i<j do begin

while (i<j) and (numa[j]>x) do dec(j)；

if i<j then begin numa[i]:=numa[j]；numb[i]:=numb[j]；inc(i)；end；

while (i<j) and (numa[i]<x) do inc(i)；

if i<j then begin numa[j]:=numa[i]；numb[j]:=numb[i]；dec(j)；end；

end；

numa[i]:=x；numb[i]:=y；

qsrtnumab(h,i-1)；qsrtnumab(i+1,t)；

end；

function bfind(h,t,x:longint):longint；

var m:longint；

begin

if h>t then bfind:=h

else begin

m:=(h+t) div 2；

if x<numa[m] then bfind:=bfind(h,m-1,x)

else bfind:=bfind(m+1,t,x)；

end；

end；

begin

randomize；

read(n)；

for i:=1 to n do read(a[i])；

for i:=1 to n do read(b[i])；

for i:=1 to n do begin numa[i]:=i；numb[i]:=i；end；

qsrta(1,n)；

qsrtb(1,n)；

qsrtnumab(1,n)；

for i:=1 to n do numa[i]:=maxlongint；

for i:=1 to n do begin

j:=bfind(1,n,numb[i])；

numa[j]:=numb[i]；

end；

j:=bfind(1,n,maxlongint-1)；

write(n-j+1)；

end.