拼多多校招笔试真题 10.26 - 标价差内选购(C++/Py/Java /Js/Go)

标价差内选购

拼多多 10月26号 笔试真题 第四题

拼多多真题目录点击查看: 拼多多笔试真题题库目录｜笔试题库 + 算法考点详解

题目内容

多多爱吃橘子。这天他停在一家水果摊前面，摊上依次摆着

M

M

M 种彼此不同的橘子。老板每一天都会选中其中一种，把这一天的标价换成一个新数，换完就停在这个新数上，不会自己变回去。 每改完一天，多多都要算一算：只挑标价最高与最低相差不超过

G

G

G 的种类来买，最多可以买进几种。标价一样的橘子仍然各算一种。

输入描述

首行两个整数

M

,

G

M,G

M,G（

1

≤

M

≤

5

×

10

4

,

0

≤

G

≤

10

8

1 \\le M \\le 5 \\times 10^4,0 \\le G \\le 10^8

1≤M≤5×104,0≤G≤108），空格隔开，依次是橘子有几种、允许的最大标价差。 第二行

M

M

M 个正整数

W

1

,

W

2

,

…

,

W

M

W_1,W_2,\\dots,W_M

W1​,W2​,…,WM​（

1

≤

W

i

≤

10

8

1 \\le W_i \\le 10^8

1≤Wi​≤108），空格隔开，是按摆放顺序每种橘子一开始的标价。 第三行单独写天数

T

T

T（

1

≤

T

≤

10

5

1 \\le T \\le 10^5

1≤T≤105）。 其后每一天占一行，先写被改的那种橘子的序号

B

B

B，再写它的新标价

C

C

C（

1

≤

B

≤

M

,

1

≤

C

≤

10

8

1 \\le B \\le M,1 \\le C \\le 10^8

1≤B≤M,1≤C≤108）。

输出描述

一共写出

T

T

T 行。第

i

i

i 行一个整数，表示第

i

i

i 天改完之后，标价差不超过

G

G

G 时最多能买进几种。

样例1

输入

4 3
4 8 1 6
3
2 5
3 4
4 20

输出

3
4
3

说明 第

2

2

2 种改成

5

5

5 后，标价是

4

,

5

,

1

,

6

4,5,1,6

4,5,1,6。

4

,

5

,

6

4,5,6

4,5,6 的极差是

2

2

2，一共

3

3

3 种；

1

1

1 和

4

4

4 也能放在一起，但只有

2

2

2 种。 第

3

3

3 种再改成

4

4

4 后，标价是

4

,

5

,

4

,

6

4,5,4,6

4,5,4,6，全体极差是

2

2

2，答案是

4

4

4。 第

4

4

4 种改成

20

20

20 后，

20

20

20 只能单独算，

4

,

5

,

4

4,5,4

4,5,4 的极差是

1

1

1，答案是

3

3

3。

样例2

输入

3 5
1 6 20
2
3 6
2 100

输出

3
2

说明 第

3

3

3 种改成

6

6

6 后，标价是

1

,

6

,

6

1,6,6

1,6,6。

6

6

6 和

1

1

1 正好相差

5

5

5，三种都能买。 第

2

2

2 种再改成

100

100

100 后，标价是

1

,

100

,

6

1,100,6

1,100,6。

1

1

1 和

6

6

6 仍相差

5

5

5，

100

100

100 放不进这一组，答案是

2

2

2。

题解

思路

解题思路：线段树

C++

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

using ll = long long;

