JOI2014春day1-historical

わからん
subtask2 imos
subtask3 しゃくとり(よい実装方法がよくわからん)
subtask4 わからん(強い人が平方分割とか言ってた、強い人に聞いてください)

#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define rep1(i,n) for(int i=1;i<=(n);++i)
#define ALL(c) (c).begin(),(c).end()
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,int> PP;
ll anss[100000],x[100000],y[100000],naiyo[100000],imos[5000][5001];		//種類,~まで
vector<ll> vc;
vector<P> vv;
vector<PP> vvc;
set<P> st;
int main(){
	int n,q;
	scanf("%d%d",&n,&q);
	rep(i,n){
		scanf("%lld",&x[i]);
		vc.push_back(x[i]);
	}
	sort(ALL(vc));
	vc.erase(unique(ALL(vc)),vc.end());
	if(n<=5000){
		rep(i,n){
			imos[lower_bound(ALL(vc),x[i])-vc.begin()][i+1]++;
		}
		rep(j,vc.size()){
			rep(i,n) imos[j][i+1]+=imos[j][i];
		}
		rep(i,q){
			ll a,b;
			scanf("%lld%lld",&a,&b);
			ll ans=0;
			rep(j,vc.size()){
				ans=max(ans,(imos[j][b]-imos[j][a-1])*vc[j]);
			}
			cout << ans << endl;
		}
		return 0;
	}else{
		rep(i,q){
			ll a,b;
			scanf("%lld%lld",&a,&b);
			vv.push_back(P(a,b));
			vvc.push_back(PP(P(a,b),i));
		}
		sort(ALL(vv));
		sort(ALL(vvc));
		rep(i,n){
			y[i]=lower_bound(ALL(vc),x[i])-vc.begin();		//圧縮後y
		}
		ll right=0,left=0;
		rep(i,vv.size()){		//st:(重要度,内容(圧))
			ll a=vv[i].first,b=vv[i].second;
			while(right!=b){
				if(naiyo[y[right]]==0){
					st.insert(P(x[right],y[right]));
				}else{
					st.erase(P(naiyo[y[right]],y[right]));
					st.insert(P(naiyo[y[right]]+x[right],y[right]));
				}
				naiyo[y[right]]+=x[right];
				right++;
			}
			while(left!=a-1){
				st.erase(P(naiyo[y[left]],y[left]));
				st.insert(P(naiyo[y[left]]-x[left],y[left]));
				naiyo[y[left]]-=x[left];
				left++;
			}
			set<P>::iterator it=st.end();
			it--;
			anss[vvc[i].second]=(*it).first;
		}
		rep(i,q) printf("%lld\n",anss[i]);
	}
	return 0;
}