【CF1635F】 Closest Pair 题解

综上，我们得到结论：区间内的带权距离最小的点对一定属于那 $2n$ 个点对之中。

4

$l_i$ 和 $r_i$ 可以通过单点栈得到。

直觉经验告诉我们查找区间最优点对可以使用线段树实现。具体地，将每个 $d(l_i,i)$ 存在点 $l_i$ 上，$r_i$ 同理，再将询问离线下来，按 $R$ 升序依次查询处理即可。

Code

#include
using namespace std;
 
#define int long long
#define per(i, a, b) for(register int i = a; i >= b; --i)
#define rep(i, a, b) for(register int i = a; i <= b; ++i)
const int maxn = 3e5 + 5;
int n, q;
int x[maxn], w[maxn], st[maxn], top;
struct node{int l, id;};
vector<node> que[maxn];
int ans[maxn];
vector<int> p[maxn];
int fr[maxn], bc[maxn], l, r;
 
struct segment_tree{
    #define ls(x) (x<<1)
    #define rs(x) (x<<1|1)
    int mn[maxn << 2];
    inline void updt(int i, int l, int r, int pos, int k){
        if(l == r){
            mn[i] = min(mn[i], k); return;
        }
        int mid = l + r >> 1;
        if(pos <= mid) updt(ls(i), l, mid, pos, k); else updt(rs(i), mid + 1, r, pos, k);
        mn[i] = min(mn[ls(i)], mn[rs(i)]);
    }
    inline int qry(int i, int l, int r, int L, int R){
        if(l >= L and r <= R) return mn[i];
        int mid = l + r >> 1, res = 5e18;
        if(L <= mid) res = min(res, qry(ls(i), l, mid, L, R));
        if(R > mid) res = min(res, qry(rs(i), mid + 1, r, L, R));
        return res;
    }
}T;
 
signed main(){
    scanf("%lld%lld", &n, &q);
    rep(i, 1, n << 2) T.mn[i] = 5e18;
    rep(i, 1, n) scanf("%lld%lld", &x[i], &w[i]);
    rep(i, 1, n){
        while(top and w[st[top]] > w[i]) top -= 1;
        fr[i] = st[top], st[++top] = i;
    } top = 0;
    per(i, n, 1){
        while(top and w[st[top]] > w[i]) top -= 1;
        bc[i] = st[top], st[++top] = i;
    }
    rep(i, 1, n){
        if(fr[i]) p[i].push_back(fr[i]);
        if(bc[i]) p[bc[i]].push_back(i); 
    }
    rep(i, 1, q) 
        scanf("%lld%lld", &l, &r), ans[i] = 5e18, que[r].push_back({l, i});
    rep(i, 1, n){
        for(auto j : p[i]) T.updt(1, 1, n, j, 1ll * abs(x[i] - x[j]) * (w[i] + w[j]));
        for(auto j : que[i]) ans[j.id] = T.qry(1, 1, n, j.l, i);
    }
    rep(i, 1, q) printf("%lld\n", ans[i]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61