[数据结构与算法]Codeforces 1635 F. Closest Pair —— 树状数组，思维，有一丶丶东西

This way

题意：

给你长度为n的数组x（x[i]<x[i+1]）和w，对于一对i,j，定义他们的val为$|x_i?x_j|?(w_i+w_j)$。
每次给你l,r，问你[l,r]中val最小为多少

题解：

第一次挑战28的题目，说实话还是不够难，感觉只有25左右难度。
一开始我想到的是笛卡尔树，但是不太对劲，因为它并不是区间这种东西。
接下来我想到的是斜率优化，然后我就开始写式子…然后就写不下去了。
由于点i一定会找w比它小的点，然后对于每一个开头的右边必然是一个随着x增大，w梯度下降，或者对于左边，随着x减小，w梯度下降，就像下面一样：

然后维护一下每个点，它相较于上一个点的最优位置区间在哪。但是搞了半天也不行。

真没想到是这么简单一个想法，其实也就是我上面这个想法没有再深入分析一下。
首先要得到一个结论：对于点i，这个点只需要找到左边离它最近的w比它小的点，或者右边离它最近的w比它小的点。比如上图红线就只需要找到紫线或者绿线即可。
但是可能会有这个问题：那说不定对于红线来说，蓝线比紫线更优呢？
要注意w逐渐减小的话，你找红蓝这对线，不如找蓝紫这对线。

那么接下来就很简单了：
我们只需要从前往后维护递增的单调栈找每个点左边的第一个小的值，然后再从右到左做一遍。
那么我们现在找到了不多余n*2对点，那么对于每个询问，答案必然在n*2对点中。如何找到？
那我们只需要从小到大枚举这些点对的右端点R，然后将左端点L的答案加入树状数组中。对于所有询问在R的位置，只需要在树状数组中找到>=L的最小值即可啊。

愚蠢了愚蠢了，应该再动点脑子的，不要被28这个标签吓到。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf=6e18;
const int N=3e5+5;
int st[N],top,x[N],w[N];
vector<int>vec[N];
#define pii pair<int,int>
vector<pii>q[N];
ll mi[N];
ll ans[N];
int lowbit(int x){return x&(-x);}
void add(int x,ll v){
    for(int i=x;i;i-=lowbit(i))
        mi[i]=min(mi[i],v);
}
ll query(int x){
    ll ans=inf;
    for(int i=x;i<N;i+=lowbit(i))
        ans=min(ans,mi[i]);
    return ans;
}
int main()
{
    for(int i=0;i<N;i++)mi[i]=inf;
    int n,m,l,r;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d%d",&x[i],&w[i]);
    for(int i=1;i<=m;i++)scanf("%d%d",&l,&r),q[r].push_back({l,i});
    for(int i=1;i<=n;i++){
        while(top&&w[st[top]]>w[i])top--;
        if(top)vec[i].push_back(st[top]);
        st[++top]=i;
    }
    top=0;
    for(int i=n;i;i--){
        while(top&&w[st[top]]>w[i])top--;
        if(top)vec[st[top]].push_back(i);
        st[++top]=i;
    }
    for(int i=1;i<=n;i++){
        for(auto j :vec[i]){
            ll v=1ll*(x[i]-x[j])*(w[i]+w[j]);
            add(j,v);
        }
        for(auto j:q[i])
            ans[j.second]=query(j.first);
    }
    for(int i=1;i<=m;i++)
        printf("%lld\n",ans[i]);
    return 0;
}