struct SegmentTree {
int n;
vector<int> tree, lazy;

SegmentTree(int n) : n(n), tree(4 * n + 5, 0), lazy(4 * n + 5, 0) {}

void apply(int node, int val) {
tree[node] += val;
lazy[node] += val;
}

void pushDown(int node) {
if (lazy[node] != 0) {
apply(node * 2, lazy[node]);
apply(node * 2 + 1, lazy[node]);
lazy[node] = 0;
}
}

void build(int node, int l, int r, const vector<int>& a) {
if (l == r) {
tree[node] = a[l];
return;
}

int mid = (l + r) / 2;
build(node * 2, l, mid, a);
build(node * 2 + 1, mid + 1, r, a);

tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
}

void update(int node, int l, int r, int ql, int qr, int val) {
if (ql <= l && r <= qr) {
apply(node, val);
return;
}

pushDown(node);

int mid = (l + r) / 2;

if (ql <= mid) {
update(node * 2, l, mid, ql, qr, val);
}

if (qr > mid) {
update(node * 2 + 1, mid + 1, r, ql, qr, val);
}

tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
}

int queryMax() {
return tree[1];
}
};

struct Query {
int b, c;
};

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int M;
ll G;
cin >> M >> G;

vector<int> W(M + 1);
vector<int> all;

for (int i = 1; i <= M; i++) {
cin >> W[i];
all.push_back(W[i]);
}

int T;
cin >> T;

vector<Query> queries(T);

// 读入所有操作，将可能出现的价格加入离散化数组
for (int i = 0; i < T; i++) {
cin >> queries[i].b >> queries[i].c;
all.push_back(queries[i].c);
}

// 离散化所有出现标价 排序 去重
sort(all.begin(), all.end());
all.erase(unique(all.begin(), all.end()), all.end());

int N = all.size();

// cnt[i] 表示当前价格等于 all[i] 的橘子数量
vector<int> cnt(N, 0);

for (int i = 1; i <= M; i++) {
// 返回第一个大于等于 W[i] 的价格下标
int id = lower_bound(all.begin(), all.end(), W[i]) – all.begin();
cnt[id]++;
}

// left[i] 表示所有包含价格 all[i] 的窗口的最小左端点
// 这些窗口的左端价格必须满足 all[i] – all[l] <= G
vector<int> left(N);

for (int i = 0; i < N; i++) {
left[i] = lower_bound(
all.begin(), all.end(), (ll)all[i] – G
) – all.begin();
}

// 初始化 f[i]：以 all[i] 为左端点的窗口内橘子数量
vector<int> f(N, 0);
int r = 0;
int sum = 0;

for (int i = 0; i < N; i++) {
while (r < N && (ll)all[r] – all[i] <= G) {
sum += cnt[r];
r++;
}

f[i] = sum;
sum -= cnt[i];
}

// 建立线段树，维护所有窗口中的最大橘子数量
SegmentTree seg(N);
seg.build(1, 0, N – 1, f);

// 逐天修改价格并输出答案
for (int i = 0; i < T; i++) {
int b = queries[i].b;
int c = queries[i].c;

int oldId = lower_bound(
all.begin(), all.end(), W[b]
) – all.begin();

int newId = lower_bound(
all.begin(), all.end(), c
) – all.begin();

// 如果新旧价格相同，不需要修改
if (oldId != newId) {
// 移除旧价格：所有包含旧价格的窗口数量减 1
seg.update(1, 0, N – 1, left[oldId], oldId, –1);
cnt[oldId]—;

// 加入新价格：所有包含新价格的窗口数量加 1
seg.update(1, 0, N – 1, left[newId], newId, 1);
cnt[newId]++;

W[b] = c;
}

// 根节点维护所有窗口中的最大值
cout << seg.queryMax() << '\\n';
}

return 0;
}

Java

import java.io.*;
import java.util.*;

