VScode安装c++竞赛环境（2025）2025年3月10日更新powershell中文UTF8乱码问题看前须知本文章同时结合了Clang++的编译器优势和UCRT的运行时兼容性，使用URCT64的运行时环境和基本工具链，加上Clang/Clang++编译器和LLDB调试器，打造现代化的C++单文件编译环境。本文面向的对象：竞赛，如ACM/OI（CSP）/蓝桥杯等单文件、单线程编译运行c++的情况；或刚上手需要安装c/c++环境的新手同志们本文操作系统：Windows 11 23H2专业工作站版（所有64位的win11、win10系统都可使用)本文章解决问题：为什么我的vscode无法运行c++？0.在开始之前的操作在开始之前，请你在此电脑页面中查看标签下确保你勾选了文件扩展名与隐藏的项目下面分别是win11和win10启用的方法安装vscodevscode在官网上可以下载：https://code.visualstudio.com/1.了解c++编译器并安装MSYS2你需要知道一个c++文件是如何才能在你的电脑中运行的：你写的是文本，而只有二进制才能运行。所以所谓的"编译器"就是解决将文本变成可执行文件的一个工具。vscode并不是一个IDE(集成开发环境)，它就是一个可以安装插件的可扩展文本编辑器。也就是说，你如果不装编译器，你的vscode是无法解决编译问题的。所以，我们当务之急是需要安装一个编译器，让c++能被编译运行什么是MSYS2？为什么要安装MYSY2？msys2打包了包括mingw在内的一大堆函数库包括gcc,g++,clang,clang++等众多编译器，以及多种shell乃至模拟了个Unix-like 环境MSYS2（Minimal System 2）是一个为Windows操作系统设计的软件开发环境，它提供了一个模拟类Unix系统的命令行界面以及一系列工具和库。MSYS2是MSYS的独立改写版本，基于现代Cygwin和MinGW-w64，提供了更多的API支持和64位应用开发能力ucrt64 是 MSYS2 提供的一种开发环境，它是基于 Windows Universal CRT（通用运行时库）的 64 位开发环境。事实上，我们安装的MSYS2只是一个壳子，而内部我们会按需安装。本次安装我们以ucrt64作为基底开发环境，选择mingw-w64-ucrt-x86_64工具箱，使用clang/clang++作为编译器，使用LLDB作为debug调试器。下载并安装MSYS2可以在https://www.msys2.org/ 直接进行下载但如果下载速度过慢，则可以在镜像网站中进行下载https://mirrors.tuna.tsinghua.edu.cn/msys2/distrib/x86_64/注意需要拉到网页最底下，可以找到最新日期的安装包双击打开文件，重复点击Next>按钮，直至安装完成，在安装时会卡在50%,你这个时候可以等它8-10分钟请注意这里的重要操作！！！（重点）MSYS2跳过卡顿安装点"Show Details"，展开安装列表，当你发现下面这句话==> Updating trust database...出现时，连续按两下Cancle并打开任务管理器结束他的进程，并再次打开安装包重新安装，就可以快速安装完成经过比较，这种操作和等待安装后的文件是一样的，但是跳过以后可以节省大量时间安装完成后，自动会弹出msys2的界面，如果不小心关掉也没关系，我们可以在默认安装路径C:\msys64下找到它并打开小贴士：可以复制后，右键黑框，选择Paste粘贴命令双击后出现黑框，我们在里面输入以下命令：sed -i "s#https\?://mirror.msys2.org/#https://mirrors.tuna.tsinghua.edu.cn/msys2/#g" /etc/pacman.d/mirrorlist* pacman -Syu这两句话分别是为了配置镜像，使得下载速度更快。以及更新msys2系统安装MYSY2中urct64环境的clang/LLDB包执行完pacman -Syu后，程序会退出，我们重新打开黑框，然后输入下面的命令安装包含clang/clang++编译器的整个工具，以及LLDB调试器pacman -S mingw-w64-ucrt-x86_64-clang mingw-w64-ucrt-x86_64-lldb安装mingw-w64-ucrt-x86_64-toolchain工具链，是UCRT的运行时环境，同时也包含了基础的GCC/G++pacman -S --needed base-devel mingw-w64-ucrt-x86_64-toolchain安装额外的clang工具箱pacman -S mingw-w64-ucrt-x86_64-clang-tools-extra按回车确认列表接着在:: Proceed with installation? [Y/n]出现数，输入y即可确认进行，最后和图一样即可这样就安装好clang环境了配置环境变量选择环境变量、双击Path所在行、点击新建、在空白行中加入C:\msys64\ucrt64\bin按windows徽标键，输入cmd，然后输入clang -v以及clang++ -v，如果能显示以下信息，说明安装完成2.配置vscode必装三大插件：LSP、快速编译运行、可视化调试代码注意！！如果clangd弹出下载lib库，或者代码提示没有运行，请看关于clangd无法被识别的问题是如何解决的如果使用clang++开发套件，那么必须的三大件是：clangd：Clangd 是一个基于 Clang 编译器的 Language Server Protocol (LSP) 实现，用于为各种代码编辑器提供智能的 C/C++ 编程支持。它通过 LSP 协议与编辑器通信，提供代码补全、语法检查、代码导航、代码格式化、代码重构等功能。简而言之，Clangd 是一个强大的工具，可以显著提升 C/C++ 开发体验。CodeRunner用于一键生成命令编译运行CodeLLDB可用GUI来Debug调试代码（注：若使用g++来编译运行，则需要额外的配置）.在.vscode目录下新建三个文件并放入CodeLLDB下载失败，但是又没有”魔法“的解决方案通过镜像加速站 https://github.moeyy.xyz/ ，输入这个链接，然后就可以下载了通过VSIX安装，然后选择刚才的文件即可请注意这三个文件只对当前工作区生效（即用vscode打开的当前文件夹）。settings.json用于配置code-runner，实质上code-runner就是将手打的编译命令clang++ test.cpp -o test.exe一键生成并执行，实质上并没有什么神奇的 。launch.json是用codeLLDB生成后修改的，主要是用于断点调试。tasks.json主要用于，在调试前自动编译运行一个新文件，其实就是预处理settings.json{ //规定clangd的位置，这是解决clangd无法被识别的最终方案 "clangd.path": "C:\\msys64\\ucrt64\\bin\\clangd.exe", "clangd.arguments": [ //如果使用万能头文件，可以屏蔽掉插入头文件的操作 //"--header-insertion=never", ], //cph和浏览器插件联动的效果 // "cph.general.defaultLanguage": "cpp", // "cph.language.cpp.SubmissionCompiler": "GNU G++14 6.4.0", // 使用 C++14 标准 // "cph.language.cpp.Args": "-std=c++14 -O2", // -O2 //这里规定了CodeRunner一键生成的命令 "code-runner.executorMap": { //这里默认c++文件用c++14标准编译，可以自己选是什么版本的，如果要c++23，那么就写-std=c++23即可 //"cpp": "cd $dir && clang++ $fileName -o $fileNameWithoutExt && $dir$fileNameWithoutExt", "cpp": "cd $dir && clang++ -std=c++14 $fileName -o $fileNameWithoutExt && $dir$fileNameWithoutExt", "c": "cd $dir && clang $fileName -o $fileNameWithoutExt && $dir$fileNameWithoutExt", "python": "python -u", }, //这两行分别是指示代码和终端的字体大小 "editor.fontSize": 22, "terminal.integrated.fontSize": 20, "code-runner.runInTerminal": true, //是否在终端中运行，选择是 //下面是美化功能，美化完以后可以使用 // "editor.mouseWheelZoom": false, //是否可以让代码字体用CTRL+滚轮进行缩放，true就是可以 // "terminal.integrated.mouseWheelZoom": true, //是否可以让终端字体用CTRL+滚轮进行缩放，true就是可以 // "terminal.integrated.fontFamily": "CaskaydiaMono Nerd Font", //重要！！请和你刚才设置的字体一致 // "terminal.integrated.defaultProfile.windows": "PowerShell", //选择默认哪个终端打开编译 }注意launch.json和tasks.json是配套的launch.json{ "version": "0.2.0", "configurations": [ { "name": "clang++ build and debug active file", "type": "lldb", "request": "launch", //fileBasenameNoExtension表示当前打开的文件的文件名，但不包括文件扩展名 //例如，如果当前打开的文件是 example.cpp，那么 fileBasenameNoExtension 的值将是 example "program": "${fileDirname}/${fileBasenameNoExtension}.exe", "args": [], //cwd用于指定当前工作目录 //如果当前打开的是一个文件夹，${workspaceFolder} 就是这个文件夹的路径 "cwd": "${workspaceFolder}", "preLaunchTask": "clang++ build" //这个名字需要和tasks.json的label名一致 } ] }tasks.json{ "version": "2.0.0", "tasks": [ { //这个名字需要和launch.json的preLaunchTask名一致 "label": "clang++ build", "type": "shell", "command": "clang++", //使用什么命令 //命令的参数 "args": [ "-std=c++14", // 指定 C++14 标准，可以自己选是什么版本的，如果要c++23，那么就写-std=c++23即可 "-Wall", // 打开所有警告 "${fileDirname}\\${fileBasename}", //源文件名,在工作区的任何文件夹中都能使用 "-o", // 编译输出 "${fileDirname}\\${fileBasenameNoExtension}.exe", //输出名，在工作区的任何文件夹中都能使用 "-g" // 带调试信息 ], //下面参数对于单文件意义不大 "group": { //表示这个任务属于 构建组（build group）。构建组的任务通常用于编译或构建项目。 "kind": "build", //表示这个任务是其所属组（这里是 build 组）的 默认任务。 "isDefault": true } } ] }此时，已经安装完成，我们可以按快捷键CTRL+ALT+N进行CodeRunner的运行关于clangd无法被识别的问题是如何解决的在settings.json中强制规定clangd的位置，这个方法百分百奏效//规定clangd的位置 "clangd.path": "C:\\msys64\\ucrt64\\bin\\clangd.exe", "clangd.arguments": [ //如果使用万能头文件，可以屏蔽掉插入头文件的操作 //"--header-insertion=never", ], //这里规定了CodeRunner一键生成的命令 "code-runner.executorMap": { //这里默认c++文件用c++14标准编译，可以自己选是什么版本的，如果要c++23，那么就写-std=c++23即可 //"cpp": "cd $dir && clang++ $fileName -o $fileNameWithoutExt && $dir$fileNameWithoutExt", "cpp": "cd $dir && clang++ -std=c++14 $fileName -o $fileNameWithoutExt && $dir$fileNameWithoutExt", "c": "cd $dir && clang $fileName -o $fileNameWithoutExt && $dir$fileNameWithoutExt", "python": "python -u", },使用PowerShell7的运行效果设置断点，按F5即可进行调试，按F9单步调试两次后效果如下：可选插件1.CPH编程竞赛扩展工具Competitive Programming Helper (CPH) 是一款专为编程竞赛设计的 Visual Studio Code (VS Code) 扩展工具，旨在帮助参赛者更高效地进行竞赛编程。主要功能：快速编译、运行和评判：CPH 允许用户在 VS Code 内快速编译、运行代码，并对竞赛题目进行评判。自动下载测试用例：通过与 Competitive Companion 浏览器扩展配合使用，CPH 可以自动从竞赛平台（如 Codeforces、Codechef、TopCoder 等）下载测试用例。本地测试与提交：用户可以在本地编写和测试自己的问题，并通过 CPH 直接提交解决方案。支持多种编程语言：CPH 支持 C++、C、Rust、Python、Java 等多种编程语言3.美化终端3.1安装PowerShell7众所周知，windows自带的PowerShell是旧版的还有广告，如果要一个强大的命令行终端，那么PowerShell的最新版就是最好的选择。在 https://github.com/PowerShell/PowerShell/releases/ 下载最新版powershell7并安装如果无法下载，可以在微软商店（MicroSoft Store）中下载无脑下一步安装完毕，进入cmd后右键边框，选择设置，将安装后的PowerShell7作为首选项关于powershell7中文乱码问题解决方案可以修改 PowerShell 的配置文件，让每次启动 PowerShell 时都自动将编码设置为 UTF - 8。创建配置文件路径：在 PowerShell 7 终端中运行以下命令来操作：如果没有配置文件，那么新建配置文件if (!(Test-Path -Path $PROFILE)) { New-Item -ItemType File -Path $PROFILE -Force }notepad $PROFILE加入下面的文本#修改UTF8编码 $OutputEncoding = [System.Text.Encoding]::UTF8 [console]::InputEncoding = [System.Text.Encoding]::UTF8 [console]::OutputEncoding = [System.Text.Encoding]::UTF83.2安装oh-my-poshOh My Posh 是一个跨平台、高度可定制的终端提示符引擎，支持多种 Shell 环境，包括 PowerShell、bash、zsh 等。它可以让终端的提示符更加美观和实用，同时提供丰富的自定义选项下载地址：https://github.com/JanDeDobbeleer/oh-my-posh/releases如果无法下载，可以在微软商店（MicroSoft Store)中下载无脑下一步，安装成功后可以在powershell7中输入oh-my-posh，显示下面信息代表安装成功3.3在PowerShell7中使用oh-my-posh1.如果没有配置文件，那么新建配置文件（如果之前修复了UTF8编码问题这句话就没什么必要）if (!(Test-Path -Path $PROFILE)) { New-Item -ItemType File -Path $PROFILE -Force }2.用记事本打开配置文件(下面都指的是这个打开的配置文件)notepad $PROFILE3.在打开的文件中加入下面这句话oh-my-posh init pwsh | Invoke-Expression4.输入下面这句话，查看所有可以用的皮肤Get-PoshThemes5.在配置文件中修改原来的oh-my-posh init pwsh | Invoke-Expression，把这句话替换成下面的。其中montys.omp.json是你在皮肤里面选择的一个喜欢的名字oh-my-posh init pwsh --config "$env:POSH_THEMES_PATH\montys.omp.json" | Invoke-Expression6.安装windows文件夹等徽标（可选）Install-Module -Name Terminal-Icons -Repository PSGallery然后在配置文件中加入：Import-Module Terminal-Icons最后配置状态如下：打开PowerShell7，此时会出现下面这样的乱码情况，这是因为皮肤里面的图标需要特殊字体解决图标乱码：下载和配置Nerd字体Nerd Fonts 是一个开源项目，旨在为开发者提供带有大量图标和符号的字体集合。这些字体通过集成来自流行图标集（如 Font Awesome、Devicons、Octicons 等）的额外图标，增强了传统编程字体的功能。https://www.nerdfonts.com/font-downloads 在这里下载你喜欢的字体我选择的是CaskaydiaMono Nerd Font打开压缩包，将所有TTF文件解压缩到C:\Windows\Fonts文件夹下同样的，右键边框进入设置，选择刚才你下载的nerd字体，然后保存，重新打开PowerShell你会发现图标生成了。3.4在VScode中使用刚才调好的powershell7注意这里最关键的是"terminal.integrated.fontFamily": "CaskaydiaMono Nerd Font"，在这里必须填入刚才你选择的字体。"terminal.integrated.defaultProfile.windows": "PowerShell"是选择PowerShell7作为默认终端打开只需要将settings.json文件中修改成下面这个样子即可：{ //规定clangd的位置 "clangd.path": "C:\\msys64\\ucrt64\\bin\\clangd.exe", "clangd.arguments": [ //如果使用万能头文件，可以屏蔽掉插入头文件的操作 //"--header-insertion=never", ], //cph和浏览器插件联动的效果 // "cph.general.defaultLanguage": "cpp", // "cph.language.cpp.SubmissionCompiler": "GNU G++14 6.4.0", // 使用 C++14 标准 // "cph.language.cpp.Args": "-std=c++14 -O2", // -O2 //这里规定了CodeRunner一键生成的命令 "code-runner.executorMap": { //这里默认c++文件用c++14标准编译，不过可以自己选择是否加 -std=c++14，如果保持默认就用下面这句话 //"cpp": "cd $dir && clang++ $fileName -o $fileNameWithoutExt && $dir$fileNameWithoutExt", "cpp": "cd $dir && clang++ -std=c++14 $fileName -o $fileNameWithoutExt && $dir$fileNameWithoutExt", "c": "cd $dir && clang $fileName -o $fileNameWithoutExt && $dir$fileNameWithoutExt", "python": "python -u", }, //这两行分别是指示代码和终端的字体大小 "editor.fontSize": 22, "terminal.integrated.fontSize": 20, "code-runner.runInTerminal": true, //是否在终端中运行，选择是 "editor.mouseWheelZoom": false, //是否可以让代码字体用CTRL+滚轮进行缩放，true就是可以 "terminal.integrated.mouseWheelZoom": true, //是否可以让终端字体用CTRL+滚轮进行缩放，true就是可以 "terminal.integrated.fontFamily": "CaskaydiaMono Nerd Font", //重要！！请和你刚才设置的字体一致 "terminal.integrated.defaultProfile.windows": "PowerShell", //选择默认哪个终端打开编译 }最后测试效果如下：3.5其他功能性插件1.PSReadLinePSReadLine 提供语法高亮、错误提示、多行编辑、键绑定、历史记录搜索等功能，提升命令行体验。Install-Module PSReadLine2.posh-gitposh-git 可以在 PowerShell 中显示 Git 状态信息，并提供 Git 命令的自动补全。Install-Module posh-git在 PowerShell 配置文件 ($PROFILE) 中添加以下行以启用该插件：Import-Module posh-git3.ZLocationZLocation 插件类似于 autojump 或 Zsh-z，通过关键字直接跳转到指定目录，提升效率。安装 ZLocation 插件：Install-Module ZLocation修改配置文件：打开 PowerShell 配置文件：notepad $PROFILE在文件末尾添加：Import-Module ZLocation3.6最终powershell配置# 引入所需模块 Import-Module Terminal-Icons Import-Module PSReadLine Import-Module posh-git Import-Module ZLocation # 初始化 oh-my-posh oh-my-posh init pwsh --config "$env:POSH_THEMES_PATH\montys.omp.json" | Invoke-Expression #修改UTF8编码 $OutputEncoding = [System.Text.Encoding]::UTF8 [console]::InputEncoding = [System.Text.Encoding]::UTF8 [console]::OutputEncoding = [System.Text.Encoding]::UTF8
速通线段树（入门）2023年3月15日第6次修订本内容必要条件：看懂代码的必要条件：c++的基本语法（数组、函数调用、结构体、输入输出）掌握逻辑的必要条件：掌握递归算法思想（不会的我无法保证你能看懂）warning-警告！！！ warning-警告！！！ warning-警告！！！（一）如果你没有了解过递归，我无法保证你能完全看懂本文。如果你执意学习，请做好可能失败的心理准备。（二）如果你没有学过C++基本语法（但是学过其他语言，也了解过递归），请翻阅下去，本文不会让你后悔。作者也是JAVA出身。作者保证你可以看懂除代码外的其它内容。如果你没有了解过递归，请至少学习斐波那契数列的递归实现或汉诺塔的递归（或者其它简单递归）的实现后再来观看！谢谢您的配合！如果你没有了解过递归，请至少学习斐波那契数列的递归实现或汉诺塔的递归（或者其它简单递归）的实现后再来观看！谢谢您的配合！如果你没有了解过递归，请至少学习斐波那契数列的递归实现或汉诺塔的递归（或者其它简单递归）的实现后再来观看！谢谢您的配合！非必要条件：会堆（Heap）这个数据结构（可以帮助你更快速入门）读者若是不会堆，作者也保证你可以看懂线段树0.观前提醒：递归和堆结构是递归且非动态开点的线段树的必要组成本文只教授递归式且非动态开点的线段树递归式线段树堆（Heap）式的、且空间以及开辟完成的、采用数组模拟内存的线段树如果你不会堆，本文可以保证你可以看懂。1.（重点）抓住线段树的精髓：维护区间信息线段树是一个数据结构区间信息：数据离散化（数据索引是有限的）成一条直线（数组），上面截出一段（数组的一部分）的信息（区间和，区间平方差和，最大最小值，异或值……）维护：如果你改了上面的一些数据，它仍然可以帮你查询出来请仔细理解维护区间信息这个内容，并牢记于心，仔细体会2.如何实现维护区间信息（思想）2.1.线段树的结构观前提醒：如果你是新手，在看这一节（2.1节）的时候，请你把大脑中“这个用代码怎么实现？”这种问题清除掉，我们只关注结构本身。请牢记：开始的时候，走的稳、走的慢，最后才能走的远。假设我们有以下的区间信息（下标从1到8一共8个内容），内容是随便取的不用纠结，因为下面用不到它线段树的做法利用分而治之的思想，将1-8的区间信息放入一个格子中，然后将其分成两段（其实是有多段实现的，但是我们只学习最基础的两段式）我们将顶点1-4和5-8的区间信息分开存储，周而复始，依次往下1-4分成1-2和3-4，5-8分成5-6和7-8，以此类推如果你无法理解什么是区间信息的话，你可以举例（假装）为这些格子的数字之和（假装现在区间信息就是这些数字之和）其实区间信息有很多种，我在第一节中就列出来了一些（区间和，区间平方差和，最大最小值，异或值……）（如果你没有好好看，请你回过去再仔细体会一下维护区间信息这个精髓说法）一图胜千言：你可能非常容易就发现了最底下的格子颜色与上面的不一样，因为他们是最小区间单位（也就是只存储一个格子的信息，所谓的2-2就是2到2，那就是2这个格子本身）。那么到此为止，读者肯定发现了一个问题：为什么我刚好选的是8，刚好是2的幂次？原因是这样好画，但是这不是问题的答案。因为我们必须也应该知道，不是2的倍数，不是2的幂次时线段树该如何建立譬如1到7时，我们该怎么建立呢？一般是向下取整建立分段（即7整除2答案为3，你可以理解为把余数全部去除）区间1-3分成1-2和1-1，区间4-7分成4-5和6-7（4加7是11，11整除2是5，所以以5位分界点）所以这样建立的图如下所示：2.1练习：绘画1-11的线段树大家可以在纸上自己绘画1-11的线段树区间信息段，然后与我的数据对照，重点关注绿色的最小区间单位节点是什么地方至此为止，其实你已经学了一半的线段树了，也就是线段树的数据存储方式（怎么画出线段树，每个格子是什么意思）作者这里想说一些话：假设不涉及代码，我们也可以画出线段树的格子，不是吗？代码固然重要，但是思路在其中占比至少也是50%如果你是初学者，画出了格子，那么你已经成功百分之50了。有些东西没有想象的那么难。2.2.核心思想一：儿子与父亲的关系从2.2开始，我们慢慢铺垫如何用代码实现，稍安勿躁。（也不会出现很多代码）如果你没有学过二叉树（Binary-Tree）和堆（Heap），那么可以仔细看看下面的内容。儿子和父亲是相对关系，上面的是父亲，下面的是儿子。树上的每一个格子我们称为结点请注意：儿子和父亲是一层之内的相对关系，儿子分左右，父亲只有一个，请对照下面的图进行理解（重点）堆(Heap)的结点编号系统我们接下来要干一个非常重要的事情：对每个结点进行编号，也是堆的核心思想。请仔细观察每个儿子与父亲编号的关系！！我们可以得出以下结论：所有的左儿子的编号是它父亲编号的两倍所有的右儿子的编号是它父亲编号的两倍加一所有的父亲的编号是任意一个儿子的编号整除二先从左往右，再从上往下，我们可以发现编号刚好是顺序的1到161到3毋庸置疑，4可以得出一个非常爆炸的结论：我们可以将这颗树按照顺序存入一个数组中。存入数组后，这棵树的父亲和儿子关系可以通过编号的乘法和除法得到聪明的读者肯定发现了一个问题：你这不对啊，那我刚刚1-11的那颗树不是还有空着的地方吗，那怎么存？我的回答是：建立空节点，缺多少，塞多少，全部塞满，直接塞成$ 2^n - 1$个结点就行了，（NULL就是空节点）本节核心：成功使用数组的形式解决了存储树的问题。2.3.核心思想二：递归建立（build）线段树递归的本质是：函数的自调用这里想问问大家：函数自调用的核心是什么？我的回答是：递归出口（即停止递归的条件）。一个递归如果没有出口，那么它会无限调用自己，然后爆栈（Stack Overflow）函数自调用的秘诀是什么？build() { ---------- if（） return； -----递归出口可以出现在拿资源之前的任何地方，但是必须出现，否则无法停止。可以有多个递归出口 操作已经有的资源 ====调用前==== ----让我的儿子（下属，奴仆）去拿资源 build() ====调用后==== ----这个时候已经拿到了想要的资源了 整合资源 }操作已经有的资源，做准备工作（调用前）找到还缺少的资源，让我的儿子去拿资源（调用函数Call）儿子拿到我要的资源，我就整合所有资源（调用后）以线段1-8为例，向大家展示整个调用过程使用《》来代表图中的箭头，使用【】代表图中的结点，重要位置我会用下划线标注《箭头1》调用函数Build()【1号点】：我没有区间1到8的信息《箭头2》【1号点】：调用函数Build()，指向【2号点】【2号点】我没有区间1到4的信息《箭头3》【2号点】：调用函数Build()，指向【4号点】【4号点】我没有区间1到2的信息《箭头4》【4号点】：调用函数Build()，指向【8号点】【8号点】：我拥有区间1到1的信息！！，退出递归，存储数据给【4号点】！《箭头5》【4号点】：调用函数Build()，指向【9号点】【9号点】：我拥有区间2到2的信息！！，退出递归，存储数据给【4号点】！【4号点】：我拥有了区间1到2的信息!!退出递归，存储数据给【2号点】！《箭头6》【2号点】：调用函数Build()，指向【5号点】【5号点】：我没有区间3到4的信息《箭头7》【5号点】：调用函数Build()，指向【10号点】【10号点】：我拥有区间3到3的信息！！，退出递归，存储数据给【5号点】！《箭头8》【5号点】：调用函数Build()，指向【11号点】【11号点】：我拥有区间4到4的信息！！，退出递归，存储数据给【5号点】！【5号点】：我拥有了区间3到4的信息!!退出递归，存储数据给【2号点】！【2号点】：我拥有了区间5到8的信息!!退出递归，存储数据给【1号点】！《箭头9》【1号点】：调用函数Build()，指向【3号点】【3号点】：我没有区间5到8的信息----------过程略…………………………【3号点】：我拥有了区间5到8的信息!!退出递归，存储数据给【1号点】！【1号点】：我已经有区间1到8的信息了！退出递归！完成最终函数！线段树建立完成！！！！线段树建立完成！！！！线段树建立完成！！！！粗略计算一下建立线段树需要多少时间复杂度假设数据量是N，假设所有叶子结点（最底下这层区间只有自己的点）都充满，最多的时间也不过2N（满二叉树的叶子结点是所有结点数量的一半+1，所以剩余的结点数不会超过叶子结点）所以建立线段树是线性复杂度O(N），虽然是递归实现的2.4.核心思想三：递归修改（modify）线段树我们知道，线段树的核心是维护区间信息，刚才我们已经初始化了区间信息，是否能用原来的方法实现修改呢？正所谓天上没有掉下来的馅饼，世界上哪有这么好的事情呢？假设我们要修改区间4-7（譬如每一个点上都加上3），那么紫色结点就是我们最终要到达的地方，蓝色结点是走过的地方。你会发现一个严重的问题：我这要跑的次数也太多了吧如果在大量的修改下，每一次都是近乎N的数据量。假设有M次修改，我的时间复杂度就约等于N*M如果是10000的数据量和10000次查询，那就是1亿的数据量！！（一般100万数据需要0.1s（0.1秒），1000万就是1s（秒））只有10000的数据量就导致了时间近乎10秒以上，这是令人无法接受的，所以要引出线段树的核心中的核心最最最重点部分：懒加载（lazy-load）其实用一句话概括这个神奇的算法就是：用的时候才给你，不用的时候就欺上瞒下什么意思呢？什么叫做懒加载呢？假设我们要修改区间信息5-8（比如每个都加上3）此时递归进行到5-8，你会发现整个区间都落在了5-8，那么我们修改完后递归上去，让1-8这个节点也修改也就是说此时你只有【区间信息5-8】和【区间信息1-8】是被修改的。然后你给【区间信息5-6】【区间信息7-8】打个标记，告诉他们这次我每个点加了多少，让他们记好。这个标签就是lazytag（你想叫啥都行啦，只是个名字，你叫他dog也没事）。也就是【区间信息5-8】欺上瞒下（其实没有瞒下）完成了修改。对于懒标记我们必须要了解这几个事实拥有懒标记的结点说明此前并没有查询到，需要激活懒标记来获得正确数据（如果这个操作不一样，那么代码也就不一样，有多种解释。可以跳转第四节观看详细解释。）激活懒标记后，应该将懒标记下放到两个儿子结点，儿子结点不会修改，只是添加了懒标记激活懒标记后，数据更改，懒标记归回初始值（每个算法不一样，如果是加和，那么初始是0）拥有了懒加载后，我们需要激活（active）懒标记。如何激活懒标记接下来演示的两种情况是：父亲节点没有懒标记和原来已经有懒标记的两种情况首先看父节点的lazytag是初始值的情况接下来看看父节点本来就已经有lazytag的情况如何寻找区间并执行这里还有一个更加重要的问题，那就是如何寻找区间：哪些区间要打上标记，哪些区间是被查找到后就欺上瞒下直接返回消息的首先我们先给出最终结果：假设我们要查找4-7的时候，区间信息3-4 区间信息5-6 区间信息7-7这三块（红色部分）的就是最终欺上瞒下的部分他们的左右子树（黄色部分）就是打上懒标记的部分看到这个结果以后，我们必须要模拟出来具体寻找过程设我们修改的区间是L到R（如果是4到7，那么L就是4，R就是7）修改（modify）函数请严格遵循以下原则：无论如何，先判断自身是否拥有懒标记激活自己的懒标记，因为只有这样自己的值才是正确的将自己的懒标记下发左右子树，让他们获得自己当前懒标记初始化自身懒标记，回归原始状态当前的区间信息范围完全不在L到R之内时，我们直接返回（return）当前的区间信息范围完全在L到R之内时将自己的值直接修改完成将左右子树的懒标记改为自己需要修改的值返回(return)当前的区间信息范围部分落在L到R之内时，继续搜索左右子树（调用函数递归向下）读取左右子树已经更新过的信息，将自身信息更新，因为只有被查到的会有被修改，而父亲节点不会被修改关于2的说明：怎么样保证当前的区间信息范围完全不在L到R之内？【对于原则5的示意图片】：这些没有被修改的信息必须在子树修改完后，递归回去的路上被修复。2.5.核心思想四：递归查找（query）线段树其实递归查找的步骤就是递归修改的稍微改版而已。只是有一些些的不一样。这里我们直接给出递归查找的原则查询（query）函数请严格遵循以下原则：无论如何，先判断自身是否拥有懒标记激活自己的懒标记，因为只有这样自己的值才是正确的将自己的懒标记下发左右子树，让他们获得自己当前懒标记初始化自身懒标记，回归原始状态当前的区间信息范围完全不在L到R之内时，我们直接返回初始值（每个题不一样，如果是求和就返回0）（return 初始值）当前的区间信息范围完全在L到R之内时，我们直接返回这个结点的值（return 结点值）当前的区间信息范围部分落在L到R之内时，继续搜索左右子树（调用函数递归向下），并将其返回的内容进行处理请注意：我们这里不需要进行修改中的第5步：自身信息更新，因为查询的时候不会修改，那么原来的值就已经是最终值了，我们只需要激活懒标记就行了。而存在着lazytag值的父亲已经被变过了，否则这个结点也不可能有lazytag（它的lazytag是父亲给的，那么父亲已经被修改过了，是最终值了）请仔细理解以下的话，与修改的部分进行仔细对比，必须理解清楚再进入第三章存在着lazytag值的父亲已经被变过了激活懒标记只是为了让它回到正确的值，而不是它现在会被改变，是它曾经已经被改变过了别忘了激活懒标记后下放到左右子树还是以查询4-7为例，我们只需要激活lazytag和下放lazytag然后返回即可。3.如何用C++实现线段树（代码）3.1.线段树的结构体实现这里我使用了结构体，但是这个结构体完全可以拆成4个数组使用。使用结构体的目的是为了让思路更加清楚，将每一个线段树的结点封装成一个结构体类型抽象化，能更加容易写出代码线段树的每个结点至少包含四个东西区间信息的左起始点区间信息的右起始点当前结点的值当前结点的懒标记而且这样的结点是批量建立的数组形式（堆的形式）由于我们不用维护左右子树和父亲的关系（因为我们采用了堆的建法），所以不需要在结点内写明关系。我们只需要建立足够大的堆（数组）将结点依次存入即可，数组之间的下标就是他们之间的关系所以我们可以写出这样的结构体：struct Tree{ 左起始点 l 右起始点 r 值 ans 懒标记 lazy }数组名[数组大小];这里给出我的例子（以洛谷P3372 【模板】线段树 1为例）typedef long long LL; //将long long 类型定义为LL，后面使用LL就是使用long long 长整型 const int N = 2e5 + 10; //定义只读整型int，2e5是科学计数法 代表2 * 10^5，也就是20万。 最后加上5 就是 200005 struct Tree{ int l, r; LL ans, lazy; }tr[N << 2]; //N<<2 代表N位运算左移两位， 代表N乘以4 //tr代表结构体数组，存储树的每个结点信息，下标以1开始。 LL e[N << 2]; // 这里e存储的是原本的数据，下标以1开始。3.2.线段树的初始化建立假设我们的函数是buildvoid build(结点下标 x, 当前结点的左起始点 l, 当前结点的右起始点r) { tr[x].l = l; tr[x].r = l; //这一步是在利用递归函数初始化线段树每个结点的左右起始点（区间信息） if(l == r) { //当l==r的时候，说明这个结点已经到头了。区间只有一格这么大，所以我们存储值然后返回 存储tr[x]的值； return; } mid = (l + r) / 2; //找出当前结点的中间值，区分左右 build(x * 2, l, mid); //向左节点查询，范围是【l,mid】 build(x * 2 + 1, mid + 1, r); //向右节点查询，范围是【mid+1，r】 tr[x]的值 整合为 tr[x]左节点的值 与 tr[x]右节点的值的信息 }这里给出我的例子（以洛谷P3372 【模板】线段树 1为例）这里请注意：e[l]代表到了叶子结点时，它的左右起始点就代表了原数组的位置。（可以观察一下起始点和原数据的关系）void build(int x, int l, int r) { tr[x].l = l; tr[x].r = r; if(l == r) { tr[x].ans = e[l]; // 这里e存储的是原本的数据的数组。e[l]代表到了叶子结点时，它的左右起始点就代表了原数组的位置。 return; } int mid = (l + r) >> 1; // >>1 就是右移一位，位运算。相当于除以2 build(x << 1, l, mid); // << 1 就是左移一位，位运算。相当于乘以2 build(x << 1 | 1, mid + 1, r); // << 1 | 1 就是左移一位然后和1进行与运算，位运算。相当于乘以2加1 tr[x].ans = tr[x << 1].ans + tr[x << 1 | 1].ans; //这里是整合左右节点信息之和，因为题目就是信息之和 }3.3.线段树的修改修改（modify）函数请严格遵循以下原则：无论如何，先判断自身是否拥有懒标记激活自己的懒标记，因为只有这样自己的值才是正确的将自己的懒标记下发左右子树，让他们获得自己当前懒标记初始化自身懒标记，回归原始状态当前的区间信息范围完全不在L到R之内时，我们直接返回（return）当前的区间信息范围完全在L到R之内时将自己的值直接修改完成将左右子树的懒标记改为自己需要修改的值返回(return)当前的区间信息范围部分落在L到R之内时，继续搜索左右子树（调用函数递归向下）读取左右子树已经更新过的信息，将自身信息更新，因为只有被查到的会有被修改，而父亲节点不会被修改void modify(结点下标 x, 要修改的位置左起始点 l, 要修改的位置右起始点 r, 要修改的数据 k) { if(tr[x] 有懒标记) { 1. 激活自己的懒标记，因为只有这样自己的值才是正确的 2. 将自己的懒标记下发左右子树，让他们获得自己当前懒标记 3. 初始化自身懒标记，回归原始状态 } // 当前的区间信息范围完全不在L到R之内时，我们直接返回 if(tr[x].l > r || tr[x].r < l) return; // 当前的区间信息范围完全在L到R之内时 if(tr[x].l >= l && tr[x].r <= r) { 1. 将自己的值 直接修改完成 2. 将左右子树的懒标记改为 自己需要修改的值 return; } //当前的区间信息范围部分落在L到R之内时，继续搜索左右子树（调用函数递归向下） modify(x * 2, l, r, k); //向左节点查询 modify(x * 2 + 1, l, r, k); //向右节点查询 //读取左右子树已经更新过的信息，将自身信息更新 tr[x]的值 整合为 tr[x]左节点的值 与 tr[x]右节点的值的信息 }这里给出我的例子（以洛谷P3372 【模板】线段树 1为例）对于（tr[x].l > r || tr[x].r < l） 这个内容的解释，看下图所示void modify(int x, int l, int r, LL k) { if(tr[x].lazy) { //1. 激活自己的懒标记，因为只有这样自己的值才是正确的 tr[x].ans += (tr[x].r - tr[x].l + 1) * tr[x].lazy; //2. 将自己的懒标记下发左右子树，让他们获得自己当前懒标记 tr[x << 1].lazy += tr[x].lazy; tr[x << 1 | 1].lazy += tr[x].lazy; //3. 初始化自身懒标记，回归原始状态 tr[x].lazy = 0; } // 当前的区间信息范围完全不在L到R之内时，我们直接返回 // 这个内容可以直接看上图所示 if(tr[x].l > r || tr[x].r < l) return; // 当前的区间信息范围完全在L到R之内时 if(tr[x].l >= l && tr[x].r <= r) { //1. 将自己的值 直接修改完成 tr[x].ans += (tr[x].r - tr[x].l + 1) * k; // 2. 将左右子树的懒标记改为 自己需要修改的值 tr[x << 1].lazy += k; tr[x << 1 | 1].lazy += k; return; } //当前的区间信息范围部分落在L到R之内时，继续搜索左右子树（调用函数递归向下） modify(x << 1, l, r, k); modify(x << 1 | 1, l, r, k); //读取左右子树已经更新过的信息，将自身信息更新 tr[x].ans = tr[x << 1].ans + tr[x << 1 | 1].ans; }3.4.线段树的查询查询（query）函数请严格遵循以下原则：无论如何，先判断自身是否拥有懒标记激活自己的懒标记，因为只有这样自己的值才是正确的将自己的懒标记下发左右子树，让他们获得自己当前懒标记初始化自身懒标记，回归原始状态当前的区间信息范围完全不在L到R之内时，我们直接返回初始值（每个题不一样，如果是求和就返回0）（return 初始值）当前的区间信息范围完全在L到R之内时，我们直接返回这个结点的值（return 结点值）当前的区间信息范围部分落在L到R之内时，继续搜索左右子树（调用函数递归向下），并将其返回的内容进行处理返回值 query(结点下标 x, 要查询的位置左起始点 l, 要查询的位置右起始点 r) { if(tr[x] 有懒标记) { 1. 激活自己的懒标记，因为只有这样自己的值才是正确的 2. 将自己的懒标记下发左右子树，让他们获得自己当前懒标记 3. 初始化自身懒标记，回归原始状态 } // 当前的区间信息范围完全不在L到R之内时，我们直接返回初始值（每个题不一样，如果是求和就返回0）（return 初始值） if(tr[x].l > r || tr[x].r < l) return 初始值; // 当前的区间信息范围完全在L到R之内时,我们直接返回这个结点的值 if(tr[x].l >= l && tr[x].r <= r) return 结点值; // 当前的区间信息范围部分落在L到R之内时，继续搜索左右子树（调用函数递归向下） // 并将其返回的内容进行处理 }这里给出我的例子（以洛谷P3372 【模板】线段树 1为例）LL query(int x, int l, int r) { LL ans = 0; //这就是处理值的内容，每个题目都不一样 if(tr[x].lazy) { // 1. 激活自己的懒标记，因为只有这样自己的值才是正确的 tr[x].ans += (tr[x].r - tr[x].l + 1) * tr[x].lazy; // 2. 将自己的懒标记下发左右子树，让他们获得自己当前懒标记 tr[x << 1].lazy += tr[x].lazy; tr[x << 1 | 1].lazy += tr[x].lazy; // 3. 初始化自身懒标记，回归原始状态 tr[x].lazy = 0; } // 当前的区间信息范围完全不在L到R之内时，我们直接返回初始值（每个题不一样，如果是求和就返回0）（return 初始值） if(tr[x].l > r || tr[x].r < l) return 0; // 当前的区间信息范围完全在L到R之内时,我们直接返回这个结点的值 if(tr[x].l >= l && tr[x].r <= r) return tr[x].ans; // 当前的区间信息范围部分落在L到R之内时，继续搜索左右子树（调用函数递归向下） // 并将其返回的内容进行处理 ans += query(x << 1, l, r); ans += query(x << 1 | 1, l, r); return ans; }3.5.【例题1】洛谷P3372 【模板】线段树 1链接在下方：P3372 【模板】线段树 1 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)题目描述如题，已知一个数列，你需要进行下面两种操作：将某区间每一个数加上 $k$。求出某区间每一个数的和。输入格式第一行包含两个整数 $n, m$，分别表示该数列数字的个数和操作的总个数。第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。接下来 $m$ 行每行包含 $3$ 或 $4$ 个整数，表示一个操作，具体如下：1 x y k：将区间 $[x, y]$ 内每个数加上 $k$。2 x y：输出区间 $[x, y]$ 内每个数的和。输出格式输出包含若干行整数，即为所有操作 2 的结果。样例 #1样例输入 #15 5 1 5 4 2 3 2 2 4 1 2 3 2 2 3 4 1 1 5 1 2 1 4样例输出 #111 8 20提示对于 $30\%$ 的数据：$n \le 8$，$m \le 10$。 对于 $70\%$ 的数据：$n \le {10}^3$，$m \le {10}^4$。 对于 $100\%$ 的数据：$1 \le n, m \le {10}^5$。保证任意时刻数列中所有元素的绝对值之和 $\le {10}^{18}$。【样例解释】【例题1】题目解析与代码对于此题，我使用的懒标记激活方法与之前相同我的代码如下：#include <bits/stdc++.h> using namespace std; typedef long long LL; //将long long 类型定义为LL，后面使用LL就是使用long long 长整型 const int N = 2e5 + 10; //定义只读整型int，2e5是科学计数法 代表2 * 10^5，也就是20万。 最后加上5 就是 200005 struct Tree{ int l, r; LL ans, lazy; }tr[N << 2]; //N<<2 代表N位运算左移两位， 代表N乘以4 //tr代表结构体数组，存储树的每个结点信息，下标以1开始。 LL e[N << 2]; // 这里e存储的是原本的数据，下标以1开始。 void build(int x, int l, int r) { tr[x].l = l; tr[x].r = r; if(l == r) { tr[x].ans = e[l]; // 这里e存储的是原本的数据的数组。e[l]代表到了叶子结点时，它的左右起始点就代表了原数组的位置。 return; } int mid = (l + r) >> 1; // >>1 就是右移一位，位运算。相当于除以2 build(x << 1, l, mid); // << 1 就是左移一位，位运算。相当于乘以2 build(x << 1 | 1, mid + 1, r); // << 1 | 1 就是左移一位然后和1进行与运算，位运算。相当于乘以2加1 tr[x].ans = tr[x << 1].ans + tr[x << 1 | 1].ans; //这里是整合左右节点信息之和，因为题目就是信息之和 } void modify(int x, int l, int r, LL k) { if(tr[x].lazy) { //1. 激活自己的懒标记，因为只有这样自己的值才是正确的 tr[x].ans += (tr[x].r - tr[x].l + 1) * tr[x].lazy; //2. 将自己的懒标记下发左右子树，让他们获得自己当前懒标记 tr[x << 1].lazy += tr[x].lazy; tr[x << 1 | 1].lazy += tr[x].lazy; //3. 初始化自身懒标记，回归原始状态 tr[x].lazy = 0; } // 当前的区间信息范围完全不在L到R之内时，我们直接返回 // 这个内容可以直接看上图所示 if(tr[x].l > r || tr[x].r < l) return; // 当前的区间信息范围完全在L到R之内时 if(tr[x].l >= l && tr[x].r <= r) { //1. 将自己的值 直接修改完成 tr[x].ans += (tr[x].r - tr[x].l + 1) * k; // 2. 将左右子树的懒标记改为 自己需要修改的值 tr[x << 1].lazy += k; tr[x << 1 | 1].lazy += k; return; } //当前的区间信息范围部分落在L到R之内时，继续搜索左右子树（调用函数递归向下） modify(x << 1, l, r, k); modify(x << 1 | 1, l, r, k); //读取左右子树已经更新过的信息，将自身信息更新 tr[x].ans = tr[x << 1].ans + tr[x << 1 | 1].ans; } LL query(int x, int l, int r) { LL ans = 0; //这就是处理值的内容，每个题目都不一样 if(tr[x].lazy) { // 1. 激活自己的懒标记，因为只有这样自己的值才是正确的 tr[x].ans += (tr[x].r - tr[x].l + 1) * tr[x].lazy; // 2. 将自己的懒标记下发左右子树，让他们获得自己当前懒标记 tr[x << 1].lazy += tr[x].lazy; tr[x << 1 | 1].lazy += tr[x].lazy; // 3. 初始化自身懒标记，回归原始状态 tr[x].lazy = 0; } // 当前的区间信息范围完全不在L到R之内时，我们直接返回初始值（每个题不一样，如果是求和就返回0）（return 初始值） if(tr[x].l > r || tr[x].r < l) return 0; // 当前的区间信息范围完全在L到R之内时,我们直接返回这个结点的值 if(tr[x].l >= l && tr[x].r <= r) return tr[x].ans; // 当前的区间信息范围部分落在L到R之内时，继续搜索左右子树（调用函数递归向下） // 并将其返回的内容进行处理 ans += query(x << 1, l, r); ans += query(x << 1 | 1, l, r); return ans; } int main() { int n, m; cin >> n >> m; //读入初始数据量 for(int i = 1; i <= n; i++) { scanf("%lld", &e[i]); } //建立线段树 build(1, 1, n); while(m--) { int a, b, d; LL c; scanf("%d", &d); if(d == 2) { //查询 scanf("%d%d", &a, &b); printf("%lld\n", query(1, a, b)); } else { //修改 scanf("%d%d%lld", &a, &b, &c); modify(1, a, b, c); } } return 0; }4.关于懒标记Lazy-tag不同种类的写法2023年3月14日修订：两个方法都可以使用，方法二是市面上（包括洛谷中）一直都使用的方法，而作者的方法是方法一，大家按需使用由于方法二市面上给出的比较多，我在后面的例题中就不再重复给出了。我的方法主要有以下特性拥有懒标记的结点说明此前并没有查询到，需要激活懒标记来获得正确数据激活懒标记后，应该将懒标记下放到两个儿子结点，儿子结点不会修改，只是添加了懒标记激活懒标记后，数据更改，懒标记归回初始值但是目前许多代码中的操作是这样的：拥有懒标记的结点说明此前已经被查询到了，且已经获得了正确的数据查询到懒标记时，需要对儿子结点进行修改，并且下放懒标记，然后将懒标记回归初始值激活懒标记后，数据不会更改（因为以前就更改过了），懒标记归回初始值关键点在于拥有懒标记的节点是否已经被修改过。文中给出的是《到了以后再加载》 这种比较符合逻辑的解法而《标记有了就已经被修改过了》注重的是标记只是用来下放，下放的时候就应该把儿子结点修改完成了但是方法二有个优点：由于到了这个标记时，它已经被修改过了，所以可以放在函数出口的后面，而不造成影响具体看下列函数对比：//这是方法二的函数 //有懒标记的，说明它是已经被加过的数据. void modify(int x, int l, int r, LL k) { if(tr[x].l > r || tr[x].r < l) return; // ==================注意这里的细节(1)================= // 懒加载被激活可以放在函数返回之后，因为懒标记被放上去的时候就已经被修改了 // 懒标记只会激活儿子结点，而自己只是作为下放工具 if(tr[x].lazy) { tr[x << 1].ans += (tr[x << 1].r - tr[x << 1].l + 1) * tr[x].lazy; tr[x << 1].lazy += tr[x].lazy; tr[x << 1 | 1].ans += (tr[x << 1 | 1].r - tr[x << 1 | 1].l + 1) * tr[x].lazy; tr[x << 1 | 1].lazy += tr[x].lazy; tr[x].lazy = 0; } if(tr[x].l >= l && tr[x].r <= r) { tr[x].ans += (tr[x].r - tr[x].l + 1) * k; // ==================注意这里的细节(2)================= // 懒标记只加载自己的结点 tr[x].lazy += k; return; } modify(x << 1, l, r, k); modify(x << 1 | 1, l, r, k); tr[x].ans = tr[x << 1].ans + tr[x << 1 | 1].ans; } //这是方法一的函数 //有懒标记的，说明它是未初始化的函数 void modify(int x, int l, int r, LL k) { // ==================注意这里的细节(1)================= // 懒加载被激活必须放在函数返回之前，因为这样才能保证每个点是最新的 // 懒标记只会激活自己，儿子结点只会下放 if(tr[x].lazy) { tr[x].ans += (tr[x].r - tr[x].l + 1) * tr[x].lazy; tr[x << 1].lazy += tr[x].lazy; tr[x << 1 | 1].lazy += tr[x].lazy; tr[x].lazy = 0; } if(tr[x].l > r || tr[x].r < l) return; if(tr[x].l >= l && tr[x].r <= r) { tr[x].ans += (tr[x].r - tr[x].l + 1) * k; // ==================注意这里的细节(2)================= // 懒标记只加载儿子结点 tr[x << 1].lazy += k; tr[x << 1 | 1].lazy += k; return; } modify(x << 1, l, r, k); modify(x << 1 | 1, l, r, k); tr[x].ans = tr[x << 1].ans + tr[x << 1 | 1].ans; }具体的通过代码贴在下放供大家研究#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 2e5 + 10; struct Tree{ LL ans; int l, r; LL lazy; }tr[N << 2]; LL e[N << 2]; void build(int x, int l, int r) { tr[x].l = l; tr[x].r = r; if(l == r) {tr[x].ans = e[l]; return;} int mid = (l + r) >> 1; build(x << 1, l, mid); build(x << 1 | 1, mid + 1, r); tr[x].ans = tr[x << 1].ans + tr[x << 1 | 1].ans; } //有懒标记的，说明它是已经被加过的数据. void modify(int x, int l, int r, LL k) { if(tr[x].l > r || tr[x].r < l) return; if(tr[x].lazy) { tr[x << 1].ans += (tr[x << 1].r - tr[x << 1].l + 1) * tr[x].lazy; tr[x << 1].lazy += tr[x].lazy; tr[x << 1 | 1].ans += (tr[x << 1 | 1].r - tr[x << 1 | 1].l + 1) * tr[x].lazy; tr[x << 1 | 1].lazy += tr[x].lazy; tr[x].lazy = 0; } if(tr[x].l >= l && tr[x].r <= r) { tr[x].ans += (tr[x].r - tr[x].l + 1) * k; tr[x].lazy += k; return; } modify(x << 1, l, r, k); modify(x << 1 | 1, l, r, k); tr[x].ans = tr[x << 1].ans + tr[x << 1 | 1].ans; } LL query(int x, int l, int r) { LL ans = 0; if(tr[x].l > r || tr[x].r < l) return 0; if(tr[x].lazy) { tr[x << 1].ans += (tr[x << 1].r - tr[x << 1].l + 1) * tr[x].lazy; tr[x << 1].lazy += tr[x].lazy; tr[x << 1 | 1].ans += (tr[x << 1 | 1].r - tr[x << 1 | 1].l + 1) * tr[x].lazy; tr[x << 1 | 1].lazy += tr[x].lazy; tr[x].lazy = 0; } if(tr[x].l >= l && tr[x].r <= r) return tr[x].ans; ans += query(x << 1, l, r); ans += query(x << 1 | 1, l, r); return ans; } int main() { int n, m; cin >> n >> m; for(int i = 1; i <= n; i++) { scanf("%lld", &e[i]); } build(1, 1, n); while(m--) { int a, b, d; LL c; scanf("%d", &d); if(d == 2) { scanf("%d%d", &a, &b); printf("%lld\n", query(1, a, b)); } else { scanf("%d%d%lld", &a, &b, &c); modify(1, a, b, c); } } return 0; }5.其他例题2023年3月14日修订【例题2】洛谷P3373 【模板】线段树 2题目链接如下：P3373 【模板】线段树 2 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)题目描述如题，已知一个数列，你需要进行下面三种操作：将某区间每一个数乘上 $x$将某区间每一个数加上 $x$求出某区间每一个数的和输入格式第一行包含三个整数 $n,m,p$，分别表示该数列数字的个数、操作的总个数和模数。第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。接下来 $m$ 行每行包含若干个整数，表示一个操作，具体如下：操作 $1$： 格式：1 x y k 含义：将区间 $[x,y]$ 内每个数乘上 $k$操作 $2$： 格式：2 x y k 含义：将区间 $[x,y]$ 内每个数加上 $k$操作 $3$： 格式：3 x y 含义：输出区间 $[x,y]$ 内每个数的和对 $p$ 取模所得的结果输出格式输出包含若干行整数，即为所有操作 $3$ 的结果。样例 #1样例输入 #15 5 38 1 5 4 2 3 2 1 4 1 3 2 5 1 2 4 2 2 3 5 5 3 1 4样例输出 #117 2提示【数据范围】对于 $30\%$ 的数据：$n \le 8$，$m \le 10$ 对于 $70\%$ 的数据：$n \le 10^3 $，$ m \le 10^4$ 对于 $100\%$ 的数据：$ n \le 10^5$，$ m \le 10^5$除样例外，$p = 571373$（数据已经过加强^\_^）样例说明： 故输出应为 $17$、$2$（ $40 \bmod 38 = 2$ ）【例题2】题目解析与代码我用的方法还是懒标记在原地激活的方法（具体见第四章），也就是拥有懒标记的结点并没有被激活过。本题的难点在于两个懒标记的先后加载顺序，以及它们之间会发生的影响。那么这里存在一个问题就是如果我有加法标记后再次加上乘法标记需要怎么操作：我们需要对加法标记乘以相同的乘法数值才行。而且激活的时候必须先激活乘法标记再激活加法标记（因为我们激活的顺序影响了儿子结点的懒标记更改顺序）#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; typedef long long LL; int MOD = 571373; struct Tree{ int l, r; //mul是乘法标记，它的初始值为1，add是加法标记，它的初始值为0 LL ans, add = 0, mul = 1; }tr[N * 6]; int n, m; void build(int x, int l, int r) { tr[x].l = l; tr[x].r = r; if(l == r) { scanf("%lld", &tr[x].ans); return; } int mid = l + r >> 1; build(x << 1, l, mid); build(x << 1 | 1, mid + 1, r); tr[x].ans = (tr[x << 1].ans + tr[x << 1 | 1].ans) % MOD; } void modify(int x, int l, int r, LL k, int way) { //注意这里是先激活乘的后激活加的，顺序不可改变 //因为子树如果原来存在add标记,那么它必须先乘mul标记 //注意子树的mul是相乘的 if(tr[x].mul != 1) { tr[x].ans = (tr[x].ans * tr[x].mul) % MOD; tr[x << 1].add = (tr[x << 1].add * tr[x].mul) % MOD; tr[x << 1 | 1].add = (tr[x << 1 | 1].add * tr[x].mul) % MOD; tr[x << 1].mul = (tr[x << 1].mul * tr[x].mul) % MOD; tr[x << 1 | 1].mul = (tr[x << 1 | 1].mul * tr[x].mul) % MOD; tr[x].mul = 1; } //必须后激活add的标记 if(tr[x].add) { tr[x].ans = (tr[x].ans + (((tr[x].r - tr[x].l + 1) * tr[x].add) % MOD)) % MOD; tr[x << 1].add = (tr[x << 1].add + tr[x].add) % MOD; tr[x << 1 | 1].add = (tr[x << 1 | 1].add + tr[x].add) % MOD; tr[x].add = 0; } if(tr[x].l > r || tr[x].r < l) return; if(tr[x].l >= l && tr[x].r <= r) { if(way == 2) { tr[x].ans = (tr[x].ans + (((tr[x].r - tr[x].l + 1) * k) % MOD)) % MOD; tr[x << 1].add = (tr[x << 1].add + k) % MOD; tr[x << 1 | 1].add = (tr[x << 1 | 1].add + k) % MOD; } else { tr[x].ans = (tr[x].ans * k) % MOD; //子树如果存在add标记，那么必须乘这个下发的值 tr[x << 1].add = (tr[x << 1].add * k) % MOD; tr[x << 1 | 1].add = (tr[x << 1 | 1].add * k) % MOD; tr[x << 1].mul = (tr[x << 1].mul * k) % MOD; tr[x << 1 | 1].mul = (tr[x << 1 | 1].mul * k) % MOD; } return; } modify(x << 1, l, r, k, way); modify(x << 1 | 1, l, r, k, way); tr[x].ans = (tr[x << 1].ans + tr[x << 1 | 1].ans) % MOD; } LL query(int x, int l, int r) { LL ans = 0; if(tr[x].mul != 1) { tr[x].ans = (tr[x].ans * tr[x].mul) % MOD; tr[x << 1].add = (tr[x << 1].add * tr[x].mul) % MOD; tr[x << 1 | 1].add = (tr[x << 1 | 1].add * tr[x].mul) % MOD; tr[x << 1].mul = (tr[x << 1].mul * tr[x].mul) % MOD; tr[x << 1 | 1].mul = (tr[x << 1 | 1].mul * tr[x].mul) % MOD; tr[x].mul = 1; } if(tr[x].add) { tr[x].ans = (tr[x].ans + (((tr[x].r - tr[x].l + 1) * tr[x].add) % MOD)) % MOD; tr[x << 1].add = (tr[x << 1].add + tr[x].add) % MOD; tr[x << 1 | 1].add = (tr[x << 1 | 1].add + tr[x].add) % MOD; tr[x].add = 0; } if(tr[x].l > r || tr[x].r < l) return 0; if(tr[x].l >= l && tr[x].r <= r) return tr[x].ans; ans = (ans + query(x << 1, l, r)) % MOD; ans = (ans + query(x << 1 | 1, l, r)) % MOD; return ans; } int main() { cin >> n >> m >> MOD; int t, a, b; LL c; build(1, 1, n); while(m--) { scanf("%d", &t); if(t == 1 || t == 2) { scanf("%d%d%lld", &a, &b, &c); modify(1, a, b, c, t); }else { scanf("%d%d", &a, &b); printf("%d\n", (query(1, a, b) % MOD)); } } return 0; }
速通模拟退火（Simulated Annealing）作者：郭程(judgemeido@163.com)本教程为原创教程，转载请标明出处，禁止商业用途。本教程属于快速入门（Quick-Start)系列，不对具体退火细节深究，只论算法竞赛题目研究。1.是什么？为什么？怎么做？Q1:模拟退火是什么算法？模拟退火是模拟物理上退火方法，通过N次迭代（退火），逼近函数的上的一个最值（最大或者最小值）。比如逼近这个函数的最大值C点：Q2:模拟退火为什么可行？讨论这个问题需要理解一下物理原型是怎么样的，也就是原来是怎么“退火”的：模拟退火算法的思想借鉴于固体的退火原理，当固体的温度很高的时候，内能比较大，固体的内部粒子处于快速无序运动，当温度慢慢降低的过程中，固体的内能减小，粒子的慢慢趋于有序，最终，当固体处于常温时，内能达到最小，此时，粒子最为稳定。注意标粗字体：温度高->运动速度快（温度低->运动速度慢）温度是缓慢（想象成特别慢的那种）降低的温度基本不再变化后，趋于有序(最后内能达到最小，也就是接近最优)我们通过模拟这个操作，使得我们需要的答案“趋于有序”，也就是最靠近需要的值（最值）。Q3:怎么做？大方向首先，理解一下大方向：模拟退火就是一种循环算法。我们先设定一个初始的温度$T$（这个温度会比较高，比如2000）每次循环都退火一次。（具体怎么操作后面详解）然后降低$T$的温度，我们通过让$T$和一个“降温系数”$\Delta T$（一个接近1的小数，比如$0.99$)相乘，达到慢慢降低温度的效果，直到接近于0（我们用$eps$来代表一个接近0的数(比如0.00001)，只要$T>eps$就可以退出循环了）所以总的来说，用伪代码表示退火的流程是这样的：double T = 2000; //代表开始的温度 double dT = 0.99; //代表系数delta T double eps = 1e-14; //相当于0.0000000000000001 while(T > eps) { //-------------- //这里是每一次退火的操作 //-------------- T = T * dT; //温度每次下降一点点， T * 0.99 }退火详解我们要求解的答案无非是两个：自变量$x$和对应函数的最大值$f(x)$那么模拟退火的是怎么做到的呢？【下面车速很快，请系好安全带！】我们先随机找一点$x_0$ ，不论是哪个点都可以，随机！（不超过定义域就行）。这个点作为我们的初始值（相当于物体里的一个粒子）再找到一点$f(x_0)$,来代表$x_0$所对应的函数值现在正式开始退火！刚才我们说了$x_0$相当于是一个粒子，所以我们会进行一个无序运动，也就是向左或者向右随机移动是的，是随机移动，可能向左，也可能向右，但是请记住一个关键点：移动的幅度和当前的温度$T$有关。温度$T$越大，移动的幅度越大。温度$T$越小，移动的幅度就越小。这是在模拟粒子无序运动的状态。接受(Accept)更"好"的状态假设我们移动到了$x_1$处，那么这个点对应的$f(x_1)$很明显答案是优于（大于）当前的$f(x_0)$的因此我们将答案进行更新。也就是将初始值进行替换：$x_0=x_1,f(x_0)=f(x_1)$。这是一种贪心的思想。以一定概率接受(Accept)更差的状态这是退火最精彩的部分。为什么我们要接受一个更加差的状态呢？因为可能在一个较差的状态旁边会出现一个更加高的山峰如果我们鼠目寸光，只盯着右半区，很容易随着温度的下降、左右跳转幅度的减小而迷失自己，最后困死在小山丘中。而我们如果找到了左边山峰的低点，以一定的概率接受了它（概率大小和温度以及当前的值的关键程度有关），会在跳转幅度减少之前，尽可能找到最优点。那么我们以多少的概率去接受它呢？我们用一个公式表示（这个公式我们只需记住，这是科学家推导出来的结论）：$$ \Huge e^{\frac{\Delta f}{kT}} $$别慌！很简单！我们来理解一下这里面的变量：$e$是自然对数，约等于2.71。我们可以把右上角这一坨值$\frac{\Delta f}{kT}$看成一个整体$x$:$e^x$的图形画出来是这样的：因为我们想要函数$e^x$来代表一个概率值，所以我们只需要关注x为负数的部分即可：负数部分的值域是在$(0,1)$开区间内，x越小，越接近0，越大越靠近1。因为在0到1之间，所以这个值相当于是概率了。比如$e^x=0.97$，那么我们接受的概率就是$97\%$而正数部分的值域会大于1，也就是说概率会超过$100\%$，所以会一定选（其实是上一种找到更优的情况）$kT$$k$其实是个物理学常数，我们在代码中不会用到。$T$很简单，就是当前的温度。所以实际上这个分母就是$T$，$k$当做$1$使用。$\Delta f$我们着重讲一下什么是$\Delta f$。其实从前面的函数$e^x$中可以发现，$\Delta f$必须是个负数！我们想要函数$e^x$来代表一个概率值，一定要让它的值域属于$(0,1)$，所以$\frac{\Delta f}{kT}$必须是个负数。但是$kT$在我们的模拟中一定是正数，那么$\Delta f$必须是个负数！其实$\Delta f$就是当前解的函数值与目标解函数值之差，$\Delta f=-\left|f\left(x_0\right)-f\left(x_1\right)\right|$，并且一定是个负数。这个需要具体问题具体分析。比如现在我们求一个函数的最大值，那么如果$f(x_0) < f(x_1)$了，那就说明结果变好了，我们肯定选择它（见第4点）如果$f(x_0) > f(x_1)$，那就说明结果变差了，我们需要概率选择它，因此$\Delta f=-(f(x_0) - f(x_1))$所以总结一下就是：随机后的函数值如果结果更好，我们一定选择它(即$x_0=x_1,f(x_0)=f(x_1)$) 随机后的函数值如果结果更差，我们以$\LARGE e^{\frac{\Delta f}{kT}}$的概率接受它伪代码流程注：对代码中的函数作出解释：①对rand()函数rand()函数可以默认拿到[0,32767]内的随机整数RAND_MAX = 32767，可以看作常量。本质是宏定义: #define RAND_MAX 32767rand() * 2 的范围是[0,32767 * 2]rand() * 2 - RAND_MAX 的范围是[-32767, 32767]②对exp()函数exp(x)代表$e^x$③关于exp((df - f) / T) * RAND_MAX > rand()目的是要概率接受，但是$e^x$是个准确值，所以从理论上我们可以生成一个（0,1）的随机数，如果$e^x$比(0,1)这个随机数要大，那么我们就接受。但是由于rand()只能产生[0,32767]内的随机整数，化成小数太过麻烦。所以我们可以把左边乘以RAND_MAX（也就是把概率同时扩大32767倍），效果就等同于$e^x$比(0,1)了。double T = 2000; //代表开始的温度 double dT = 0.99; //代表系数delta T double eps = 1e-14; //相当于0.0000000000000001 //用自变量计算函数值,这里可能存在多个自变量对应一个函数值的情况，比如f(x,y) double func(int x, ... ) { //这里是对函数值进行计算 double ans = ....... return ans; } //原始值 double x = rand(); //x0取随机值 double f = func(x,...); //通过自变量算出f(x0)的值 while(T > eps) { //-------------- //这里是每一次退火的操作 //x1可以左右随机移动，幅度和温度T正相关，所以*T //注意这里移动可以左右移动，但是也可以单向移动 //关于rand()详细见开头注的① double dx = (2*rand() - RAND_MAX) * T; //让x落在定义域内，如果没在里面，就重新随机。题目有要求需要写，否则不用写 // ================ while(x > ? || x < ? ...) { double dx = (2*rand() - RAND_MAX) * T; } // ================ //求出f(x1)的值 double df = func(dx); //这里需要具体问题具体分析，我们要接受更加优秀的情况。可能是df < f(比如求最小值） if(f < df) { f = df; x = dx; [...,y = dy;] // 接受，替换值，如果多个自变量，那么都替换 } //否则概率接受，注意这里df-f也要具体问题具体分析。 //详细见开头注的②③ else if(exp((df - f) / T) * RAND_MAX > rand()) { f = df; x = dx; [...y = dy;] // 接受，替换值，如果多个自变量，那么都替换 } //-------------- T = T * dT; //温度每次下降一点点， T * 0.99 } //最后输出靠近最优的自变量x值，和函数值f(x) cout << x << " " << f << endl;2.通过模拟退火算出 根号n的值思路是这样的：我们试图通过退火找出一个值$x_0$，使得${x_0}^2$的值更加接近于${\sqrt{n}}^2$。（记住退火是让一个随机值去逼近最后的答案）因为${x_0}^2$的值更加接近于${\sqrt{n}}^2$。因此$x_0$值就更加接近于$\sqrt{n}$所以我们需要一个函数$f(x)$，算出${x_0}^2$和${\sqrt{n}}^2$的接近程度，那么毋庸置疑，我们需要算出他们绝对值的差。$$ f(x)=\left |x^2 - n \right | $$也就是说我们的函数表达式就有了//n代表我们最后函数要逼近的值 double n; //x表示我们随机产生的那个数的平方和n的靠近程度 double func(double x) { return fabs(x * x - n); }写出退火函数SA()double T = 20000; //初始温度，初始温度主要是看题目开始需要跳转的幅度。 double dT = 0.993; //变化率，这里需要速度稍微慢一点，写0.995 或者 0.997都可以，但是越靠近1速度就越慢 const double eps = 1e-14; //10的-14次方已经非常小了，写这个大概率没问题 void SA() { //首先随机生成一个点x0，这里我用0代替。 double x = 0; //算出x平方和n的差距f(x0) double f = func(x); while(T > eps) { //这里x0既可以变小，也可以变大，所以我们正负都要进行一个跳转,算出变换后的点dx double dx = x + (2 * rand() - RAND_MAX) * T; //但是请注意，dx很明显要保证 >= 0才行，因为算术平方根的定义域是>=0，因此小于0就重新随机 while(dx < 0) dx = x + (2 * rand() - RAND_MAX) * T; //算出变换后的点dx的平方和n的差距，f(dx) double df = func(dx); //这里就是关键的地方了，很明显我们需要算出来的function值越小，自变量x更加接近那个根号值。 //所以如果新来的值df 比 f更小，我们百分百接受 if(df < f) { //注意更新所有变量 f = df; x = dx; } //否则我们概率接受，这里的需要写 f - df了，因为这样才是负值。负值说明我们并不是贪心接受的，他是不太好的值。 else if(exp((f - df)/T) * RAND_MAX > rand()) { //注意更新所有变量 f = df; x = dx; } //温度下降一下 T *= dT; } printf("%.8lf",x); }最后贴上完整代码和注释供大家调试。#include <bits/stdc++.h> using namespace std; //n代表我们最后函数要逼近的值 double n; //x表示我们随机产生的那个数的平方和n的靠近程度 double func(double x) { return fabs(x * x - n); } double T = 20000; //初始温度，初始温度主要是看题目开始需要跳转的幅度。 double dT = 0.993; //变化率，这里需要速度稍微慢一点，写0.995 或者 0.997都可以，但是越靠近1速度就越慢 const double eps = 1e-14; //10的-14次方已经非常小了，写这个大概率没问题 void SA() { //首先随机生成一个点x0，这里我用0代替。 double x = 0; //算出x平方和n的差距f(x0) double f = func(x); while(T > eps) { //这里x0既可以变小，也可以变大，所以我们正负都要进行一个跳转,算出变换后的点dx double dx = x + (2 * rand() - RAND_MAX) * T; //但是请注意，dx很明显要保证 >= 0才行，因为算术平方根的定义域是>=0，因此小于0就重新随机 while(dx < 0) dx = x + (2 * rand() - RAND_MAX) * T; //算出变换后的点dx的平方和n的差距，f(dx) double df = func(dx); //这里就是关键的地方了，很明显我们需要算出来的function值越小，自变量x更加接近那个根号值。 //所以如果新来的值df 比 f更小，我们百分百接受 if(df < f) { //注意更新所有变量 f = df; x = dx; } //否则我们概率接受，这里的需要写 f - df了，因为这样才是负值。负值说明我们并不是贪心接受的，他是不太好的值。 else if(exp((f - df)/T) * RAND_MAX > rand()) { //注意更新所有变量 f = df; x = dx; } //温度下降一下 T *= dT; } printf("%.8lf",x); } int main() { cin >> n; SA(); }3.例题POJ - 2420 题目描述给出平面上N（N<=100）个点，你需要找到一个这样的点，使得这个点到N个点的距离之和尽可能小。输出这个最小的距离和（四舍五入到最近的整数）。Input输入第一行N，接下来N行每行两个整数，表示N个点Output输出一行一个正整数，最小的距离和。Sample Input样例输入4 0 0 0 10000 10000 10000 10000 0Sample Output样例输出28284题目解析学过平面几何的一定知道，假定两点的坐标为$a(x_1,y_1),b(x_2,y_2)$，那么他们之间的距离$d$可以用勾股定理计算：$$ d = \sqrt{(x_1-x_2)^2-(y_1-y_2)^2} $$所以我们的函数$func()$就是：求出一个随机点 $A=(x_0,y_0)$到$N$个点的距离之和$D$，就是把这个点A和所有N个点的距离相加，即：$$ \large D=\sum_{i=1}^{N} {\sqrt{(x_0-x_i)^2-(y_0-y_i)^2}} $$我们将N个点用结构体存起来const int N = 1e5 + 5; struct Point { double x, y; }e[N]; //main函数中输入N个点 int main() { cin >> n; for(int i = 1; i <= n; i++) scanf("%lf%lf", &e[i].x, &e[i].y); }那么我们最关键的函数（求出一个随机点$A=(x_0,y_0)$到$N$个点的距离之和$D$）就是：//输入我们随机生成的点A 坐标 x0, y0 double func(double x, double y) { double ans = 0; for(int i = 1; i <= n; i++) { double xx = e[i].x, yy = e[i].y; // xx 就是 xi ，yy 就是 yi double p = fabs(e[i].x - x); // x0 - xi double q = fabs(e[i].y - y); // y0 - yi ans += (sqrt((p * p + q * q))); // ans加上到随机点A到点i的距离 } return ans; }然后套用上面的公式，我们写出SA()模拟退火double T = 2000; //初始温度 double dT = 0.993; //变化率，这里需要速度稍微慢一点，写0.995 或者 0.997都可以，但是越靠近1速度就越慢 const double eps = 1e-14; //10的-14次方已经非常小了，写这个大概率没问题 void SA() { //随机生成点A(x0,y0)，这里我直接赋值为了0。当然也可以写rand()，差别都不大。 double x = 0, y = 0; //生成的点A(x0,y0)对应的函数值f(x0, y0) double f = func(x, y); while(T > eps) { //这里对x和y同时进行一个偏移，很明显在一个平面中，上下左右都可以移动，所以我们选择了rand() * 2 - RAND_MAX //对于每个点，我们的偏移幅度都要 * T,温度越高，偏移量越大 double dx = x + (rand() * 2 - RAND_MAX) * T; double dy = y + (rand() * 2 - RAND_MAX) * T; //算出偏移后的点B(dx, dy)对应的函数值f(dx, dy) double df = func(dx, dy); //这里就是关键的地方了，很明显我们需要算出来的function值越小，就更加优秀 //所以如果新来的值df 比 f更小，我们百分百接受 if(df < f) { //注意更新所有变量 f = df; y = dy; x = dx; } //否则我们概率接受，这里的需要写 f - df了，因为这样才是负值 else if(exp((f - df) / T) * RAND_MAX > rand()) { //注意更新所有变量 f = df; y = dy; x = dx; } //降低温度 T = T * dT; } //输出答案 printf("%.f\n", f); }最后贴上完全版代码#include <iostream> #include <algorithm> #include <cstdio> #include <cmath> #include <cstring> #include <ctime> using namespace std; const int N = 1e5 + 5; double dT = 0.993; double T = 2000; const double eps = 1e-14; struct vega { double x, y; }e[N]; int n; //输入我们随机生成的点A 坐标 x0, y0 double func(double x, double y) { double ans = 0; for(int i = 1; i <= n; i++) { double xx = e[i].x, yy = e[i].y; // xx 就是 xi ，yy 就是 yi double p = fabs(e[i].x - x); // x0 - xi double q = fabs(e[i].y - y); // y0 - yi ans += (sqrt((p * p + q * q))); // ans加上到随机点A到点i的距离 } return ans; } void SA() { //随机生成点A(x0,y0)，这里我直接赋值为了0。当然也可以写rand()，差别都不大。 double x = 0, y = 0; //生成的点A(x0,y0)对应的函数值f(x0, y0) double f = func(x, y); while(T > eps) { //这里对x和y同时进行一个偏移，很明显在一个平面中，上下左右都可以移动，所以我们选择了rand() * 2 - RAND_MAX //对于每个点，我们的偏移幅度都要 * T,温度越高，偏移量越大 double dx = x + (rand() * 2 - RAND_MAX) * T; double dy = y + (rand() * 2 - RAND_MAX) * T; //算出偏移后的点B(dx, dy)对应的函数值f(dx, dy) double df = func(dx, dy); //这里就是关键的地方了，很明显我们需要算出来的function值越小，就更加优秀 //所以如果新来的值df 比 f更小，我们百分百接受 if(df < f) { //注意更新所有变量 f = df; y = dy; x = dx; } //否则我们概率接受，这里的需要写 f - df了，因为这样才是负值 else if(exp((f - df) / T) * RAND_MAX > rand()) { //注意更新所有变量 f = df; y = dy; x = dx; } //降低温度 T = T * dT; } //输出答案 printf("%.f\n", f); } int main() { cin >> n; for(int i = 1; i <= n; i++) { scanf("%lf%lf", &e[i].x, &e[i].y); } SA(); }
VScode安装c/c++环境本文操作系统：windows10 22H2 专业工作站版（所有win10系统都可使用)本文目标人群：刚上手需要安装c/c++环境的新手同志们。或是单纯重装系统需要重新配置c++环境的。本文章解决问题：为什么我的vscode无法运行c++？0.在此之前的操作在开始之前，请你在此电脑页面中查看标签下确保你勾选了文件扩展名与隐藏的项目1.vscode下载与安装vscode在官网上可以下载：在百度中搜索vscode，点击下载即可安装安装环节不多赘述，下一步即可。选项默认。安装地址可以自行更改。2.编译器MinGW-64的安装（老手可跳过）你需要知道一个c++文件是如何才能在你的电脑中运行的：你写的是文本，而只有二进制才能运行。所以所谓的"编译器"就是解决将文本变成可执行文件的一个工具。vscode并不是一个IDE(集成开发环境)，它就是一个可以安装插件的可扩展文本编辑器。也就是说，你如果不装编译器，你的vscode是无法解决编译问题的。所以我们需要下载一个在windows电脑上可以帮你编译的编译器，也就是MinGW-64。MinGW的全称是Minimalist GNU on Windows。它实际上是将经典的开源C语言 编译器 GCC 移植到了 Windows 平台下，并且包含了 Win32API ，因此可以将源代码编译为可在 Windows 中运行的可执行程序。而且还可以使用一些 Windows 不具备的，Linux平台下的开发工具。一句话来概括：MinGW 就是 GCC 的 Windows 版本 。下载方式如下：首先搜索mingw-64 sourceforge找到地址为sourceforge.net的网站注意名字叫做MinGW-w64 - for 32 and 64 bit Windows，请确定是这个名字接着我们点击Files然后向下拉，找到这个文件x86_64-posix-seh点击就可以下载了。如果你5秒后没有弹出下载页面或者下载非常慢，请点击这个按钮点击direct link可以解决没有下载的问题。点击auto-select可以解决下载过慢的问题（会自动分配最好的镜像节点进行下载）请确认你的下载全名是x86_64-8.1.0-release-posix-seh-rt_v6-rev0，并且是7z压缩包，大小48213KB使用解压缩软件进行解压。如果你没有解压缩软件，你可以下载7-zip这个开源免费软件。当然也可以使用win-rar,360压缩等一系列软件进行解压。我现在演示7-zip这个软件,其他软件同理右键，使用7-zip打开，出现这样的页面解压到你需要的目录。这里我解压到了C:\Environment解压以后是这样的接下来我们配置环境变量。右键此电脑点击属性。在打开的窗口中依次点击高级系统设置，环境变量在打开的窗口中系统变量里找到Path，单击选中，然后点击编辑。（或者直接双击）在环境变量中点击新建，在生成的地方粘贴进去你的目录bin位置假如你解压的地方是c:\Environment，那么这里应该填写c:\Environment\mingw64\bin或者你打开刚才解压的位置，然后单击地址栏（注意在空白部分单击），进行复制设置完成后一定要点击确定，直到刚才的三个窗口全部确定且关闭、然后按下开始菜单键或者键盘上的win键，搜索cmd输入gcc，回车。若是出现以下情况，说明安装完成。3.vscode 的配置打开后，安装c/c++ 与 中文插件点击打开文件夹，选择一个你用来工作，放置c++文件的文件夹（最好是空的）请注意！：接下来的配置只能在此文件夹或者这个文件夹的子文件夹下生效请注意！：接下来的配置只能在此文件夹或者这个文件夹的子文件夹下生效请注意！：接下来的配置只能在此文件夹或者这个文件夹的子文件夹下生效打开后在左边右键新建文件，我新建了x.cpp，你也可以新建a.cpp、b.cpp等，以.cpp结尾的文件接下来输入测试代码#include <iostream> using namespace std; int main() { cout << "hello" << endl; return 0; }这个时候请按下Ctrl+Shift+P键盘上的三个键在弹出的框中输入edit configurations，选择编辑配置（UI）注意：如果你的默认配置就与我一样，那么就不需要改注意：如果你的默认配置就与我一样，那么就不需要改注意：如果你的默认配置就与我一样，那么就不需要改请选择刚才安装路径下g++.exe在IntelliSense 模式中选择windows-gcc-x64。并且此时你可以看到在左边出现了.vscode的配置文件c_cpp_properties.json在高级设置中清空所有设置最终文件应该如下所示{ "configurations": [ { "name": "Win32", "includePath": [ "${workspaceFolder}/**" ], "defines": [ "_DEBUG", "UNICODE", "_UNICODE" ], "compilerPath": "C:/Environment/mingw64/bin/g++.exe", "cStandard": "c17", "cppStandard": "c++17", "intelliSenseMode": "windows-gcc-x64" } ], "version": 4 }name可以随便改变， includePath表示在什么地方可以调用包含库文件（比如iostream，cmath等标志库），/**代表工作目录以及子目录下。 "name": "Win32", "includePath": [ "${workspaceFolder}/**" ], "defines": [ "_DEBUG", "UNICODE", "_UNICODE" ], 这是你的安装路径： "compilerPath": "C:/Environment/mingw64/bin/g++.exe" 下面这三个不会改变，当然你把c17改成c11也可以。 "cStandard": "c17", "cppStandard": "c++17", "intelliSenseMode": "windows-gcc-x64"然后到x.cpp文件上，按下F5，选择GDB/LLDB这个选项接下来选择g++.exe生成和调试活动文件接着会在调试控制台看到一堆东西会生成tasks.json和x.exe两个文件我们点击终端，打入./x.exe，然后回车，就输出了。到此为止，我们完成了编译为二进制文件并且执行的步骤.exe文件就是二进制可执行文件接下来我们要进行调试（debug）来进行更方便的操作。从左到右点击这三个选项。这个时候launch.json就创建完毕了，具体如下你可以直接复制下面的最终参数注意修改miDebuggerPath中的gdb.exe位置注意修改miDebuggerPath中的gdb.exe位置注意修改miDebuggerPath中的gdb.exe位置以及preLaunchTask与你的tasks.json中的"label"保持一致以及preLaunchTask与你的tasks.json中的"label"保持一致以及preLaunchTask与你的tasks.json中的"label"保持一致，也可以从头开始跟着一步步进行修改。{ // 使用 IntelliSense 了解相关属性。 // 悬停以查看现有属性的描述。 // 欲了解更多信息，请访问: https://go.microsoft.com/fwlink/?linkid=830387 "version": "0.2.0", "configurations": [ { "name": "(gdb) 启动", "type": "cppdbg", "request": "launch", "program": "${fileDirname}\\${fileBasenameNoExtension}.exe", "args": [], "stopAtEntry": false, "cwd": "${fileDirname}", "environment": [], "externalConsole": true, "MIMode": "gdb", //这里选择你的gdb.exe位置 "miDebuggerPath": "C:/Environment/mingw64/bin/gdb.exe", "setupCommands": [ { "description": "为 gdb 启用整齐打印", "text": "-enable-pretty-printing", "ignoreFailures": true }, ], //请保证与tasks.json中的label内容相同 "preLaunchTask": "C/C++: g++.exe 生成活动文件" } ] }接下来的内容是从0开始创建的内容，可以跳过接下来的内容是从0开始创建的内容，可以跳过接下来的内容是从0开始创建的内容，可以跳过点击添加配置，点击gdb启动这个选项接着会出现这些代码，我们将需要改动的进行说明。"program": "${fileDirname}\\${fileBasenameNoExtension}.exe", //这个文件夹所有exe都可以被调试 "externalConsole": true, //cmd外部窗口打开 "miDebuggerPath": "C:/Environment/mingw64/bin/gdb.exe", //gdb路径 "preLaunchTask": "C/C++: g++.exe 生成活动文件" //调试之前执行编译最后在这个位置单击生成断点按F5运行，效果如下。点击红框即可退出调试。