HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步 完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH不断地收集新的贝壳，因此，他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答。。。因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。
题解：
用last[i]记录上一个与i号贝壳相同的贝壳所在位置。对于一段区间[l,r]，求出其中满足last[i]<l的i的个数，即为答案。
用线段树记录last为0~n-1的贝壳的个数，因为每加入一个贝壳，只会改变last[0~n-1]中的一个，所以可以用可持久化线段树维护。
代码：
var i,j,k,n,m,cnt,xx,yy:longint; pre,root:array[1..50001]of longint; last:array[0..1000000]of longint; t:array[1..3000000,-2..2]of longint; function qq(x,l,r:longint):longint; var ll,rr:longint; begin if(t[x,1]=l)and(t[x,2]=r)then exit(t[x,0]); ll:=t[x,-1]; rr:=t[x,-2]; if r<=(t[x,1]+t[x,2])div 2 then exit(qq(ll,l,r)); if l>(t[x,1]+t[x,2])div 2 then exit(qq(rr,l,r)); exit(qq(ll,l,t[ll,2])+qq(rr,t[rr,1],r)); end; procedure build(l,r,x:longint); var k:longint; begin k:=cnt; t[k,1]:=l; t[k,2]:=r; if l=r then begin if l=x then t[k,0]:=1; exit; end; inc(cnt); t[k,-1]:=cnt; build(l,(l+r)div 2,x); inc(cnt); t[k,-2]:=cnt; build(((l+r)div 2)+1,r,x); t[k,0]:=t[t[k,-1],0]+t[t[k,-2],0]; end; procedure newtree(l,r,x,y:longint); var k:longint; begin k:=cnt; t[k,1]:=l; t[k,2]:=r; if l=r then begin t[k,0]:=t[y,0]; if l=x then inc(t[k,0]); exit; end; if x<=(l+r)div 2 then begin t[k,-2]:=t[y,-2]; inc(cnt); t[k,-1]:=cnt; newtree(l,(l+r)div 2,x,t[y,-1]); end else begin t[k,-1]:=t[y,-1]; inc(cnt); t[k,-2]:=cnt; newtree(((l+r)div 2)+1,r,x,t[y,-2]); end; t[k,0]:=t[t[k,-1],0]+t[t[k,-2],0]; end; begin readln(n); for i:=1 to n do begin read(j); pre[i]:=last[j]; last[j]:=i; end; root[1]:=1; cnt:=1; build(0,n,pre[1]); for i:=2 to n do begin inc(cnt); root[i]:=cnt; newtree(0,n,pre[i],root[i-1]); end; readln(m); for i:=1 to m do begin readln(j,k); if j=1 then xx:=0 else xx:=qq(root[j-1],0,j-1); if k=0 then yy:=0 else yy:=qq(root[k],0,j-1); writeln(yy-xx); end; end.
原文：http://www.cnblogs.com/GhostReach/p/6257174.html