新卷-敌情监控-（Java&Python&JS&C++&C）

Ne0inhk

— 17 min read

新卷-敌情监控-（Java&Python&JS&C++&C）

题目描述

H国最近在和M国打仗，H国间谍头子Peter负责监视敌国M的兵力部署情况。M国沿边境线布置了N个营地，Peter的任务就是监视这些营地的兵力部署情况。中央情报局要研究敌情，所以Peter要汇报一段兵营中哪个连续的K个营地驻兵最少之和是多少，可以作为攻击的突破点，例如：“Peter，快汇报第2个营地到第10个营地中H连续的3座兵营人数之和最少”；而且每个营地的人数在不断变化。请你帮Peter设计一个程序，快速计算汇到的结果

输入描述

第一行3个正整数：N K L

N(N<=50000),表示敌人营地兵营的数量，每个营地编号为1,2,3...N.K表示连续的兵营数,L表示后续要问的命令数量；接下来有N个正整数，第i个正整数ai代表第i个营地里开始时有ai个人（1<=ai<=50000）

接下来有行有L条命令。命令有3种形式：

(1)Add i j, i和j为正整数，表示第i个营地增加j个人（j不超过30）

(2)Sub i j, i和j为正整数，表示第i个营地减少j个人（j不超过30）

(3)Query i j, i和j为正整数, i<=j，表示询问问第i个营地到第j个营地，连续H个兵营人数之和最少的总人数

其中: j-i+1>=K，每组数据最多有50条命令

输出描述

对于每个Query询问，输出一个整数并回车，表示询问的该段中的连续的K座兵营人数之和最少的数量，这个数保持在int以内

用例1

说明

说明 第一行第一个正整数5，表示敌人有5个营地，第二个正整数2，表示连续营地 的数量是2， 第3个正整数3，表示后续会有3条询问的命令；接下来一行有 5个正整数，分别表示每个营地里开使的人数，第1个营地开始有1个人，第 2个营地开始有2个人，第3个营地开始有2个人，第4个营地开始有3个人，第5 个营地开始有3个人；

接下来每行有一条命令：

第1条命令：Query 1 3 表示要查询第1到第3个营地的总人数，结果：1+2=3 第一个输出是：3

第2条命令：Add 3 6 表示第3个营地增加6个人 无需输出

第3条命令：Query 2 4 表示查询第2到第4个营地的总人数，结果：

2+8=10 第一个输出是：10，注意这里第3个营地人数在第2条命令中增加了 6

思路分析

  1. 问题核心：对于每个Query，需要在区间[i, j]内找到所有长度为K的子区间，求它们和的最小值
  2. 数据规模：
    • N ≤ 50000
    • 最多50条命令（L ≤ 50）
    • 单点更新，j ≤ 30（变化不大）
  3. 关键点：
    • 需要快速查询区间内固定长度子数组的最小和
    • 由于命令数很少，可以用线段树维护区间信息
    • 每个节点需要存储的信息：区间和、区间内所有长度为K的子区间的最小和

Java实现

java