public class Main {
static class SegmentTree {
int n;
int[] tree, lazy;

SegmentTree(int n) {
this.n = n;
tree = new int[4 * n + 5];
lazy = new int[4 * n + 5];
}

void apply(int node, int val) {
tree[node] += val;
lazy[node] += val;
}

void pushDown(int node) {
if (lazy[node] != 0) {
apply(node * 2, lazy[node]);
apply(node * 2 + 1, lazy[node]);
lazy[node] = 0;
}
}

void build(int node, int l, int r, int[] a) {
if (l == r) {
tree[node] = a[l];
return;
}

int mid = (l + r) / 2;
build(node * 2, l, mid, a);
build(node * 2 + 1, mid + 1, r, a);

tree[node] = Math.max(tree[node * 2], tree[node * 2 + 1]);
}

void update(int node, int l, int r, int ql, int qr, int val) {
if (ql <= l && r <= qr) {
apply(node, val);
return;
}

pushDown(node);

int mid = (l + r) / 2;

if (ql <= mid) {
update(node * 2, l, mid, ql, qr, val);
}

if (qr > mid) {
update(node * 2 + 1, mid + 1, r, ql, qr, val);
}

tree[node] = Math.max(tree[node * 2], tree[node * 2 + 1]);
}

int queryMax() {
return tree[1];
}
}

static class Query {
int b, c;

Query(int b, int c) {
this.b = b;
this.c = c;
}
}

public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());

int M = Integer.parseInt(st.nextToken());
long G = Long.parseLong(st.nextToken());

int[] W = new int[M + 1];
List<Integer> allList = new ArrayList<>();

st = new StringTokenizer(br.readLine());
for (int i = 1; i <= M; i++) {
W[i] = Integer.parseInt(st.nextToken());
allList.add(W[i]);
}

int T = Integer.parseInt(br.readLine().trim());
Query[] queries = new Query[T];

// 读入所有操作，将可能出现的价格加入离散化数组
for (int i = 0; i < T; i++) {
st = new StringTokenizer(br.readLine());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());

queries[i] = new Query(b, c);
allList.add(c);
}

// 离散化所有出现标价：排序、去重
Collections.sort(allList);

int size = allList.size();
int[] temp = new int[size];
int N = 0;

for (int x : allList) {
if (N == 0 || temp[N – 1] != x) {
temp[N++] = x;
}
}

int[] all = Arrays.copyOf(temp, N);

// cnt[i] 表示当前价格等于 all[i] 的橘子数量
int[] cnt = new int[N];

for (int i = 1; i <= M; i++) {
// 返回第一个大于等于 W[i] 的价格下标
int id = Arrays.binarySearch(all, W[i]);
cnt[id]++;
}

// left[i] 表示所有包含价格 all[i] 的窗口的最小左端点
// 这些窗口的左端价格必须满足 all[i] – all[l] <= G
int[] left = new int[N];

for (int i = 0; i < N; i++) {
long target = (long) all[i] – G;

int lo = 0, hi = N;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (all[mid] < target) {
lo = mid + 1;
} else {
hi = mid;
}
}

left[i] = lo;
}

// 初始化 f[i]：以 all[i] 为左端点的窗口内橘子数量
int[] f = new int[N];
int r = 0;
int sum = 0;

for (int i = 0; i < N; i++) {
while (r < N && (long) all[r] – all[i] <= G) {
sum += cnt[r];
r++;
}

f[i] = sum;
sum -= cnt[i];
}

// 建立线段树，维护所有窗口中的最大橘子数量
SegmentTree seg = new SegmentTree(N);
seg.build(1, 0, N – 1, f);

// 逐天修改价格并输出答案
StringBuilder out = new StringBuilder();

for (int i = 0; i < T; i++) {
int b = queries[i].b;
int c = queries[i].c;

int oldId = Arrays.binarySearch(all, W[b]);
int newId = Arrays.binarySearch(all, c);

// 如果新旧价格相同，不需要修改
if (oldId != newId) {
// 移除旧价格：所有包含旧价格的窗口数量减 1
seg.update(1, 0, N – 1, left[oldId], oldId, –1);
cnt[oldId]—;

// 加入新价格：所有包含新价格的窗口数量加 1
seg.update(1, 0, N – 1, left[newId], newId, 1);
cnt[newId]++;

W[b] = c;
}

// 根节点维护所有窗口中的最大值
out.append(seg.queryMax()).append('\\n');
}

System.out.print(out);
}
}

python

import sys
from bisect import bisect_left

input = sys.stdin.readline

class SegmentTree:
def __init__(self, n):
self.n = n
self.tree = [0] * (4 * n + 5)
self.lazy = [0] * (4 * n + 5)

def apply(self, node, val):
self.tree[node] += val
self.lazy[node] += val

def push_down(self, node):
if self.lazy[node] != 0:
self.apply(node * 2, self.lazy[node])
self.apply(node * 2 + 1, self.lazy[node])
self.lazy[node] = 0

def build(self, node, l, r, a):
if l == r:
self.tree[node] = a[l]
return

mid = (l + r) // 2
self.build(node * 2, l, mid, a)
self.build(node * 2 + 1, mid + 1, r, a)

self.tree[node] = max(self.tree[node * 2],
self.tree[node * 2 + 1])

def update(self, node, l, r, ql, qr, val):
if ql <= l and r <= qr:
self.apply(node, val)
return

self.push_down(node)

mid = (l + r) // 2

if ql <= mid:
self.update(node * 2, l, mid, ql, qr, val)

if qr > mid:
self.update(node * 2 + 1, mid + 1, r, ql, qr, val)

self.tree[node] = max(self.tree[node * 2],
self.tree[node * 2 + 1])

def query_max(self):
return self.tree[1]

def main():
M, G = map(int, input().split())

W = [0] + list(map(int, input().split()))
all_prices = W[1:].copy()

T = int(input())

queries = []

# 读入所有操作，将可能出现的价格加入离散化数组
for _ in range(T):
b, c = map(int, input().split())
queries.append((b, c))
all_prices.append(c)

# 离散化所有出现标价：排序、去重
all_prices = sorted(set(all_prices))
N = len(all_prices)

# cnt[i] 表示当前价格等于 all_prices[i] 的橘子数量
cnt = [0] * N

for i in range(1, M + 1):
# 返回第一个大于等于 W[i] 的价格下标
idx = bisect_left(all_prices, W[i])
cnt[idx] += 1

# left[i] 表示所有包含价格 all_prices[i] 的窗口的最小左端点
# 这些窗口的左端价格必须满足 all_prices[i] – all_prices[l] <= G
left = [0] * N

for i in range(N):
left[i] = bisect_left(all_prices, all_prices[i] – G)

# 初始化 f[i]：以 all_prices[i] 为左端点的窗口内橘子数量
f = [0] * N
r = 0
total = 0

for i in range(N):
while r < N and all_prices[r] – all_prices[i] <= G:
total += cnt[r]
r += 1

f[i] = total
total -= cnt[i]

# 建立线段树，维护所有窗口中的最大橘子数量
seg = SegmentTree(N)
seg.build(1, 0, N – 1, f)

# 逐天修改价格并输出答案
ans = []

for b, c in queries:
old_id = bisect_left(all_prices, W[b])
new_id = bisect_left(all_prices, c)

# 如果新旧价格相同，不需要修改
if old_id != new_id:
# 移除旧价格：所有包含旧价格的窗口数量减 1
seg.update(1, 0, N – 1, left[old_id], old_id, –1)
cnt[old_id] -= 1

# 加入新价格：所有包含新价格的窗口数量加 1
seg.update(1, 0, N – 1, left[new_id], new_id, 1)
cnt[new_id] += 1

W[b] = c

# 根节点维护所有窗口中的最大值
ans.append(str(seg.query_max()))

print('\\n'.join(ans))

if __name__ == "__main__":
main()

JavaScript

const readline = require('readline');

const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});

const input = [];

rl.on('line', line => {
input.push(line.trim());
});

