Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

雁过留声——预处理+RMQ

Posted by fanhqme at 2009-11-28 18:47:40 on Problem 3419
首先,可以很快速的获得以每个数i为左端点,区间的最右断点R[i],
方法是注意到R[i]=min(R[i+1],min{j|A[j]=A[i]}-1)

接下来,就是求一个区间[l,r]内的最长相异序列,
观察此时以i为左端点的序列的最大长度f(i):
f(i)=min{R[i]-i+1,r-i+1},
如果只对付R[i]-i+1或r-i+1,那么还是比较容易的,但那个取最小却太烦了。
怎么办?
继续深思:
R[i]为单调的
那么...
存在x,使
for l<=i<=x f(i)=R[i]-i+1
for x<i<r f(i)=r-i+1
这是一个惊人的结论!换句话说,只要找到x,问题转化为一个
对R[i]-i+1的RMQ
那如何求x呢?
易知,x为最大的x使R[x]<r
呵呵,用二分查找x就可以了!

由于我比较懒,不想去默写rmq标准算法(或DC3)了,
就用传说中的“扩展树状数组”来实现。

关键代码:
struct BIT{
	int d[NMax];
	BIT(){for (int i=0;i<NMax;i++)d[i]=0;}
	void ins(int a,int x){
		for (d[a]=(d[a]<x?x:d[a]);a<N;a+=((a+1)&-(a+1)))
			if (d[a]<x)d[a]=x;
	}
	int ask(int b,int e){
		int ret;
		for (ret=0;e>=0 && e-((e+1)&-(e+1))+1>=b;e-=((e+1)&-(e+1)))
			if (ret<d[e])ret=d[e];
		return ret;
	}
}bit;
struct BIA{
	int d[NMax];
	BIA(){for (int i=0;i<NMax;i++)d[i]=0;}
	void ins(int a,int x){if (!a)return;
		for (d[a]=(d[a]<x?x:d[a]);a>0;a-=(a&-a))
			if (d[a]<x)d[a]=x;
	}
	int ask(int b,int e){if (!b)b++;if (b>e)return 0;
		int ret;
		for (ret=0;b<N && b+(b&-b)-1<=e;b+=(b&-b))
			if (ret<d[b])ret=d[b];
		return ret;
	}
}bia;
int Ask(int b,int e){
	int ret=bit.ask(b,e);
	int tmp=bia.ask(b,e);
	if (ret>tmp)return ret;
	return tmp;
}
        for (int i=0;i<2000001;i++)last[i]=N;
	R[N-1]=N-1;
	last[A[N-1]+1000000]=N-1;
	for (int i=N-2;i>=0;i--){
		R[i]=R[i+1];
		if (last[A[i]+1000000]-1<R[i])R[i]=last[A[i]+1000000]-1;
		last[A[i]+1000000]=i;
	}
	for (int i=0;i<N;i++){
		bit.ins(i,R[i]-i+1);
		bia.ins(i,R[i]-i+1);
	}


		if (R[b]>=e)printf("%d\n",e-b+1);
		else{
			//find that R[l]<e
			l=b;r=e;
			while (r-l>1){
				if (R[(r+l)>>1]<e)l=((r+l)>>1);
				else r=((r+l)>>1);
			}
			ret=Ask(b,l);
			if (ret<e-l)ret=e-l;
			printf("%d\n",ret);
		}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator