题目

设 \(f(x,y)=|a_x-a_y|*(w_x+w_y)\)，其中 \(a\) 单调递增

多组询问求 \(\min_{l\leq l'

\(n,Q\leq 3*10^5,|a|,w\leq 10^9\)

分析

可以发现尽量让 \(l',r'\) 靠近最优，处理出每个数的不超过这个数的前驱和后继，

答案一定只能在这最多 \(2n\) 个点对中产生，所以直接离线按右端点排序用树状数组维护即可

代码

#include 
#include 
#include 
using namespace std;
const int N=300011; struct node{int y,next;}e[N];
int x[N],a[N],n,Q,st[N],Top,as[N]; vectorK[N]; 
typedef long long lll; lll ans[N],c[N];
int iut(){
	int ans=0,f=1; char c=getchar();
	while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();
	while (isdigit(c)) ans=ans*10+c-48,c=getchar();
	return ans*f;
}
void print(lll ans){
	if (ans>9) print(ans/10);
	putchar(ans%10+48);
}
lll min(lll a,lll b){return aa[i]) --Top;
		K[i].push_back(st[Top]),st[++Top]=i;
	}
	Top=0;
	for (int i=n;i;--i){
		while (Top&&a[st[Top]]>a[i]) --Top;
		K[st[Top]].push_back(i),st[++Top]=i;
	}
	for (int i=1;i<=Q;++i){
		int l=iut(),r=iut();
		e[i]=(node){l,as[r]},as[r]=i;
	}
	for (int i=1;i<=n;++i){
		int len=K[i].size();
		for (int j=0;j