rl.on('close', () => {
let idx = 0;

const [M, G] = input[idx++].split(' ').map(Number);

const W = [0, …input[idx++].split(' ').map(Number)];
const all = W.slice(1);

const T = Number(input[idx++]);
const queries = [];

// 读入所有操作，将可能出现的价格加入离散化数组
for (let i = 0; i < T; i++) {
const [b, c] = input[idx++].split(' ').map(Number);
queries.push({ b, c });
all.push(c);
}

// 离散化所有出现标价：排序、去重
all.sort((a, b) => a – b);

const prices = [];
for (const x of all) {
if (prices.length === 0 || prices[prices.length – 1] !== x) {
prices.push(x);
}
}

const N = prices.length;

// 返回第一个大于等于 target 的价格下标
function lowerBound(target) {
let l = 0;
let r = N;

while (l < r) {
const mid = Math.floor((l + r) / 2);

if (prices[mid] < target) {
l = mid + 1;
} else {
r = mid;
}
}

return l;
}

// cnt[i] 表示当前价格等于 prices[i] 的橘子数量
const cnt = new Array(N).fill(0);

for (let i = 1; i <= M; i++) {
// 返回第一个大于等于 W[i] 的价格下标
const id = lowerBound(W[i]);
cnt[id]++;
}

// left[i] 表示所有包含价格 prices[i] 的窗口的最小左端点
// 这些窗口的左端价格必须满足 prices[i] – prices[l] <= G
const left = new Array(N);

for (let i = 0; i < N; i++) {
left[i] = lowerBound(prices[i] – G);
}

// 初始化 f[i]：以 prices[i] 为左端点的窗口内橘子数量
const f = new Array(N).fill(0);
let r = 0;
let sum = 0;

for (let i = 0; i < N; i++) {
while (r < N && prices[r] – prices[i] <= G) {
sum += cnt[r];
r++;
}

f[i] = sum;
sum -= cnt[i];
}

class SegmentTree {
constructor(n) {
this.n = n;
this.tree = new Array(4 * n + 5).fill(0);
this.lazy = new Array(4 * n + 5).fill(0);
}

apply(node, val) {
this.tree[node] += val;
this.lazy[node] += val;
}

pushDown(node) {
if (this.lazy[node] !== 0) {
this.apply(node * 2, this.lazy[node]);
this.apply(node * 2 + 1, this.lazy[node]);
this.lazy[node] = 0;
}
}

build(node, l, r, a) {
if (l === r) {
this.tree[node] = a[l];
return;
}

const mid = Math.floor((l + r) / 2);

this.build(node * 2, l, mid, a);
this.build(node * 2 + 1, mid + 1, r, a);

this.tree[node] = Math.max(
this.tree[node * 2],
this.tree[node * 2 + 1]
);
}

update(node, l, r, ql, qr, val) {
if (ql <= l && r <= qr) {
this.apply(node, val);
return;
}

this.pushDown(node);

const mid = Math.floor((l + r) / 2);

if (ql <= mid) {
this.update(node * 2, l, mid, ql, qr, val);
}

if (qr > mid) {
this.update(node * 2 + 1, mid + 1, r, ql, qr, val);
}

this.tree[node] = Math.max(
this.tree[node * 2],
this.tree[node * 2 + 1]
);
}

queryMax() {
return this.tree[1];
}
}

// 建立线段树，维护所有窗口中的最大橘子数量
const seg = new SegmentTree(N);
seg.build(1, 0, N – 1, f);

// 逐天修改价格并输出答案
const ans = [];

for (const { b, c } of queries) {
const oldId = lowerBound(W[b]);
const newId = lowerBound(c);

// 如果新旧价格相同，不需要修改
if (oldId !== newId) {
// 移除旧价格：所有包含旧价格的窗口数量减 1
seg.update(1, 0, N – 1, left[oldId], oldId, –1);
cnt[oldId]—;

// 加入新价格：所有包含新价格的窗口数量加 1
seg.update(1, 0, N – 1, left[newId], newId, 1);
cnt[newId]++;

W[b] = c;
}

// 根节点维护所有窗口中的最大值
ans.push(seg.queryMax());
}

console.log(ans.join('\\n'));
});

Go

package main

import (
"bufio"
"fmt"
"os"
"sort"
)

func max(a, b int) int {
if a > b {
return a
}
return b
}

type SegmentTree struct {
n int
tree []int
lazy []int
}

func NewSegmentTree(n int) *SegmentTree {
return &SegmentTree{
n: n,
tree: make([]int, 4*n+5),
lazy: make([]int, 4*n+5),
}
}

