记录编号	130313	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队 2012] 几乎平均数	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	31.414 s
提交时间	2014-10-21 22:43:50	内存使用	982.70 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
typedef long long LL;
const LL INF=(LL)1e12;
const int SIZEN=100010,SIZEK=320;
LL gcd(LL a,LL b){return !b?a:gcd(b,a%b);}
class Frac{
public:
	LL p,q;
};
inline Frac getFrac(LL a,LL b){
	LL g=gcd(a,b);
	a/=g,b/=g;
	if(b<0) a*=-1,b*=-1;
	return (Frac){a,b};
}
void print(Frac a){
	printf("%lld/%lld",a.p,a.q);
}
inline bool operator < (Frac a,Frac b){return (a.p+0.0)*(b.q+0.0)<(b.p+0.0)*(a.q+0.0);}
inline Frac operator + (Frac a,Frac b){return getFrac(a.p*b.q+b.p*a.q,a.q*b.q);}
inline Frac operator - (Frac a,Frac b){return getFrac(a.p*b.q-b.p*a.q,a.q*b.q);}
inline Frac operator * (Frac a,Frac b){return getFrac(a.p*b.p,a.q*b.q);}
class Point{
public:
	double x,y;
	void print(void){cout<<"("<<x<<","<<y<<")";}
};
void print(Point p){cout<<"("<<p.x<<","<<p.y<<")";}
inline Point operator - (Point a,Point b){return (Point){a.x-b.x,a.y-b.y};}
inline double crp(Point a,Point b){
	return a.x*b.y-b.x*a.y;
}
int N,Q,SZ,K;
LL X[SIZEN]={0},S[SIZEN]={0};
int head[SIZEN]={0},tail[SIZEN]={0},belong[SIZEN]={0};
Frac f[SIZEK][SIZEN],g[SIZEK][SIZEN];//f[i][j]:L=head[i],R=j的查询答案;g[i][j]:L=j,R=tail[i]的查询的答案
class Convex_Hull_L_Active{
public:
	//凸包是"上凸"的
	Point H[SIZEN];
	int n;//0~n-1,从右向左
	inline void clear(void){n=0;}
	inline void print(void){for(int i=n-1;i>=0;i--){H[i].print();cout<<" ";}cout<<endl;}
	inline void add(Point p){//p的横坐标小于H中的点
		while(n>=2&&crp(H[n-1]-p,H[n-2]-H[n-1])>=0) n--;
		H[n++]=p;
	}
	inline Frac calc(Point p){//p的横坐标小于H中的点,计算p和凸包上某点形成的最大斜率
		int l=0,r=n-1,mid;
		while(l<r){
			mid=(l+r)/2;
			if(crp(H[mid+1]-p,H[mid]-H[mid+1])>=0) r=mid;
			else l=mid+1;
		}
		return getFrac(H[l].y-p.y,H[l].x-p.x);
	}
};
class Convex_Hull_R_Active{//"右端活跃"的凸包
public:
	//凸包是"下凸"的
	Point H[SIZEN];
	int n;//0~n-1,从左到右
	inline void clear(void){n=0;}
	inline void print(void){for(int i=0;i<n;i++){H[i].print();cout<<" ";}cout<<endl;}
	inline void add(Point p){//p的横坐标大于H中的点
		while(n>=2&&crp(p-H[n-2],H[n-1]-H[n-2])>=0) n--;
		H[n++]=p;
	}
	inline Frac calc(Point p){//p的横坐标大于H中的点,计算p和凸包上某点形成的最大斜率
		int l=0,r=n-1,mid;
		while(l<r){
			mid=(l+r)/2;
			if(crp(p-H[mid],H[mid+1]-H[mid])>=0) r=mid;
			else l=mid+1;
		}
		return getFrac(H[l].y-p.y,H[l].x-p.x);
	}
};
class Super_Hull{//把两种不同姿势的凸包打包成一个类......这是一种诡异的思路
public:
	Convex_Hull_L_Active hull_L;
	Convex_Hull_R_Active hull_R;
	//type=0为左(上凸),type=1为右(下凸)
	void print(bool type){type?hull_R.print():hull_L.print();}
	inline void clear(bool type){type?hull_R.clear():hull_L.clear();}
	inline void add(int k,bool type){
		if(!type) hull_L.add((Point){k,S[k]});
		else hull_R.add((Point){k,S[k-1]});
	}
	inline Frac calc(int k,bool type){
		if(!type) return hull_L.calc((Point){k,S[k-1]});
		else return hull_R.calc((Point){k,S[k]});
	}
}hull;
Frac calc_seg(int l,int r){
	return getFrac(S[r]-S[l-1],r-l);
}
inline Frac calc(int a,int b){
	Frac ans=getFrac(-INF,1);
	if(belong[a]<K&&head[belong[a]+1]<b){
		if(ans<f[belong[a]+1][b]) ans=f[belong[a]+1][b];
	}
	if(belong[b]>1&&tail[belong[b]-1]>a){
		if(ans<g[belong[b]-1][a]) ans=g[belong[b]-1][a];
	}
	/*下面考虑:头在a的块,尾在b的块内的情况,这时我们采用的思路是,
	将右端的元素加入凸包后枚举答案的左端点,因而凸包左活跃,操作代码0*/
	int l_end=min(b-1,tail[belong[a]]),r_end=max(a+1,head[belong[b]]);
	hull.clear(0);
	int k=l_end;
	for(int i=b;i>=r_end;i--){
		hull.add(i,0);
		if(k==i-1){
			Frac tmp=hull.calc(k,0);
			if(ans<tmp) ans=tmp;
			k--;
		}
	}
	for(;k>=a;k--){
		Frac tmp=hull.calc(k,0);
		if(ans<tmp) ans=tmp;
	}
	return ans;
}
void DP_prepare(void){
	//计算f,即向后的情况,这时是向凸包的尾端插入,凸包右活跃,操作代码1
	for(int i=1;i<=K;i++){
		//该块中元素压入凸包
		hull.clear(1);
		for(int j=head[i];j<=tail[i];j++){
			if(j>head[i]) f[i][j]=hull.calc(j,1);
			hull.add(j,1);
		}
		for(int j=tail[i]+1;j<=N;j++) f[i][j]=hull.calc(j,1);
		for(int j=head[i]+1;j<=N;j++) if(f[i][j]<f[i][j-1]) f[i][j]=f[i][j-1];
	}
	for(int i=K-1;i>=1;i--){
		for(int j=head[i+1];j<=N;j++){
			if(f[i][j]<f[i+1][j]) f[i][j]=f[i+1][j];
		}
	}
	//计算g,即向前的情况,这时是向凸包的头部加入,凸包左活跃,操作代码0
	for(int i=K;i>=1;i--){
		//该块中元素压入凸包
		hull.clear(0);
		for(int j=tail[i];j>=head[i];j--){
			if(j<tail[i]) g[i][j]=hull.calc(j,0);
			hull.add(j,0);
		}
		for(int j=head[i]-1;j>=1;j--) g[i][j]=hull.calc(j,0);
		for(int j=tail[i]-1;j>=1;j--) if(g[i][j]<g[i][j+1]) g[i][j]=g[i][j+1];
	}
	for(int i=2;i<=K;i++){
		for(int j=1;j<=tail[i-1];j++){
			if(g[i][j]<g[i-1][j]) g[i][j]=g[i-1][j];
		}
	}
}
void work(void){
	int a,b;
	for(int i=1;i<=Q;i++){
		scanf("%d%d",&a,&b);
		print(calc(a,b));
		printf("\n");
	}
}
void read(void){
	scanf("%d%d",&N,&Q);
	for(int i=1;i<=N;i++) scanf("%lld",&X[i]),S[i]=S[i-1]+X[i];
	SZ=sqrt(N+0.5)*3;
	K=head[1]=1;
	int tot=0;
	for(int i=1;i<=N;i++){
		belong[i]=K;
		tot++;
		if(tot==SZ||i==N){
			tail[K]=i;
			K++;
			tot=0;
			head[K]=i+1;
		}
	}
	K--;
}
int main(){
	freopen("almost.in","r",stdin);
	freopen("almost.out","w",stdout);
	read();
	DP_prepare();
	work();
	return 0;
}