BZOJ2221:[Jsoi2009]面试的考验 单调性+随机数据

思路:

宋文杰的题解很详细.

一开始每个点30s,结果在OJ上一共30s...

也就是说原来莫队是能过的,结果我无悬念TLE.

莫队怎么做我就不说了.(貌似官方正解就是莫队...)

莫队很暴力,因为没有利用一个题目中的性质:就是数据随机生成!

询问随不随机意义是不大的.

但是如果询问很特殊,我们就可以用科学的方法去处理:

(1)任意两个区间不互相包含.这种情况我们将区间随便排个序就能发现总移动次数是\(O(n)\)的.

(2)任意两个区间要么互相包含,要么不相交.这样就会形成一棵树.我们利用启发式合并,插入次数就为\(O(nlogn)\).

但是随机数据显然没有这种性质.

那么唯一可能有比较优秀的性质的就是随机数列了.

考虑一种朴素算法:

将所有询问离线按照右端点从小到大排序.

从前向后依次加入右端点,令\(f_i\)表示当前以\(i\)为起点的后缀的答案,那么朴素来看,如果当前加入的是\(n\),那么\(f_1-f_{n-1}\)都需要更新.

但是有很多冗余的更新.

例如我们考虑所有大于\(a_n\)的数,不妨令\(a_i,a_j>a_n,a_i>a_j,i<j\),那么如果我们能够维护一个后缀的答案,我们就只需更新\(f_j\)就可以了.

于是我们发现了某些单调性.

我们利用数据结构维护后缀的答案,那么只需更新一些点就行了.

那么我们的任务就是找到,对于\(n\)之前的数,一个均\(>a_n\)的递减序列,一个均\(<a_n\)的递增序列.然后我们就拿序列中的东西暴力更新答案.

然而由于是随机数据,序列中的元素个数是\(O(logn)\)级别的.

这样总时间复杂度就是\(O(qlogn+nlog^2n)\).

具体去看宋文杰的题解.

(另外此题要求结果\(>0\) 23333)

#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

#define N 100010
#define Q 100010
int n,q,a[N];

struct Interval{
	int l,r,lab;
	bool operator<(const Interval&B)const{return r<B.r;}
}S[N];
int re[Q];

inline void mini(int&x,int y){if(x>y)x=y;}
struct SegmentTree{
	int A[262144],M;
	inline void Init(int _siz){
		for(M=1;M<(_siz+2);M<<=1);
		memset(A,0x3f,sizeof A);
	}
	inline void modify(int x,int d){
		for(x+=M;x;x>>=1)mini(A[x],d);
	}
	inline int query(int tl,int tr){
		int re=~0U>>1;
		for(tl+=M-1,tr+=M+1;tl^tr^1;tl>>=1,tr>>=1){
			if(~tl&1)mini(re,A[tl^1]);
			if(tr&1)mini(re,A[tr^1]);
		}
		return re;
	}
}Seg;

int preless[N],premore[N],small[N][30],big[N][30],stk[N],top;

int main(){
	//freopen("tt.in","r",stdin);
	scanf("%d%d",&n,&q);
	register int i,j,k;
	
	for(i=1;i<=n;++i)scanf("%d",&a[i]);
	
	for(i=1;i<=q;++i)
		scanf("%d%d",&S[i].l,&S[i].r),S[i].lab=i;
	sort(S+1,S+q+1);
	
	Seg.Init(n);
	
	for(i=1;i<=n;++i){
		while(top&&a[stk[top]]>=a[i])--top;
		preless[i]=stk[top];
		stk[++top]=i;
	}
	top=0;
	for(i=1;i<=n;++i){
		while(top&&a[stk[top]]<=a[i])--top;
		premore[i]=stk[top];
		stk[++top]=i;
	}
	
	for(i=1;i<=n;++i){
		if(premore[i]){
			big[i][++big[i][0]]=premore[i];
			j=big[i][1];
			while(1){
				bool find=0;
				for(k=1;k<=small[j][0];++k)if(a[small[j][k]]>a[i]){find=1;break;}
				if(find)big[i][++big[i][0]]=(j=small[j][k]);else break;
			}
		}
		if(preless[i]){
			small[i][++small[i][0]]=preless[i];
			j=small[i][1];
			while(1){
				bool find=0;
				for(k=1;k<=big[j][0];++k)if(a[big[j][k]]<a[i]){find=1;break;}
				if(find)small[i][++small[i][0]]=(j=big[j][k]);else break;
			}
		}
	}
	j=1;
	for(i=1;i<=n;++i){
		for(k=1;k<=small[i][0];++k)Seg.modify(small[i][k],a[i]-a[small[i][k]]);
		for(k=1;k<=big[i][0];++k)Seg.modify(big[i][k],a[big[i][k]]-a[i]);
		
		for(;j<=q&&S[j].r==i;++j)re[S[j].lab]=Seg.query(S[j].l,S[j].r);
		
	}
	
	for(i=1;i<=q;++i)printf("%d\n",re[i]);
	
	return 0;
}