func (st *SegmentTree) apply(node, val int) {
st.tree[node] += val
st.lazy[node] += val
}

func (st *SegmentTree) pushDown(node int) {
if st.lazy[node] != 0 {
st.apply(node*2, st.lazy[node])
st.apply(node*2+1, st.lazy[node])
st.lazy[node] = 0
}
}

func (st *SegmentTree) build(node, l, r int, a []int) {
if l == r {
st.tree[node] = a[l]
return
}

mid := (l + r) / 2
st.build(node*2, l, mid, a)
st.build(node*2+1, mid+1, r, a)

st.tree[node] = max(st.tree[node*2], st.tree[node*2+1])
}

func (st *SegmentTree) update(node, l, r, ql, qr, val int) {
if ql <= l && r <= qr {
st.apply(node, val)
return
}

st.pushDown(node)

mid := (l + r) / 2

if ql <= mid {
st.update(node*2, l, mid, ql, qr, val)
}

if qr > mid {
st.update(node*2+1, mid+1, r, ql, qr, val)
}

st.tree[node] = max(st.tree[node*2], st.tree[node*2+1])
}

func (st *SegmentTree) queryMax() int {
return st.tree[1]
}

type Query struct {
b, c int
}

func lowerBound(a []int, target int) int {
return sort.Search(len(a), func(i int) bool {
return a[i] >= target
})
}

func main() {
reader := bufio.NewReader(os.Stdin)
writer := bufio.NewWriter(os.Stdout)
defer writer.Flush()

var M, G int
fmt.Fscan(reader, &M, &G)

W := make([]int, M+1)
all := make([]int, 0)

for i := 1; i <= M; i++ {
fmt.Fscan(reader, &W[i])
all = append(all, W[i])
}

var T int
fmt.Fscan(reader, &T)

queries := make([]Query, T)

// 读入所有操作，将可能出现的价格加入离散化数组
for i := 0; i < T; i++ {
fmt.Fscan(reader, &queries[i].b, &queries[i].c)
all = append(all, queries[i].c)
}

// 离散化所有出现标价：排序、去重
sort.Ints(all)

prices := make([]int, 0, len(all))
for _, x := range all {
if len(prices) == 0 || prices[len(prices)–1] != x {
prices = append(prices, x)
}
}

N := len(prices)

// cnt[i] 表示当前价格等于 prices[i] 的橘子数量
cnt := make([]int, N)

for i := 1; i <= M; i++ {
// 返回第一个大于等于 W[i] 的价格下标
id := lowerBound(prices, W[i])
cnt[id]++
}

// left[i] 表示所有包含价格 prices[i] 的窗口的最小左端点
// 这些窗口的左端价格必须满足 prices[i] – prices[l] <= G
left := make([]int, N)

for i := 0; i < N; i++ {
left[i] = lowerBound(prices, prices[i]–G)
}

// 初始化 f[i]：以 prices[i] 为左端点的窗口内橘子数量
f := make([]int, N)
r := 0
sum := 0

for i := 0; i < N; i++ {
for r < N && prices[r]–prices[i] <= G {
sum += cnt[r]
r++
}

f[i] = sum
sum -= cnt[i]
}

// 建立线段树，维护所有窗口中的最大橘子数量
seg := NewSegmentTree(N)
seg.build(1, 0, N–1, f)

// 逐天修改价格并输出答案
for _, query := range queries {
b, c := query.b, query.c

oldId := lowerBound(prices, W[b])
newId := lowerBound(prices, c)

// 如果新旧价格相同，不需要修改
if oldId != newId {
// 移除旧价格：所有包含旧价格的窗口数量减 1
seg.update(1, 0, N–1, left[oldId], oldId, –1)
cnt[oldId]—

// 加入新价格：所有包含新价格的窗口数量加 1
seg.update(1, 0, N–1, left[newId], newId, 1)
cnt[newId]++

W[b] = c
}

// 根节点维护所有窗口中的最大值
fmt.Fprintln(writer, seg.queryMax())
}
}