解题思路

问题分析

有向图构建规则

对于区间[l,r]内任意两个不同顶点u,v，如果满足条件a[u] - a[v] ≥ b[u] - b[v]，则在图中添加有向边u→v。

强势顶点定义

顶点V是强势顶点当且仅当V能够通过有向边到达区间内所有其他顶点。

关键观察与转化

数学转化

将有向边的条件进行重写：

• 原条件：a[u] - a[v] ≥ b[u] - b[v]
• 移项得到：a[u] - b[u] ≥ a[v] - b[v]
• 定义辅助数组：c[i] = a[i] - b[i]
• 简化条件：从u到v有边当且仅当c[u] ≥ c[v]

核心结论

在这种图结构下，顶点u是强势顶点当且仅当对于区间内所有其他顶点v，都有c[u] ≥ c[v]。换句话说，强势顶点就是区间内c值最大的所有顶点。

算法设计

预处理阶段

1. 计算辅助数组c[i] = a[i] - b[i]
2. 构建线段树，每个节点维护两个信息：
   • max_val：区间内c的最大值
   • max_count：最大值在区间内出现的次数

线段树节点合并规则

合并两个子区间时：

• 如果左子区间最大值 > 右子区间最大值：结果为(左最大值, 左计数)
• 如果左子区间最大值 < 右子区间最大值：结果为(右最大值, 右计数)
• 如果左子区间最大值 = 右子区间最大值：结果为(该最大值, 左计数+右计数)

查询处理

对于每个查询区间[l,r]：

1. 在线段树上查询区间[l,r]的最大值和出现次数
2. 直接返回最大值的出现次数作为强势顶点个数

复杂度分析

时间复杂度

• 预处理阶段：计算c数组O(n) + 构建线段树O(n) = O(n)
• 单次查询：线段树区间查询O(log n)
• 总时间复杂度：O(n + q log n)

空间复杂度

• 辅助数组c：O(n)
• 线段树存储：O(n)
• 总空间复杂度：O(n)

代码实现

Python

class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [(0, 0)] * (4 * self.n)  # (max_val, max_count)
        self.build(arr, 1, 0, self.n - 1)
    
    def build(self, arr, node, start, end):
        """构建线段树"""
        if start == end:
            # 叶子节点
            self.tree[node] = (arr[start], 1)
        else:
            mid = (start + end) // 2
            # 递归构建左右子树
            self.build(arr, 2*node, start, mid)
            self.build(arr, 2*node+1, mid+1, end)
            # 合并子节点信息
            self.tree[node] = self.merge(self.tree[2*node], self.tree[2*node+1])
    
    def merge(self, left, right):
        """合并两个区间的信息"""
        left_max, left_count = left
        right_max, right_count = right
        
        if left_max > right_max:
            return (left_max, left_count)
        elif left_max < right_max:
            return (right_max, right_count)
        else:
            return (left_max, left_count + right_count)
    
    def query(self, node, start, end, l, r):
        """查询区间[l,r]的最大值和出现次数"""
        if r < start or end < l:
            return (-float('inf'), 0)  # 空区间
        
        if l <= start and end <= r:
            return self.tree[node]  # 完全包含
        
        mid = (start + end) // 2
        left_result = self.query(2*node, start, mid, l, r)
        right_result = self.query(2*node+1, mid+1, end, l, r)
        
        return self.merge(left_result, right_result)
    
    def range_query(self, l, r):
        """查询区间[l,r]"""
        return self.query(1, 0, self.n - 1, l, r)

def solve():
    # 读取输入
    n, q = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    
    # 计算辅助数组 c[i] = a[i] - b[i]
    c = [a[i] - b[i] for i in range(n)]
    
    # 构建线段树
    seg_tree = SegmentTree(c)
    
    # 处理查询
    for _ in range(q):
        l, r = map(int, input().split())
        l -= 1  # 转换为0-indexed
        r -= 1
        
        # 查询区间[l,r]的最大值和出现次数
        max_val, max_count = seg_tree.range_query(l, r)
        print(max_count)

solve()

Java

import java.util.*;

class SegmentTree {
    static class Node {
        long maxVal;
        int maxCount;
        
        Node(long maxVal, int maxCount) {
            this.maxVal = maxVal;
            this.maxCount = maxCount;
        }
    }
    
    private Node[] tree;
    private int n;
    
    public SegmentTree(int[] arr) {
        this.n = arr.length;
        this.tree = new Node[4 * n];
        build(arr, 1, 0, n - 1);
    }
    
    private void build(int[] arr, int node, int start, int end) {
        if (start == end) {
            // 叶子节点
            tree[node] = new Node(arr[start], 1);
        } else {
            int mid = (start + end) / 2;
            // 递归构建左右子树
            build(arr, 2 * node, start, mid);
            build(arr, 2 * node + 1, mid + 1, end);
            // 合并子节点信息
            tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
        }
    }
    
    private Node merge(Node left, Node right) {
        if (left.maxVal > right.maxVal) {
            return new Node(left.maxVal, left.maxCount);
        } else if (left.maxVal < right.maxVal) {
            return new Node(right.maxVal, right.maxCount);
        } else {
            return new Node(left.maxVal, left.maxCount + right.maxCount);
        }
    }
    