import java.io.*; public class Main { static class SegmentTree { int n, k; int[] sum; // 区间和 int[] minKSum; // 区间内长度为K的最小和 SegmentTree(int n, int k, int[] arr) { this.n = n; this.k = k; sum = new int[4 * n]; minKSum = new int[4 * n]; build(1, 1, n, arr); } void build(int node, int l, int r, int[] arr) { if (l == r) { sum[node] = arr[l]; minKSum[node] = (k == 1) ? arr[l] : Integer.MAX_VALUE; return; } int mid = (l + r) / 2; build(node * 2, l, mid, arr); build(node * 2 + 1, mid + 1, r, arr); sum[node] = sum[node * 2] + sum[node * 2 + 1]; // 合并子区间的minKSum if (r - l + 1 >= k) { minKSum[node] = Math.min(minKSum[node * 2], minKSum[node * 2 + 1]); // 还需要考虑跨越两个子区间的长度为K的子区间 if (mid - l + 1 >= k - (r - mid)) { int leftStart = Math.max(l, mid - k + 2); for (int start = leftStart; start <= mid && start + k - 1 <= r; start++) { int end = start + k - 1; if (end <= r) { minKSum[node] = Math.min(minKSum[node], querySum(start, end)); } } } } else { minKSum[node] = Integer.MAX_VALUE; } } void update(int node, int l, int r, int idx, int delta) { if (l == r) { sum[node] += delta; if (k == 1) { minKSum[node] = sum[node]; } return; } int mid = (l + r) / 2; if (idx <= mid) { update(node * 2, l, mid, idx, delta); } else { update(node * 2 + 1, mid + 1, r, idx, delta); } sum[node] = sum[node * 2] + sum[node * 2 + 1]; // 重新计算minKSum if (r - l + 1 >= k) { minKSum[node] = Math.min(minKSum[node * 2], minKSum[node * 2 + 1]); // 考虑跨越两个子区间的长度为K的子区间 if (mid - l + 1 >= k - (r - mid)) { int leftStart = Math.max(l, mid - k + 2); for (int start = leftStart; start <= mid && start + k - 1 <= r; start++) { int end = start + k - 1; if (end <= r) { minKSum[node] = Math.min(minKSum[node], querySum(start, end)); } } } } else { minKSum[node] = Integer.MAX_VALUE; } } int queryMinKSum(int node, int l, int r, int ql, int qr) { if (ql > qr || r - l + 1 < k) { return Integer.MAX_VALUE; } // 如果当前区间完全在查询区间内且长度大于等于K if (ql <= l && r <= qr) { if (r - l + 1 >= k) { return minKSum[node]; } return Integer.MAX_VALUE; } int mid = (l + r) / 2; int result = Integer.MAX_VALUE; if (ql <= mid) { result = Math.min(result, queryMinKSum(node * 2, l, mid, ql, Math.min(qr, mid))); } if (qr > mid) { result = Math.min(result, queryMinKSum(node * 2 + 1, mid + 1, r, Math.max(ql, mid + 1), qr)); } // 考虑跨越两个子区间的长度为K的子区间 if (ql <= mid && qr > mid) { int leftStart = Math.max(ql, mid - k + 2); int rightEnd = Math.min(qr, mid + k - 1); for (int start = leftStart; start <= mid && start + k - 1 <= rightEnd; start++) { int end = start + k - 1; if (end <= qr && end >= ql + k - 1) { result = Math.min(result, querySum(start, end)); } } } return result; } int querySum(int l, int r) { return querySum(1, 1, n, l, r); } int querySum(int node, int l, int r, int ql, int qr) { if (ql > qr) return 0; if (ql <= l && r <= qr) return sum[node]; int mid = (l + r) / 2; int result = 0; if (ql <= mid) result += querySum(node * 2, l, mid, ql, Math.min(qr, mid)); if (qr > mid) result += querySum(node * 2 + 1, mid + 1, r, Math.max(ql, mid + 1), qr); return result; } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] firstLine = br.readLine().split(" "); int N = Integer.parseInt(firstLine[0]); int K = Integer.parseInt(firstLine[1]); int L = Integer.parseInt(firstLine[2]); int[] arr = new int[N + 1]; String[] arrStr = br.readLine().split(" "); for (int i = 1; i <= N; i++) { arr[i] = Integer.parseInt(arrStr[i - 1]); } SegmentTree segTree = new SegmentTree(N, K, arr); for (int i = 0; i < L; i++) { String[] command = br.readLine().split(" "); String type = command[0]; int x = Integer.parseInt(command[1]); int y = Integer.parseInt(command[2]); if (type.equals("Add")) { segTree.update(1, 1, N, x, y); } else if (type.equals("Sub")) { segTree.update(1, 1, N, x, -y); } else if (type.equals("Query")) { // 查询区间[x, y]中长度为K的最小和 int result = segTree.queryMinKSum(1, 1, N, x, y - K + 1); System.out.println(result); } } } }

Python实现

python

import sys class SegmentTree: def __init__(self, n, k, arr): self.n = n self.k = k self.sum = [0] * (4 * n) self.minKSum = [float('inf')] * (4 * n) self.build(1, 1, n, arr) def build(self, node, l, r, arr): if l == r: self.sum[node] = arr[l] self.minKSum[node] = arr[l] if self.k == 1 else float('inf') return mid = (l + r) // 2 self.build(node * 2, l, mid, arr) self.build(node * 2 + 1, mid + 1, r, arr) self.sum[node] = self.sum[node * 2] + self.sum[node * 2 + 1] # 合并子区间的minKSum if r - l + 1 >= self.k: self.minKSum[node] = min(self.minKSum[node * 2], self.minKSum[node * 2 + 1]) # 考虑跨越两个子区间的长度为K的子区间 if mid - l + 1 >= self.k - (r - mid): left_start = max(l, mid - self.k + 2) for start in range(left_start, mid + 1): end = start + self.k - 1 if end <= r: self.minKSum[node] = min(self.minKSum[node], self._query_sum(start, end)) else: self.minKSum[node] = float('inf') def update(self, node, l, r, idx, delta): if l == r: self.sum[node] += delta if self.k == 1: self.minKSum[node] = self.sum[node] return mid = (l + r) // 2 if idx <= mid: self.update(node * 2, l, mid, idx, delta) else: self.update(node * 2 + 1, mid + 1, r, idx, delta) self.sum[node] = self.sum[node * 2] + self.sum[node * 2 + 1] # 重新计算minKSum if r - l + 1 >= self.k: self.minKSum[node] = min(self.minKSum[node * 2], self.minKSum[node * 2 + 1]) # 考虑跨越两个子区间的长度为K的子区间 if mid - l + 1 >= self.k - (r - mid): left_start = max(l, mid - self.k + 2) for start in range(left_start, mid + 1): end = start + self.k - 1 if end <= r: self.minKSum[node] = min(self.minKSum[node], self._query_sum(start, end)) else: self.minKSum[node] = float('inf') def query_min_k_sum(self, node, l, r, ql, qr): if ql > qr or r - l + 1 < self.k: return float('inf') if ql <= l and r <= qr: if r - l + 1 >= self.k: return self.minKSum[node] return float('inf') mid = (l + r) // 2 result = float('inf') if ql <= mid: result = min(result, self.query_min_k_sum(node * 2, l, mid, ql, min(qr, mid))) if qr > mid: result = min(result, self.query_min_k_sum(node * 2 + 1, mid + 1, r, max(ql, mid + 1), qr)) # 考虑跨越两个子区间的长度为K的子区间 if ql <= mid and qr > mid: left_start = max(ql, mid - self.k + 2) right_end = min(qr, mid + self.k - 1) for start in range(left_start, mid + 1): end = start + self.k - 1 if end <= qr and end >= ql + self.k - 1: result = min(result, self._query_sum(start, end)) return result def _query_sum(self, l, r): return self._query_sum_helper(1, 1, self.n, l, r) def _query_sum_helper(self, node, l, r, ql, qr): if ql > qr: return 0 if ql <= l and r <= qr: return self.sum[node] mid = (l + r) // 2 result = 0 if ql <= mid: result += self._query_sum_helper(node * 2, l, mid, ql, min(qr, mid)) if qr > mid: result += self._query_sum_helper(node * 2 + 1, mid + 1, r, max(ql, mid + 1), qr) return result def main(): data = sys.stdin.read().strip().split() idx = 0 N = int(data[idx]); idx += 1 K = int(data[idx]); idx += 1 L = int(data[idx]); idx += 1 arr = [0] * (N + 1) for i in range(1, N + 1): arr[i] = int(data[idx]); idx += 1 seg_tree = SegmentTree(N, K, arr) results = [] for _ in range(L): cmd = data[idx]; idx += 1 x = int(data[idx]); idx += 1 y = int(data[idx]); idx += 1 if cmd == "Add": seg_tree.update(1, 1, N, x, y) elif cmd == "Sub": seg_tree.update(1, 1, N, x, -y) elif cmd == "Query": # 查询区间[x, y]中长度为K的最小和 result = seg_tree.query_min_k_sum(1, 1, N, x, y - K + 1) results.append(str(result)) print("\n".join(results)) if __name__ == "__main__": main()

C++实现

cpp

#include <iostream> #include <vector> #include <string> #include <climits> #include <algorithm> using namespace std; class SegmentTree { private: int n, k; vector<int> sum; vector<int> minKSum; void build(int node, int l, int r, vector<int>& arr) { if (l == r) { sum[node] = arr[l]; minKSum[node] = (k == 1) ? arr[l] : INT_MAX; return; } int mid = (l + r) / 2; build(node * 2, l, mid, arr); build(node * 2 + 1, mid + 1, r, arr); sum[node] = sum[node * 2] + sum[node * 2 + 1]; if (r - l + 1 >= k) { minKSum[node] = min(minKSum[node * 2], minKSum[node * 2 + 1]); if (mid - l + 1 >= k - (r - mid)) { int leftStart = max(l, mid - k + 2); for (int start = leftStart; start <= mid; start++) { int end = start + k - 1; if (end <= r) { minKSum[node] = min(minKSum[node], querySum(start, end)); } } } } else { minKSum[node] = INT_MAX; } } int querySum(int l, int r) { return querySum(1, 1, n, l, r); } int querySum(int node, int l, int r, int ql, int qr) { if (ql > qr) return 0; if (ql <= l && r <= qr) return sum[node]; int mid = (l + r) / 2; int result = 0; if (ql <= mid) result += querySum(node * 2, l, mid, ql, min(qr, mid)); if (qr > mid) result += querySum(node * 2 + 1, mid + 1, r, max(ql, mid + 1), qr); return result; } public: SegmentTree(int n, int k, vector<int>& arr) : n(n), k(k) { sum.resize(4 * n); minKSum.resize(4 * n, INT_MAX); build(1, 1, n, arr); } void update(int node, int l, int r, int idx, int delta) { if (l == r) { sum[node] += delta; if (k == 1) { minKSum[node] = sum[node]; } return; } int mid = (l + r) / 2; if (idx <= mid) { update(node * 2, l, mid, idx, delta); } else { update(node * 2 + 1, mid + 1, r, idx, delta); } sum[node] = sum[node * 2] + sum[node * 2 + 1]; if (r - l + 1 >= k) { minKSum[node] = min(minKSum[node * 2], minKSum[node * 2 + 1]); if (mid - l + 1 >= k - (r - mid)) { int leftStart = max(l, mid - k + 2); for (int start = leftStart; start <= mid; start++) { int end = start + k - 1; if (end <= r) { minKSum[node] = min(minKSum[node], querySum(start, end)); } } } } else { minKSum[node] = INT_MAX; } } int queryMinKSum(int node, int l, int r, int ql, int qr) { if (ql > qr || r - l + 1 < k) { return INT_MAX; } if (ql <= l && r <= qr) { if (r - l + 1 >= k) { return minKSum[node]; } return INT_MAX; } int mid = (l + r) / 2; int result = INT_MAX; if (ql <= mid) { result = min(result, queryMinKSum(node * 2, l, mid, ql, min(qr, mid))); } if (qr > mid) { result = min(result, queryMinKSum(node * 2 + 1, mid + 1, r, max(ql, mid + 1), qr)); } if (ql <= mid && qr > mid) { int leftStart = max(ql, mid - k + 2); int rightEnd = min(qr, mid + k - 1); for (int start = leftStart; start <= mid; start++) { int end = start + k - 1; if (end <= qr && end >= ql + k - 1) { result = min(result, querySum(start, end)); } } } return result; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, K, L; cin >> N >> K >> L; vector<int> arr(N + 1); for (int i = 1; i <= N; i++) { cin >> arr[i]; } SegmentTree segTree(N, K, arr); for (int i = 0; i < L; i++) { string cmd; int x, y; cin >> cmd >> x >> y; if (cmd == "Add") { segTree.update(1, 1, N, x, y); } else if (cmd == "Sub") { segTree.update(1, 1, N, x, -y); } else if (cmd == "Query") { int result = segTree.queryMinKSum(1, 1, N, x, y - K + 1); cout << result << "\n"; } } return 0; }

JavaScript实现

javascript

const readline = require('readline'); class SegmentTree { constructor(n, k, arr) { this.n = n; this.k = k; this.sum = new Array(4 * n).fill(0); this.minKSum = new Array(4 * n).fill(Infinity); this.build(1, 1, n, arr); } build(node, l, r, arr) { if (l === r) { this.sum[node] = arr[l]; this.minKSum[node] = (this.k === 1) ? arr[l] : Infinity; return; } const mid = Math.floor((l + r) / 2); this.build(node * 2, l, mid, arr); this.build(node * 2 + 1, mid + 1, r, arr); this.sum[node] = this.sum[node * 2] + this.sum[node * 2 + 1]; if (r - l + 1 >= this.k) { this.minKSum[node] = Math.min(this.minKSum[node * 2], this.minKSum[node * 2 + 1]); if (mid - l + 1 >= this.k - (r - mid)) { const leftStart = Math.max(l, mid - this.k + 2); for (let start = leftStart; start <= mid; start++) { const end = start + this.k - 1; if (end <= r) { this.minKSum[node] = Math.min(this.minKSum[node], this._querySum(start, end)); } } } } else { this.minKSum[node] = Infinity; } } update(node, l, r, idx, delta) { if (l === r) { this.sum[node] += delta; if (this.k === 1) { this.minKSum[node] = this.sum[node]; } return; } const mid = Math.floor((l + r) / 2); if (idx <= mid) { this.update(node * 2, l, mid, idx, delta); } else { this.update(node * 2 + 1, mid + 1, r, idx, delta); } this.sum[node] = this.sum[node * 2] + this.sum[node * 2 + 1]; if (r - l + 1 >= this.k) { this.minKSum[node] = Math.min(this.minKSum[node * 2], this.minKSum[node * 2 + 1]); if (mid - l + 1 >= this.k - (r - mid)) { const leftStart = Math.max(l, mid - this.k + 2); for (let start = leftStart; start <= mid; start++) { const end = start + this.k - 1; if (end <= r) { this.minKSum[node] = Math.min(this.minKSum[node], this._querySum(start, end)); } } } } else { this.minKSum[node] = Infinity; } } queryMinKSum(node, l, r, ql, qr) { if (ql > qr || r - l + 1 < this.k) { return Infinity; } if (ql <= l && r <= qr) { if (r - l + 1 >= this.k) { return this.minKSum[node]; } return Infinity; } const mid = Math.floor((l + r) / 2); let result = Infinity; if (ql <= mid) { result = Math.min(result, this.queryMinKSum(node * 2, l, mid, ql, Math.min(qr, mid))); } if (qr > mid) { result = Math.min(result, this.queryMinKSum(node * 2 + 1, mid + 1, r, Math.max(ql, mid + 1), qr)); } if (ql <= mid && qr > mid) { const leftStart = Math.max(ql, mid - this.k + 2); const rightEnd = Math.min(qr, mid + this.k - 1); for (let start = leftStart; start <= mid; start++) { const end = start + this.k - 1; if (end <= qr && end >= ql + this.k - 1) { result = Math.min(result, this._querySum(start, end)); } } } return result; } _querySum(l, r) { return this._querySumHelper(1, 1, this.n, l, r); } _querySumHelper(node, l, r, ql, qr) { if (ql > qr) return 0; if (ql <= l && r <= qr) return this.sum[node]; const mid = Math.floor((l + r) / 2); let result = 0; if (ql <= mid) result += this._querySumHelper(node * 2, l, mid, ql, Math.min(qr, mid)); if (qr > mid) result += this._querySumHelper(node * 2 + 1, mid + 1, r, Math.max(ql, mid + 1), qr); return result; } } async function main() { const rl = readline.createInterface({ input: process.stdin, output: process.stdout }); const lines = []; for await (const line of rl) { lines.push(line); } const firstLine = lines[0].split(' ').map(Number); const N = firstLine[0]; const K = firstLine[1]; const L = firstLine[2]; const arr = [0]; lines[1].split(' ').forEach(val => arr.push(Number(val))); const segTree = new SegmentTree(N, K, arr); const results = []; for (let i = 0; i < L; i++) { const [cmd, xStr, yStr] = lines[2 + i].split(' '); const x = parseInt(xStr); const y = parseInt(yStr); if (cmd === "Add") { segTree.update(1, 1, N, x, y); } else if (cmd === "Sub") { segTree.update(1, 1, N, x, -y); } else if (cmd === "Query") { const result = segTree.queryMinKSum(1, 1, N, x, y - K + 1); results.push(result.toString()); } } console.log(results.join('\n')); rl.close(); } main().catch(console.error);

C实现

c

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <limits.h> #define min(a, b) ((a) < (b) ? (a) : (b)) #define max(a, b) ((a) > (b) ? (a) : (b)) typedef struct { int n, k; int* sum; int* minKSum; } SegmentTree; void build(SegmentTree* st, int node, int l, int r, int* arr) { if (l == r) { st->sum[node] = arr[l]; st->minKSum[node] = (st->k == 1) ? arr[l] : INT_MAX; return; } int mid = (l + r) / 2; build(st, node * 2, l, mid, arr); build(st, node * 2 + 1, mid + 1, r, arr); st->sum[node] = st->sum[node * 2] + st->sum[node * 2 + 1]; if (r - l + 1 >= st->k) { st->minKSum[node] = min(st->minKSum[node * 2], st->minKSum[node * 2 + 1]); if (mid - l + 1 >= st->k - (r - mid)) { int leftStart = max(l, mid - st->k + 2); for (int start = leftStart; start <= mid; start++) { int end = start + st->k - 1; if (end <= r) { // 计算区间和 int sum = 0; for (int i = start; i <= end; i++) { sum += arr[i]; } st->minKSum[node] = min(st->minKSum[node], sum); } } } } else { st->minKSum[node] = INT_MAX; } } SegmentTree* createSegmentTree(int n, int k, int* arr) { SegmentTree* st = (SegmentTree*)malloc(sizeof(SegmentTree)); st->n = n; st->k = k; st->sum = (int*)malloc(4 * n * sizeof(int)); st->minKSum = (int*)malloc(4 * n * sizeof(int)); // 初始化 for (int i = 0; i < 4 * n; i++) { st->sum[i] = 0; st->minKSum[i] = INT_MAX; } build(st, 1, 1, n, arr); return st; } int querySum(SegmentTree* st, int node, int l, int r, int ql, int qr) { if (ql > qr) return 0; if (ql <= l && r <= qr) return st->sum[node]; int mid = (l + r) / 2; int result = 0; if (ql <= mid) result += querySum(st, node * 2, l, mid, ql, min(qr, mid)); if (qr > mid) result += querySum(st, node * 2 + 1, mid + 1, r, max(ql, mid + 1), qr); return result; } void update(SegmentTree* st, int node, int l, int r, int idx, int delta, int* arr) { if (l == r) { st->sum[node] += delta; arr[l] += delta; if (st->k == 1) { st->minKSum[node] = st->sum[node]; } return; } int mid = (l + r) / 2; if (idx <= mid) { update(st, node * 2, l, mid, idx, delta, arr); } else { update(st, node * 2 + 1, mid + 1, r, idx, delta, arr); } st->sum[node] = st->sum[node * 2] + st->sum[node * 2 + 1]; if (r - l + 1 >= st->k) { st->minKSum[node] = min(st->minKSum[node * 2], st->minKSum[node * 2 + 1]); if (mid - l + 1 >= st->k - (r - mid)) { int leftStart = max(l, mid - st->k + 2); for (int start = leftStart; start <= mid; start++) { int end = start + st->k - 1; if (end <= r) { int sum = 0; for (int i = start; i <= end; i++) { sum += arr[i]; } st->minKSum[node] = min(st->minKSum[node], sum); } } } } else { st->minKSum[node] = INT_MAX; } } int queryMinKSum(SegmentTree* st, int node, int l, int r, int ql, int qr, int* arr) { if (ql > qr || r - l + 1 < st->k) { return INT_MAX; } if (ql <= l && r <= qr) { if (r - l + 1 >= st->k) { return st->minKSum[node]; } return INT_MAX; } int mid = (l + r) / 2; int result = INT_MAX; if (ql <= mid) { result = min(result, queryMinKSum(st, node * 2, l, mid, ql, min(qr, mid), arr)); } if (qr > mid) { result = min(result, queryMinKSum(st, node * 2 + 1, mid + 1, r, max(ql, mid + 1), qr, arr)); } if (ql <= mid && qr > mid) { int leftStart = max(ql, mid - st->k + 2); int rightEnd = min(qr, mid + st->k - 1); for (int start = leftStart; start <= mid; start++) { int end = start + st->k - 1; if (end <= qr && end >= ql + st->k - 1) { int sum = 0; for (int i = start; i <= end; i++) { sum += arr[i]; } result = min(result, sum); } } } return result; } void freeSegmentTree(SegmentTree* st) { free(st->sum); free(st->minKSum); free(st); } int main() { int N, K, L; scanf("%d %d %d", &N, &K, &L); int* arr = (int*)malloc((N + 1) * sizeof(int)); for (int i = 1; i <= N; i++) { scanf("%d", &arr[i]); } SegmentTree* st = createSegmentTree(N, K, arr); for (int i = 0; i < L; i++) { char cmd[10]; int x, y; scanf("%s %d %d", cmd, &x, &y); if (strcmp(cmd, "Add") == 0) { update(st, 1, 1, N, x, y, arr); } else if (strcmp(cmd, "Sub") == 0) { update(st, 1, 1, N, x, -y, arr); } else if (strcmp(cmd, "Query") == 0) { int result = queryMinKSum(st, 1, 1, N, x, y - K + 1, arr); printf("%d\n", result); } } free(arr); freeSegmentTree(st); return 0; }

Read more

《算法闯关指南：优选算法--模拟》--43.数青蛙

《算法闯关指南：优选算法--模拟》--43.数青蛙

🔥草莓熊Lotso：个人主页 ❄️个人专栏: 《C++知识分享》《Linux 入门到实践：零基础也能懂》 ✨生活是默默的坚持，毅力是永久的享受！ 🎬 博主简介： 文章目录 * 前言： * 43. 数青蛙 * 解法（模拟+分情况讨论）： * 算法思路： * C++算法代码： * 算法总结&&笔记展示： * 结尾： 前言： 聚焦算法题实战，系统讲解三大核心板块：优选算法：剖析动态规划、二分法等高效策略，学会寻找“最优解”。 递归与回溯：掌握问题分解与状态回退，攻克组合、排列等难题。 贪心算法：理解“局部最优”到“全局最优”的思路，解决区间调度等问题 内容以题带点，讲解思路与代码实现，帮助大家快速提升代码能力。 43. 数青蛙

By Ne0inhk
【LeetCode_206】反转链表

【LeetCode_206】反转链表

刷爆LeetCode系列 * LeetCode第206题：反转链表 * github地址 * 前言 * 题目描述 * 题目与思路分析 * 思路一：反转链表的指针指向 * 思路二：取链表的结点，头插到新链表中 * 代码实现 * 思路一：反转指针指向 * 以下两种写法是保存curNext指针的方式不同 * 思路二：取原链表中的节点，头插到新链表 * 试错代码 * 算法代码优化 * 思路一优化： LeetCode第206题：反转链表 github地址 有梦想的电信狗 前言 本文用C++实现LeetCode第206题：反转链表 题目描述 * 题目链接：https://leetcode-cn.com/problems/reverse-linked-list/description/ 题目与思路分析 目标分析： 1. 有单链表的头节点 head ，反转原链表 2. 返回反转后的链表的头指针 3. 提高要求：时间复杂度为O(n)

By Ne0inhk
《链表面试基础看点：这里不止“快慢指针”的完美实现，更懂“哨兵节点”的巧妙运用》

《链表面试基础看点：这里不止“快慢指针”的完美实现，更懂“哨兵节点”的巧妙运用》

🔥@晨非辰Tong：个人主页  👀专栏：《C语言》、《数据结构与算法》、《数据结构与算法刷题集》 💪学习阶段：C语言、数据结构与算法初学者 ⏳“人理解迭代，神理解递归。” 引言：链表刷题进行时。寻找中间结点，看似简单，但你的解法是否考虑了所有边界情况？本文手把手带你用“快慢指针”写出完美解，以及“哨兵节点”对合并链表的简化实现。 目录 1.  876. 链表的中间结点 - 力扣（LeetCode）（快慢指针） 2.  21. 合并两个有序链表 - 力扣（LeetCode） 1.  876. 链表的中间结点 - 力扣（LeetCode）（快慢指针） 方法一：遍历链表计算总大小，算出mid，将首节点指针向后mid个节点。（容易想到） 方法二：使用快、

By Ne0inhk