CF transfer gate: CF1635F

Find property law + monotone stack + segment tree

Solution

1

The examination room came up with the idea of throwing those pairs into a monotonous queue and then fooling around. It is found that for a query interval, if you want to throw it directly into the monotone queue and then find the minimum value of the weighted distance, the complexity is still very high.

In other words, we cannot get the interval optimal solution directly. Then try to solve the single point optimal solution, and then combine the answers in the query interval to get the best.

2

Generally, in this case, we need to discuss three or more nodes to find the property law. Consider the overall situation first.

Let's assume that there are three nodes \ (a,\ b,\ c\), which meet \ (x_a<x_b<x_c\) and \ (w_b<w_c\). The quantitative relationship of \ (w_a\) is not considered because if this property requires that \ (w\) also satisfy monotonicity (\ (x\) itself satisfies monotonicity), then there are too many constraints to do.

We can find that no matter how the three points are combined, \ (d(a,c) \) must not be optimal - \ (d(a,b),\ d(b,c) \) is obviously better than him. And because we want to find the single point optimal solution, for node \ (c\), the nodes before node \ (b\) are meaningless to it (in other words, they will not contribute to the global situation). This property is also true for the case of \ (c<b<a\).

In summary, for each node \ (i\), we can find two corresponding nodes \ (l_i,\ r_i\), which meet \ (l_i<i, \ w_{l_i}<w_i, \ r_i>i, \ w_{r_i}<w_i\). And only these \ (2n\) point pairs can contribute to the global results (because they are better than other point pairs).

3

Look back and see how to deal with the interval.

Naturally, there will be questions: for a single point \ (i\), if both \ (l_i\) and \ (r_i\) are outside the range of interval inquiry, that is, we cannot consider it, but \ (i\) itself can form the optimal solution of the interval with other nodes in the interval?

In order to solve this problem, it is advisable to construct a scenario similar to that described in the problem: for the query interval \ ([L,R]\), the point pair with the smallest weighted distance \ ((a, b) |w)_ a<w_ B\), meet \ (a>l_b\).

According to the properties obtained above, if \ (w_a<w_b\) and \ (a<b\), then obviously \ (l_b=a\) is contradictory to the assumption. The same is true for \ (w_b>w_a\).

To sum up, we conclude that the point pair with the smallest weighted distance in the interval must belong to that \ (2n\) point pair.

4

\(l_i\) and \ (r_i\) can be obtained by single point stack.

Intuitive experience tells us that we can use segment tree to find the best pair of intervals. Specifically, store each \ (d(l_i,i) \) on the point \ (l_i\), \ (r_i\) is the same, and then take the query offline and query and process it in ascending order of \ (R\).

Code

#include<bits/stdc++.h>
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;
}