クエリを先読みし、 \(X\) の降順に処理することを考えます。新たに見える山が1つ増えたときの、眺望値の総和の変化量が分かればよいです。

山が増えたときの状態の変化は「1つの山からなる山脈が新たに形成される」「隣り合う2つの山脈がマージされる」の2段階に分けて考えることができます。

それぞれの処理はUnion-Findに眺望値をもたせることでも実現できますが、山脈の両端だけが情報をもてば十分であることを用いて、（山脈の左端、右端、眺望値）の3値を管理すれば十分です。

山を追加する処理は \(O(1)\) で行えることから、全体で \(O(N\log N+Q\log Q)\) でこの問題を解くことができます。

別解として、答えが高々 \(N+1\) 通りの値しか取らないことを用い、それらを \(O(N\log N)\) で予め列挙しておき、各クエリでは二分探索により答えを求める \(O((N+Q)\log N)\) 解法も存在します。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n, q;
  cin >> n >> q;
  vector<int> a(n), b(n);
  for(int i=0; i<n; i++) cin >> a[i] >> b[i];
  
  vector<array<int, 2>> ai(n);
  for(int i=0; i<n; i++){
    ai[i] = {a[i], i};
  }
  sort(ai.rbegin(), ai.rend());
  
  vector<array<int, 2>> xi(q);
  for(int i=0; i<q; i++){
    cin >> xi[i][0];
    xi[i][1] = i;
  }
  sort(xi.rbegin(), xi.rend());

  vector<long long> ans(q);
  int pos = 0;
  long long crr = 0;  // 眺望値の総和
  vector<array<int, 3>> lrm(n, {-1,-1,-1});  // (山脈の左端, 山脈の右端, 眺望値)
  for(auto[x, ii]: xi){
    while(pos < n && ai[pos][0] >= x){
      auto[a, i] = ai[pos];
      // 山の追加
      lrm[i] = {i, i, b[i]};
      crr += b[i];
      auto merge=[&](int i,int j){
        int l = lrm[i][0];
        int r = lrm[j][1];
        int m = max(lrm[i][2], lrm[j][2]);
        crr += m - lrm[i][2] - lrm[j][2];
        lrm[l] = lrm[r] = {l, r, m};
      };
      if(i != 0 && lrm[i-1][2] != -1){
        merge(i-1, i);
      }
      if(i != n-1 && lrm[i+1][2] != -1){
        merge(i, i+1);
      }
      pos++;
    }
    ans[ii] = crr;
  }
  
  for(int i=0; i<q; i++) cout << ans[i] << endl;
}

実装例 (Python)

N, Q = map(int, input().split())
A = []
B = []
for _ in range(N):
  a, b = map(int, input().split())
  A.append(a)
  B.append(b)

AI = [(a, i) for i, a in enumerate(A)]
AI.sort(reverse=True)

XI = [(int(input()), i) for i in range(Q)]
XI.sort(reverse=True)

ans = [0] * Q
pos = 0
crr = 0  # 眺望値の総和
LRM = [(-1, -1, -1)] * N  # (山脈の左端, 山脈の右端, 眺望値)
for x, ii in XI:
  while pos < N and AI[pos][0] >= x:
    a, i = AI[pos]
    # 山の追加
    LRM[i] = (i, i, B[i])
    crr += B[i]
    def merge(i, j):
      global crr
      L = LRM[i][0]
      R = LRM[j][1]
      M = max(LRM[i][2], LRM[j][2])
      crr += M - LRM[i][2] - LRM[j][2]
      LRM[L] = (L, R, M)
      LRM[R] = (L, R, M)
    # 左の山脈とマージ
    if i != 0 and LRM[i-1][2] != -1:
      merge(i-1, i)
    # 右の山脈とマージ
    if i != N-1 and LRM[i+1][2] != -1:
      merge(i, i+1)
    pos += 1
  ans[ii] = crr

print(*ans, sep="\n")