    private Node query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) {
            return new Node(Long.MIN_VALUE, 0); // 空区间
        }
        
        if (l <= start && end <= r) {
            return tree[node]; // 完全包含
        }
        
        int mid = (start + end) / 2;
        Node leftResult = query(2 * node, start, mid, l, r);
        Node rightResult = query(2 * node + 1, mid + 1, end, l, r);
        
        // 处理空区间的情况
        if (leftResult.maxVal == Long.MIN_VALUE) return rightResult;
        if (rightResult.maxVal == Long.MIN_VALUE) return leftResult;
        
        return merge(leftResult, rightResult);
    }
    
    public Node rangeQuery(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读取输入
        int n = sc.nextInt();
        int q = sc.nextInt();
        
        int[] a = new int[n];
        int[] b = new int[n];
        
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        for (int i = 0; i < n; i++) {
            b[i] = sc.nextInt();
        }
        
        // 计算辅助数组 c[i] = a[i] - b[i]
        int[] c = new int[n];
        for (int i = 0; i < n; i++) {
            c[i] = a[i] - b[i];
        }
        
        // 构建线段树
        SegmentTree segTree = new SegmentTree(c);
        
        // 处理查询
        for (int i = 0; i < q; i++) {
            int l = sc.nextInt() - 1; // 转换为0-indexed
            int r = sc.nextInt() - 1;
            
            // 查询区间[l,r]的最大值和出现次数
            SegmentTree.Node result = segTree.rangeQuery(l, r);
            System.out.println(result.maxCount);
        }
        
        sc.close();
    }
}

C++

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

struct Node {
    long long maxVal;
    int maxCount;
    
    Node(long long maxVal = LLONG_MIN, int maxCount = 0) 
        : maxVal(maxVal), maxCount(maxCount) {}
};

class SegmentTree {
private:
    vector<Node> tree;
    int n;
    
    void build(const vector<int>& arr, int node, int start, int end) {
        if (start == end) {
            // 叶子节点
            tree[node] = Node(arr[start], 1);
        } else {
            int mid = (start + end) / 2;
            // 递归构建左右子树
            build(arr, 2 * node, start, mid);
            build(arr, 2 * node + 1, mid + 1, end);
            // 合并子节点信息
            tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
        }
    }
    
    Node merge(const Node& left, const Node& right) {
        if (left.maxVal == LLONG_MIN) return right;
        if (right.maxVal == LLONG_MIN) return left;
        
        if (left.maxVal > right.maxVal) {
            return Node(left.maxVal, left.maxCount);
        } else if (left.maxVal < right.maxVal) {
            return Node(right.maxVal, right.maxCount);
        } else {
            return Node(left.maxVal, left.maxCount + right.maxCount);
        }
    }
    
    Node query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) {
            return Node(); // 空区间
        }
        
        if (l <= start && end <= r) {
            return tree[node]; // 完全包含
        }
        
        int mid = (start + end) / 2;
        Node leftResult = query(2 * node, start, mid, l, r);
        Node rightResult = query(2 * node + 1, mid + 1, end, l, r);
        
        return merge(leftResult, rightResult);
    }

public:
    SegmentTree(const vector<int>& arr) {
        n = arr.size();
        tree.resize(4 * n);
        build(arr, 1, 0, n - 1);
    }
    
    Node rangeQuery(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    // 读取输入
    int n, q;
    cin >> n >> q;
    
    vector<int> a(n), b(n);
    
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    
    // 计算辅助数组 c[i] = a[i] - b[i]
    vector<int> c(n);
    for (int i = 0; i < n; i++) {
        c[i] = a[i] - b[i];
    }
    
    // 构建线段树
    SegmentTree segTree(c);
    
    // 处理查询
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        l--; r--; // 转换为0-indexed
        
        // 查询区间[l,r]的最大值和出现次数
        Node result = segTree.rangeQuery(l, r);
        cout << result.maxCount << "\n";
    }
    
    return 0;
}

题目内容

给定两个长度为 $n$ 的整数数组 $a$ 和 $b$ ，下标从 $1$ 到 $n$ 。我们定义对于区间 $[l,r]$ 上的有向图构造规则：

$1.$ 顶点集合为区间内所有下标； $2.$ 若 $u≠υ$ 且满足 $a_u-α_v ≥ b_u -b_v$ ，则在图中加入一条从 $u$ 指向 $v$ 的有向边。

若顶点 $V$ 能够沿着有向边可达区间内所有其他顶点，则称 $V$ 是区间 $[l,r]$ 上的一个 强势顶点 。特别地，如果区间内只有一个顶点，则该顶点也是强势顶点。对于每个查询，请输出该区间内强势顶点的个数。

【名词解释】

• 强势顶点：在有向图中，从该顶点出发，沿着边可以到达图中所有其他顶点的顶点。

输入描述

第一行输入两个整数 $n(1≦n≦2×10^5)$ 和 $q(1≦q≦ 2 × 10^5)$ ，分别表示数组长度和查询次数。

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(-10^5≦a_i≦10^5)$ 。

第三行输入 $n$ 个整数 $b_1,b_2,...,b_n(-10^5≦b_i≦10^5)$ 。

接下来 $q$ 行，每行输入两个整数 $l$ 和 $r$ $(1≦l≦r≦n)$ ，表示一次区间查询。

输出描述

对于每个查询，输出一行一个整数，表示该区间内强势顶点的个数。

样例1

输入

5 3
1 3 2 5 4
2 1 4 3 0
1 5
2 4
3 3

输出

1
2
1

说明

在第一个样例中：

• 对区间 $[1,5]$ ，有唯一的强势顶点 $5$ ；

• 对区间 $[2,4]$ ，强势顶点为 $2,4$ ；

• 对区间 $[3,3]$ ，只有一个顶点 $3$ ，自然是强势顶点。

样例2

输入

6 2
1 1 1 1 1 1
2 2 2 2 2 2
1 6
4 6

输出

6
3

说明