本文主要是介绍(AtCoder Beginner Contest 327) --- F-Apples --- 题解 （一个比较难想的线段树题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
F-Apples：
题目大意：
编辑编辑 思路解析：
代码实现：
F-Apples：
题目大意：
样例解释：
思路解析：
题目要求我们选择任意一对S，L，让苹果满足 S-0.5<= T<= S + D - 0.5 和 L-0.5 <= X <= L + W -0.5的苹果数量尽可能多，并且输出在能选择的可能性中最多的苹果数量为多少，其实我们可以发现这个需要满足的条件其实等价于 S <= T <= S+D 和 L <= x <= L + W，这是因为T和X都是整数。
那我们可以将所有苹果按照T排序，那么我们可以利用双指针来固定任意一个S的可能性，那么我们就需要查询在当前时间轴下，怎么选择L，可以使得答案最优。这个寻优过程其实可以反过来看作每个苹果可以对W大小的区间产生影响，我们应该找到那个点拥有的影响最大，这里那么就可以使用线段树的区间修改 （查询信息的正确 其实可以在修改时就可以维护出来）。
代码实现：
import java.io.*;
import java.math.BigInteger;
import java.util.*;public class Main {static long inf = (long) 2e18;static long mod = 998244353;public static void main(String[] args) throws IOException {int t = 1;while (t > 0) {solve();t--;}w.flush();w.close();br.close();}public static void solve() {int N = f.nextInt();int D = f.nextInt();int W = f.nextInt();int max = 0;int[][] p = new int[N][2];for (int i = 0; i < N; i++) {p[i][0] = f.nextInt();p[i][1] = f.nextInt();max = Math.max(p[i][1], max);}Arrays.sort(p, ((o1, o2) -> {return o1[0] - o2[0];}));int i = 0;int j = 0;SegTree seg = new SegTree();seg.build(1, 1, max);int ans = 0;while (j < N){if (i > 0){int x = p[i-1][1];seg.add(1, Math.max(1, x - W + 1), x, -1);}while (j < N && p[j][0] - p[i][0] < D){int x = p[j][1];seg.add(1, Math.max(1, x - W + 1), x, 1);j++;}ans = Math.max(ans, seg.t[1].max);i++;}w.println(ans);}static int MAXN = (int) 2e5 + 5;static class Node{int l, r, max, lazy;}static class SegTree{Node[] t = new Node[MAXN * 4];public SegTree(){for (int i = 0; i < MAXN * 4; i++) {t[i] = new Node();}}public void build(int root, int l, int r){t[root].l = l; t[root].r = r;if (l == r) return;int mid = (l + r) >> 1;build(root << 1, l, mid);build((root << 1) | 1, mid+1, r);}public void push_down(int root){if (t[root].lazy != 0){if (t[root].l != t[root].r){int ch = root << 1;int x = t[root].lazy;t[ch].max += x;t[ch |1].max += x;t[ch].lazy += x;t[ch | 1].lazy += x;}t[root].lazy = 0;}}public void add(int root, int l, int r, int x){push_down(root);if (t[root].l == l && t[root].r == r){t[root].max += x;t[root].lazy += x;return;}int mid = (t[root].l + t[root].r) >> 1;int ch = root << 1;if (r <= mid) add(ch, l, r, x);else if (l > mid) add(ch|1, l, r, x);else {add(ch, l, mid, x);add(ch|1, mid+1, r, x);}update(root);}public void update(int root){t[root].max = Math.max(t[root << 1].max, t[(root << 1) | 1].max);}}static PrintWriter w = new PrintWriter(new OutputStreamWriter(System.out));static Input f = new Input(System.in);static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static class Input {public BufferedReader reader;public StringTokenizer tokenizer;public Input(InputStream stream) {reader = new BufferedReader(new InputStreamReader(stream), 32768);tokenizer = null;}public String next() {while (tokenizer == null || !tokenizer.hasMoreTokens()) {try {tokenizer = new StringTokenizer(reader.readLine());} catch (IOException e) {throw new RuntimeException(e);}}return tokenizer.nextToken();}public String nextLine() {String str = null;try {str = reader.readLine();} catch (IOException e) {// TODO 自动生成的 catch 块e.printStackTrace();}return str;}public int nextInt() {return Integer.parseInt(next());}public long nextLong() {return Long.parseLong(next());}public Double nextDouble() {return Double.parseDouble(next());}public BigInteger nextBigInteger() {return new BigInteger(next());}}
}这篇关于(AtCoder Beginner Contest 327) --- F-Apples --- 题解 （一个比较难想的线段树题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
