这题真是太神了！

考试的时候冲着四十分写了个$O(\frac{N^3logN}{32})$的制杖算法。

然后就狠狠的T掉了。如果没有充分的理解单调性和应用单调性就只有10分的傻逼分拿了。

首先考虑枚举两维，那么随着第二维的递增，第三维必定不上升，搞个指针瞎贪贪就是$O(N^2)$了（而我却SB的硬上了个二分）

然后考虑再优化掉一维，我们把值离散化后求出每个值在A,B,C的第一次出现位置，然后按在A的出现位置递减排序。

那么我们枚举A，这样就只用考虑枚举到的之前的情况了，因为枚举到的后面已经被覆盖了。

接着考虑如果一个点的B和C都同时小于另一个点，那么这个点显然是没有用的。

这样的话我们先考虑一个脑残点的算法，每次枚举A的时候把剩下的元素按B排序，这样的话每次把B放到单调队列里同时剔除没有用的元素，这样就必定得到一个B不递减，C不递增的单调队列。

而且这个单调队列里和枚举到的点相邻的点的B和C就构成了答案。

那么显然不能按照上面来，太暴力了。我们开一个set来维护单调队列，开一个multiset来维护答案即可。

//array//by Cydiater//2017.2.17#include <iostream>#include <queue>#include <map>#include <cstring>#include <string>#include <algorithm>#include <cstdio>#include <cstdlib>#include <iomanip>#include <cmath>#include <ctime>#include <bitset>#include <set>#include <vector>#include <complex>using namespace std;#define ll long long#define up(i,j,n)	for(int i=j;i<=n;i++)#define down(i,j,n)	for(int i=j;i>=n;i--)#define cmax(a,b)	a=max(a,b)#define cmin(a,b)	a=min(a,b)#define pii		pair<int,int>#define FILE		"array"const int MAXN=1e6+5;const int oo=1e7+5;inline int read(){	char ch=getchar();int x=0,f=1;	while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}	while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}	return x*f;}int N,A[MAXN],B[MAXN],C[MAXN],top=0,num[MAXN],ans=oo;struct Array{	int a,b,c;	Array(){a=b=c=oo-1;}}d[MAXN];multiset<int>ANS;set<pii>Q;namespace solution{	bool cmp(Array x,Array y){return x.a>y.a;}	void Insert(pii now){		set<pii>::iterator i,j,k;		cout<<(*ANS.begin())<<endl;		k=Q.lower_bound(now);		if(k->second>=now.second)return;		Q.insert(now);i=Q.find(now);j=i;j--;		ANS.erase(ANS.find(j->first+k->second));		ANS.insert(now.first+k->second);		ANS.insert(j->first+now.second);		//cout<<(*ANS.begin())<<endl;		while(j->second<=now.second){			i=j;j--;			ANS.erase(ANS.find(j->first+i->second));			ANS.erase(ANS.find(i->first+now.second));			Q.erase(i);			ANS.insert(j->first+now.second);			//cout<<(*ANS.begin())<<endl;		}	}	void Prepare(){		N=read();		up(i,1,N)num[++top]=A[i]=read();		up(i,1,N)num[++top]=B[i]=read();		up(i,1,N)num[++top]=C[i]=read();		sort(num+1,num+top+1);		top=unique(num+1,num+top+1)-(num+1);		up(i,1,N)A[i]=lower_bound(num+1,num+top+1,A[i])-num;		up(i,1,N)B[i]=lower_bound(num+1,num+top+1,B[i])-num;		up(i,1,N)C[i]=lower_bound(num+1,num+top+1,C[i])-num;		down(i,N,1)d[A[i]].a=i;		down(i,N,1)d[B[i]].b=i;		down(i,N,1)d[C[i]].c=i;		sort(d+1,d+top+1,cmp);	}	void Solve(){		Q.insert(make_pair(0,oo));		Q.insert(make_pair(oo,0));		ANS.insert(0);		cmin(ans,d[1].a);		d[top+1].a=0;		up(i,1,top){			Insert(make_pair(d[i].b,d[i].c));			//cout<<d[i+1].a<<‘ ‘<<(*ANS.begin())<<endl;			cmin(ans,d[i+1].a+(*ANS.begin()));		}		cout<<ans<<endl;	}}int main(){	freopen(FILE".in","r",stdin);	//freopen(FILE".out","w",stdout);	using namespace solution;	Prepare();	Solve();	return 0;}

[省选模拟]array