GDB简单实用教程

GDB简单实用教程

GDB是G++附带的调试工具,提供了设置断点、打印变量、单步调试等功能,可以让你在调试程序时事半功倍…

GDB可以

  1. 启动你的程序,可以按照你的定制要求随心所欲的运行程序。
  2. 可让被调试的程序在你所指定的调置的断点处停住。
  3. 当程序被停住时,可以检查此时你的程序中所发生的事,以及内存状态等。
  4. 动态的改变你程序的执行环境。

当然,GDB不是这个东西:
TIM截图20190908113017.png

(图形化的GDB缺少一些必要的回显,例如函数中断点不会显示当前函数名和参数,有些时候很麻烦)。。。

Windows下GDB使用

一般情况下GDB在Windows系统下会在MinGW或MinGW64文件夹下的bin目录中,如图:

TIM截图20190908113710.png

双击即可开始运行,如果你想要用命令也可以cd到这个目录然后.\gdb

TIM截图20190908114132.png

(注:笔者使用的是CMDer,与普通CMD效果可能略有出入)

GDB使用的前置条件是你的程序在编译时包含了调试信息,如果你在使用命令行编译,那么请在指令的后面加入-g;如果你在使用IDE的话,也需要将IDE中的编译指令加入-g,如果你的IDE中有默认的“Debug”属性的话,那么用默认的就行:

TIM截图20190908115335.png

在加入-g时,值得注意的时-g一共有4个等级:

  • -g0等于不加-g。即不包含任何信息
  • -g1只包含最小信息,一般来说只有你不需要debug,只需要backtrace信息,并且真的很在意程序大小,或者有其他保密/特殊需求时才会使用-g1。
  • -g2为gdb默认等级,包含绝大多数你需要的信息。
  • -g3包含一些额外信息,例如包含宏定义信息。当你需要调试宏定义时,请使用-g3

进入gdb后,输入file {你的程序}。然后使用set args {arg1} {arg2} … {argN} 设定好你的程序参数,再运行run.

TIM截图20190908121133.png

GDB指令

help指令很强大!多用help!help里面总会有你需要的信息。如果你不知道如何使用help,请在gdb里面输入:help all

这里挑选一些常用的指令给大家说明一下:(指令需要在控制权在GDB下时(如遇到断点)

  1. backtrace显示栈信息。简写为bt;

  2. frame x 切换到栈的第x层。其中x会在bt命令中显示,从0开始。0表示栈顶。简写为f;

  3. up/down x 往栈顶/栈底移动x帧。当不输入x时,默认为1;

  4. print x打印x的信息,x可以是变量,也可以是对象或者数组。简写为p;

  5. print */&x 打印x的内容/地址(就相当于C++的*&运算符);

  6. call 调用函数。注意此命令需要一个正在运行的程序;

  7. break x在的第x行设置断点,然后gdb会给出断点编号y。简写为b。后面会对断点进行更详细的解释;

  8. command m 设置程序执行到断点m时要看的内容,例如:

    1
    2
    3
    4
    5
    6
    7
    command n

    >printf "x is %d\n",x

    >c

    >end

    如果command后面没有参数n,则命令被赋给最后一个breakpoint,这其实是说break和command连在一起用,在脚本里用就非常方便了;

  9. continue 继续运行程序。进入调试模式后,若你已经获取了你需要的信息或者需要程序继续运行时使用。可简写为c

  10. until 执行到当前循环完成。可简写为u;

  11. step 单步调试,步入当前函数。可简写为s;

  12. next单步调试,步过当前函数。可简写为n;

  13. finish 执行到当前函数返回;

  14. set var x=10 改变当前变量x的值。也可以这样用:set {int}0x83040 = 10把内存地址0x83040的值强制转换为int并赋值为10(慎用);

  15. info locals 打印当前栈帧的本地变量;

  16. jump使当前执行的程序跳转到某一行;

  17. return 强制函数返回。可以指定返回值;

  18. display x 设置对表达式的展示,表达式x的值将在每次控制权转移到GDB下时打印一次;

  19. delete y 删除编号为y的断点,简写为d;

GDB点位:

  1. 监视点(watchpoint)。监视点是监视内存中某个地址,当该地址的数据被改变(或者被读取)时,程序交出控制权进入调试器。注意监视点分为软件模式和硬件模式:GDB 使用软件监视点的方式是在单步执行你的程序的同时测试变量的值,所以执行程序的速度会变慢。同时,软件监视点仅在当前线程有效。幸运的是,32 位的 Intel x86 处理器提供了 4 个特殊的调试寄存器用来方便调试程序,GDB 可以使用这些寄存器建立硬件监视点。GDB 总是会优先使用硬件监视点,因为这样不会减慢程序的执行速度。然而,可用的(enable的)硬件监视点的个数是有限的。如果你设置了过多的硬件监视点,当程序从中断的状态变为执行的状态(例如continue,until或者finish)时,GDB 可能无法把它们全部激活。另外,活动的硬件监视点的数量只有在试图继续执行程序时才能知道,也就是说,即使你设置了过多的硬件监视点,gdb在你运行程序之前也不会警告你。

    设置监视点的命令有3个:

    • watch(写监视)

    • rwatch(读监视)

    • awatch(读写监视)

      他们的使用方法一样,皆为以下几种:

    1. (r/a)watch x x是一个变量名。当x的值改变/被读取时,程序交出控制权进入调试器。

    2. (r/a)watch 0xN N为一个有效地址。当该地址的内容变化/被读取时,程序交出控制权进入调试器。

    3. (r/a)watch *(int *)0xN N为一个有效地址。当该地址的中的int指针指向的内容变化/被读取时,程序交出控制权进入调试器。

    4. (r/a)watch -l *(int *)0xN N为一个有效地址。当该地址的中的int指针指向的内容变化/被读取,或者该地址的内容变化/被读取时,程序交出控制权进入调试器。

      注意3和4的区别在于,当加入-l选项后,会同时监视表达式本身以及表达式指向的内容。

  2. 断点(breakpoint)。 断点是指当执行到程序某一步时,程序交出控制权进入调试器。值得注意的是,break会有一些变体:tbreak,hbreak,thbreak与rbreak。tbreak与break功能相同,只是所设置的断点在触发一次后自动删除。hbreak是一个硬件断点。thbreak则既是一个临时的硬件断点。注意硬件断点需要硬件支持,某些硬件可能不支持这种类型的断点。rbreak稍微特殊一些,它会在匹配正则表达式的全部位置加上断点。break家族的使用方法如下:

    1. (t/h)break x.cpp:y 。在代码x.cpp的第y行加入断点。x.cpp若不指定,则会以当前执行的文件作为断点文件。若程序未执行,则以包含main函数的源代码文件作为断点文件。若x.cpp和y都不指定,则以当前debugger的点作为断点处。

    2. (t/h)break 0xN。在地址N处加入断点。N必须为一个有效的代码段(code segment)地址。

    3. (t/h)break x.cpp:func。在x.cpp的func函数入口处加入断点。x.cpp可以不提供直接使用break func。注意由于重载(overload)的存在,因此gdb可能会询问你希望在哪个函数加上断点。你也可以通过指定参数类型来避免该问题,例如break func(int ,char *)

    4. (t/h)break +/-N。在当前运行处的第N行后/前加入断点。

    5. rbreak REGEXP。 在所有符合正则表达式REGEXP的函数入口加入断点。例如rbeak EX_* 表示在所有符合以EX_开头的函数入口处加入断点。

      注意break后面还有2个可选参数,线程id和条件。线程id指在info threads中的线程序号,而非系统提供的tid。例如break x.cpp:y 2 if (a==24),表示在2号线程的x.cpp的第y行加入断点,并且只有当a的值为24时,程序才会交出控制权进入调试器。

      另外,breakpoints可以通过save命令保存,以方便使用者下次再次进入程序调试时不需要重设断点。

  3. 捕捉点(catchpoint)。捕捉点是当某些事件发生时,程序交出控制权进入调试器。例如catch一个exception,assert,signal,fork甚至syscall。tcatch与catch功能一样,只是所设置的捕捉点在触发一次后自动删除。

  4. 跟踪点(tracepoint)。跟踪点与上面三个断点不同之处在于,它只是跟踪记录信息而不会中断程序的运行。当你的程序是realtime程序(如GUI),或者与其他的程序有交互时,你可能会希望使用跟踪点达到监视程序而又不破坏程序自身行为的目的。与断点相同的是,跟踪点会保存下在跟踪点时的一些内存信息供使用者查阅,例如数组或者对象。

    另外,tracepoints可以通过save命令保存,以方便使用者下次再次进入程序调试时不需要重设这些跟踪点。

  5. 检查点(checkpoint)

    gdb可以保存某一个时间点的程序状态或者说是程序映像,并且稍后又可以返回到这个状态。这个称之为checkpoint(就如同你玩游戏时的检查点。。。)。

    每个检查点是进程的一个拷贝。这样当一个bug很难重现,而又担心调试过头了又要从头开始重现时,可以在估计要重现这个bug之前,做一个checkpoint,这样即使debug过头了,也可以从这个checkpoint开始,而不用重启整个程序并且期待它重现这个bug(也许需要很久!!)。

    但是每个checkpoint有一个唯一的进程id,这个pid与原始程序的pid不同,因此如果程序需要使用pid的信息时,需要慎重考虑。

如果你觉得这篇教程很好的话,请将其分享出去!


题解 P2146 【[NOI2015]软件包管理器】

P2146 题解

关于树链剖分的教程

思路

这题就是一道树链剖分的模板题,用0和1分别代表每个软件的存在与否,那么“安装$k$”操作就是把从$1$到$k$的路径上的节点都置为$1$,而“卸载$k$”则是将$k$的子树都置为$0$,用树链剖分就可以十分方便地维护这两种操作。

然后对根节点求区间和就可以求出一共有多少个状态值为$1$(即安装了)的软件,用这个数减去上一次操作时的安装软件数即为改变的数目。


Tips:

  • “赋值”运算不能进行叠加,打延迟标记时要注意先将原有的延迟标记下传
  • 数据范围这么大一定要写快读

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
const int maxn=100005;
int n,m,last;
vector<int> e[maxn];
int father[maxn],dep[maxn],size[maxn],hson[maxn],top[maxn],seg[maxn],rev[maxn<<2],num[maxn],tot;
struct segmenttree{ //线段树
int l,r,sum,add=-1;
#define l(x) tree[x].l
#define r(x) tree[x].r
#define sum(x) tree[x].sum
#define add(x) tree[x].add
};
segmenttree tree[maxn<<2];
inline int readint() { //快读
int x=0;char ch=getchar();
while(ch<48||ch>57) ch=getchar();
while(ch>=48&&ch<=57) x=x*10+ch-48,ch=getchar();
return x;
}
inline void readchar(char * input) { //快读
int len=0;
char ch=getchar();
while(ch!=' ' && ch!='\r' && ch !='\n')
{
input[len++]=ch;
ch=getchar();
}
}
void addedge(int x,int y) //vector存图
{
e[x].push_back(y);
e[y].push_back(x);
}
void dfs1(int u,int f) //树剖预处理
{
size[u]=1;
father[u]=f;
dep[u]=dep[f]+1;
for(int i=0;i<e[u].size();i++)
{
int v=e[u][i];
if(v!=f)
{
dfs1(v,u);
size[u]+=size[v];
if(size[v]>size[hson[u]]) hson[u]=v;
}
}
}
void dfs2(int u,int f) //树剖预处理
{
if(hson[u])
{
seg[hson[u]]=++tot;
top[hson[u]]=top[u];
rev[tot]=hson[u];
dfs2(hson[u],u);
}
for(int i=0;i<e[u].size();i++)
{
int v=e[u][i];
if(!top[v])
{
seg[v]=++tot;
rev[tot]=v;
top[v]=v;
dfs2(v,u);
}
}
}
void build(int p,int l,int r) //线段树建树
{
int mid=(l+r)>>1;
l(p)=l;r(p)=r;
if(l==r){
sum(p)=num[rev[l]];
return;
}
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
sum(p)=(sum(p<<1)+sum(p<<1|1));
return;
}
void spread(int p) //下传延迟标记
{
if(add(p)>=0)
{
sum(p<<1)=add(p)*(r(p<<1)-l(p<<1)+1);
sum(p<<1|1)=add(p)*(r(p<<1|1)-l(p<<1|1)+1);
add(p<<1)=add(p);
add(p<<1|1)=add(p);
add(p)=-1;
}
}
int query(int p,int l,int r) //区间查询
{
if(l>r) swap(l,r);
if(l<=l(p) && r>=r(p)) return sum(p);
spread(p);
int mid=((l(p)+r(p))>>1);
int ans=0;
if(l<=mid) ans=(ans+query(p<<1,l,r));
if(r>mid) ans=(ans+query(p<<1|1,l,r));
return ans;
}
void update(int p,int l,int r,int c) { //区间更新
if(l>r) swap(l,r);
spread(p); //先将原有的延迟标记下传
if(l<=l(p) && r>=r(p)) {
sum(p)=c*(r(p)-l(p)+1);
add(p)=c;
return;
}
int mid=((l(p)+r(p))>>1);
if(l<=mid) update(p<<1,l,r,c);
if(r>mid) update(p<<1|1,l,r,c);
sum(p)=(sum(p<<1)+sum(p<<1|1));
}
void crange(int x,int y,int k) //路径修改
{
while(top[x]!=top[y]) {
if(dep[top[x]]<dep[top[y]]) swap(x,y);
update(1,seg[top[x]],seg[x],k);
x=father[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
update(1,seg[x],seg[y],k);
}
void cson(int x,int k) //子树修改
{
update(1,seg[x],seg[x]+size[x]-1,k);
}
int main()
{
n=readint();
for(int i=2,a;i<=n;i++){
a=readint();
addedge(i,a+1);
}
m=readint();
dfs1(1,0);
tot=seg[1]=1; //树剖初始化
top[1]=rev[1]=1;
dfs2(1,0);
build(1,1,n+1);
int last=query(1,1,n); //存好上一次的软件数
for(int i=1,x;i<=m;i++)
{
char op[20];
scanf("%s\n",op);
if (op[0]=='i') { //安装
x=readint();
crange(x+1,1,1);
int cur=query(1,1,n);
printf("%d\n",abs(last-cur)); //更新答案
last=query(1,1,n); //存好上一次的软件数
}
else if (op[0]=='u') { //安装
x=readint();
cson(x+1,0);
int cur=query(1,1,n);
printf("%d\n",abs(last-cur)); //更新答案
last=cur; //存好上一次的软件数
}
}
return 0;
}

使用EagleGet快速下载bilibili上的港澳台专属番剧

使用EagleGet快速下载bilibili上的港澳台专属番剧

众所周知,B站上有很多“港澳台专属”的番剧,比如
TIM20190827165832e1d0071ff60df52b.md.png

但是,这些福利满满无圣光的番剧因为众所周知的原因在大陆是无法观看的,而如果用梯子的话,你也会面临消耗过多流量以及网速慢的问题,而且B站的服务器位于国内,单纯为了伪装IP而浪费宝贵的代理流量并不合算。如何解决这个问题呢?

我们可以使用视频抓取,这个方法的原理是因为B站的服务器位于国内,因此我们可以先开梯子打开页面,等bilibili加载出视频后抓取视频,然后再关掉梯子下载,这样就既可以用直连的高网速下载,又不用浪费代理流量了!


软件:

  • EagleGet: 提供快速下载功能(单源下载神器,这个软件用来下载一些冷门链接非常快,而且是免费的,比某雷要强得多)
  • 任何一个有香港代理的梯子(这里推荐Windscribe
  • Chrome或Chromium浏览器(用于支持EagleGet插件)

准备EagleGet:

在浏览器的地址栏中输入http://www.eagleget.com,或点击链接直接访问,效果如图:TIM截图20190827175353.png

将鼠标悬浮在右上角的“DOWNLOAD”上会看到下拉菜单中有如下选项TIM截图20190827175922.png

准备EagleGet主体

单击EAGLEGET PORTABLE进入如下页面vSZmE9D7JupKfId100b68d998c81157.png

单击“DOWNLOAD EAGLEGET STABLE”下载EagleGet软件主体。如果你觉得官网的速度太慢了的话,也可以用我的网盘链接:链接

准备EagleGet插件

单击CHROME EXTENSION进入Chrome网上应用店(这步需要在Chrome和Chromium中进行)(这步可能需要开梯子…)
TIM2019082718214427781b5c1da322c5.png
单击安装至Chrome安装此扩展。

准备梯子:

看这篇教程

准备浏览器:

Chromium压缩包:链接


实际操作:

打开梯子,在B站找一部“仅限港澳台地区”的番剧,进入页面(这里以炎炎消防队第一集为例(这个视频8分15秒有一个圣光镜头…))
TIM20190827183306461eec262226801c.png

重头戏来了!

同时按”control”键,”shift”键和”I”键启动开发者工具

TIM20190828115949ec136e4de023de21.png

点击右上角的”Network”进入网络请求界面

TIM20190828120031adb629afaed9eb6f.png

接下来刷新页面以加载网络请求,刷新之后,这个界面就变成了这样:

TIM2019082812321767479674bb7169b1.png

耐心等待,直到视频加载完成(毕竟用了梯子以后网速会变慢很多)

TIM20190828123246b58d08b727e9dd85.png

等到视频加载完成后,在左上角的”Filter”栏中输入”flv”(B站的视频资源是以flv格式存储的)过滤视频文件

TIM20190828123408712a2c643defc935.png

过滤后,在底部的请求栏中找到一个类型为”video/x-flv”的请求,单击它查看它的详细信息

TIM20190828123438f99b61e46c8d7503.png

复制”Request URL”链接,这时候如果你的EagleGet插件工作正常的话已经弹出下载任务界面了。如果并没有弹出,那么打开EagleGet主界面

TIM截图20190828123623.png

单击左上角的“✚”进入添加任务的界面,在上面的链接栏中粘贴刚才复制的链接

TIM截图20190828123549.png

EagleGet高速的秘密

单击左边的“连接”,进入连接设置,将“该任务的最大线程数”设为32(默认是8),如图

TIM截图20190828123603.png

开始下载,设置最大线程数以后,下载速度可以加速到5~6MBs(够快的),很快就可以下载完成(再一次证明了B站的服务器位于国内)。

下载完成后,使用格式转换软件将下载的flv视频转化为MP4格式即可(这里用的是格式工厂
TIM截图20190828133356.png


效果:

放两张图让大家对比一下(炎炎消防队第一集 08:15):

圣光版:

TIM20190828134126f904401b17741dac.png

无圣光版:

TIM201908281342024ffdd3fa7b674471.png


如果你觉得这篇教程很好的话,请将其分享出去!

ps:二次元图片建议使用看见图床分享,无须担心删图,封号问题


题解 P4513 【小白逛公园】

P4513 题解

这还是我第一次给紫题写题解。。。


题目大意:

给定$n$个公园的美观值(可能有负数),求出美观值和最大的连续花园区间 $[l,r]$

实际上就是求区间最大子段和。。。


思路:

这是一道典型的区间统计问题,对于区间统计问题,我们一般使用线段树解决

线段树教程

为了求出区间最大子段和,对于每个区间x,我们需要计算以下四个值:

1
2
3
4
sum[x] : x所代表区间的区间和
ldat[x] : 紧靠区间左端的最大子段和
rdat[x] : 紧靠区间右端的最大子段和
dat[x] : 区间最大子段和

这些值如何求出呢?

首先,我们考虑$dat$:

无标题2.png

对于一个区间的$dat$,它只能由三个途径得来:

  1. 完全在左子区间,即左子区间的$dat$(绿色部分)
  2. 完全在右子区间,即右子区间的$dat$(红色部分)
  3. 跨越中点,即左子区间的$rsum$加上右子区间的$lsum$(黄色部分)

那么,如何求出$ldat$和$rdat$呢?

由于$ldat$和$rdat$的求法相似,只是方向不同,这里只考虑$ldat$的求法 $\dots$

无标题3.png

$ldat$更加简单,只有两种情况:

  1. 完全在左子区间,即左子区间的$ldat$(绿色部分)
  2. 跨越中点,即左子区间的$sum +$ 右子区间的 $ldat$(红色部分)

看到这里,相信大家都已经知道$rdat$怎么求了,这里就不在赘述。。。

至此,问题得到完美解决 $\dots$

怎么可能


Tips:

  1. 测试数据可能会出现$a>b$的情况,需要进行交换…(血的教训)
  2. 查询时要同时返回4个数据并按要求归并…

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=500001;
int n,m;
struct segment_tree{
int l,r;
int sum,lsum,rsum,dat;
};
segment_tree tree[maxn*4];
//宏定义
#define l(x) tree[x].l
#define r(x) tree[x].r
#define sum(x) tree[x].sum
#define lsum(x) tree[x].lsum
#define rsum(x) tree[x].rsum
#define dat(x) tree[x].dat
int read()//快读
{
int s=0,w=1;
char c=getchar();
while(c<'0' || c>'9')
{
if(c=='-') w=-1;
c=getchar();
}
while(c>='0' && c<='9')
{
s=(s<<3)+(s<<1)+(c^48);
c=getchar();
}
return s*w;
}
void update(int p)//归并信息
{
sum(p)=sum(p<<1)+sum(p<<1|1); //区间和
lsum(p)=max(lsum(p<<1),sum(p<<1)+lsum(p<<1|1)); //紧靠区间左端的最大子段和
rsum(p)=max(rsum(p<<1|1),sum(p<<1|1)+rsum(p<<1));//紧靠区间右端的最大子段和
dat(p)=max({dat(p<<1),dat(p<<1|1),rsum(p<<1)+lsum(p<<1|1)}); //区间最大子段和
}
void build(int p,int l,int r) //建树
{
l(p)=l,r(p)=r;
if(l(p)==r(p)){ //如果是叶子结点
sum(p)=lsum(p)=rsum(p)=dat(p)=read(); //初始化的同时读入,高效建树
return;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
update(p);
}
void change(int p,int addr,int c) //单点修改
{
if(l(p)==r(p))
{
sum(p)=lsum(p)=rsum(p)=dat(p)=c;
return;
}
int mid=(l(p)+r(p))>>1;
if(addr<=mid) change(p<<1,addr,c);
else if(addr>mid) change(p<<1|1,addr,c);
update(p);
}
segment_tree ask(int p,int l,int r) //区间查询(要同时返回4个数据)
{
if(l<=l(p) && r>=r(p)) return tree[p];
int ans=0xc0c0c0c0;
int mid=(l(p)+r(p))>>1;
if(r<=mid) return ask(p<<1,l,r);
if(l>mid) return ask(p<<1|1,l,r);
else{
segment_tree x,y,ans;
x=ask(p<<1,l,r),y=ask(p<<1|1,l,r);
ans.sum=x.sum+y.sum;
ans.lsum=max(x.lsum,x.sum+y.lsum);
ans.rsum=max(y.rsum,y.sum+x.rsum);
ans.dat=max({x.dat,y.dat,x.rsum+y.lsum});
return ans;
}
// return ans;
}
int k,a,b;
int main()
{
n=read(),m=read();
build(1,1,n);
for(int i=1;i<=m;i++)
{
k=read();
if(k==1)
{
a=read(),b=read();
if(a>b) swap(a,b);
printf("%d\n",ask(1,a,b).dat);
}
else if(k==2)
{
a=read(),b=read();
change(1,a,b);
}
}
return 0;
}

【算法笔记】树链剖分

【算法笔记】树链剖分

强烈建议在阅读本文之前已经掌握前置知识 线段树,如果你没有,请先阅读这篇文章

不知道树是什么的,请前往搜狗百科-树

树链剖分,又名轻重路径剖分、树剖,是一种 看起来十分高大上实际很水的能让你代码强行增加180行的不那么容易爆炸(并不)的算法,本质上是将树转化为一系列重链轻边(这两个东西的定义后边会讲),然后用线段树(或一切支持区间修改和查询操作的数据结构,但其中线段树能维护的信息最广泛)进行存储。

树链剖分十分实用(前提是你线段树写的很熟练,不然满屏RE。。。),能将复杂的树上维护转化为简单相对不那么复杂的区间维护。

树链剖分的作用有:

  • 证明出题人是个毒瘤
  • 修改静态树上两点间最短路径上的所有点权(边权可以边转点解决)
  • 查询静态树上两点间最短路径上的点权和及最值(或任何你可以想到的满足区间可加性的信息)
  • 修改一个点及其子树上的所有点权
  • 查询一个点及其子树上的所有点权和及最值(其他信息同上)

树剖也能解决,但一般不用树剖解决的问题有:

  • 求LCA(60行和180行你选哪个)
  • 只维护树上两点间最短路径上的所有点权(树上差分就可以)
  • 只查询树上两点间最短路径上的点权和(依然是树上差分)

思路

首先给出几个定义:

  • 重儿子:一个节点的子树中节点数最多的子树的根(如果有多个可以取任意一个)
  • 重链:由重儿子连接形成的链
  • 轻边:树中不属于重链的其他边

树链剖分示意,其中点上的数是编号,加粗的边为重边:

5c24d0664c185.png

上面的图中,点1,2,3,4,5,6构成一条重链,点7,8,9,11,13构成一条重链,点12、14分别构成两条长度为1的重链(自己)

树链剖分的性质:

  • 树上的所有点属于且仅属于一条重路径
  • 设size[x]为x的子树大小,则如果(u,v)为轻边,size[u]<=size[u]/2(因为u已经有一个重儿子,而如果v的子树大小超过u的一半,则v应该是重儿子)
  • 因此,对于任何非根节点u,在u到根的路径上,轻边和重链最多有 $logn$条

实现

预处理

为了预处理树剖的操作,我们需要计算如下几个值:

1
2
3
4
5
6
7
8
对树中的每一个节点x
father[x]:x在树中的父亲
dep[x]:x的深度
size[x]:x的子树节点数
hson[x]:x的重儿子
top[x]:x所在重链的顶部节点(深度最小)
seg[x]:x在线段树中的位置(下标)
rev[x]:线段树中第x个位置对应的节点编号

我们需要两遍dfs来计算这些值,第一次DFS可以计算前四个值,第二次DFS可以计算后三个值。预处理代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
void dfs1(int u,int f) {
size[u]=1; //子树大小默认为1
dep[u]=dep[f]+1; //深度
father[u]=f; //记录父亲
for(int i=0;i<e[u].size();i++)
{
int v=e[u][i]; //使用vector存图
if(v!=f)//排除父亲
{
dfs1(v,u);
size[u]+=size[v]; //累加子树大小
if(size[v]>size[hson[u]]) hson[u]=v; //如果v的子树大小比当前重儿子的大小大那么更新重儿子
}
}
}

void dfs2(int u,int f) {
if(hson[u]) //先走重儿子,使重儿子在线段树中的序号连续,这样才能用区间操作维护重链信息
{
seg[hson[u]]=++tot;//插入点
top[hson[u]]=top[u];//u和重儿子同属于一条重链
rev[tot]=hson[u]; //此时tot为当前点
dfs2(hson[u],u);
for(int i=0;i<e[u].size();i++)
{
int v=e[u][i];
if(v!=f && v!=hson[u]) //排除父亲也不是重儿子
{
seg[v]=++tot;
top[v]=v; //轻儿子一定是重链的顶部节点
rev[tot]=v;
dfs2(v,u);
}
}
}
}

int main() //主函数
{
/*other codes*/
dfs1(root,0);
seg[root]=tot=1;
rev[1]=top[root]=root;
dfs2(root,0)
build(1,1,n);
/*other codes*/
}

操作

1.路径查询

给定两个点x,y,统计x到y最短路径上的信息:

  • 如果x、y属于一条重链(即top[x] $=$ top[y]),那么直接进行一次线段树的区间查询即可
  • 如果x、y属于两条重链(即top[x] $\ne$ top[y]),那么一定是由x走到 $LCA(x,y)$ 再走到y,此时
    • 首先找到top深度较大的点(因为LCA一定不可能在顶部节点深度较大的重链上)
    • 假设这个点是x,那x可以直接跳到father[top[x]],并在线段树上统计[seg[x]~seg[top[x]]]的信息(这会使x跳到一条离根更近的重链上)
    • 重复上面的操作直到top[x] $=$ top[y],此时用一次区间查询统计[x~y]的信息

代码(以统计和为例):

1
2
3
4
5
6
7
8
9
10
11
12
13
int qrange(int x,int y)
{
int ans=0;
while(top[x]!=top[y]) { //当x、y属于两条重链
if(dep[top[x]]<dep[top[y]]) //找到top深度较大的点
swap(x,y);
ans+=query(1,seg[top[x]],seg[x]); //区间查询,统计[seg[x]~seg[top[x]]]的信息
x=father[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
ans+=query(1,seg[x],seg[y]);//统计[x~y]的信息
return ans;
}

2.路径修改

给定两个点x,y,更新x到y最短路径上的信息:

方法同上,只不过将区间查询换成区间修改。
代码:

1
2
3
4
5
6
7
8
9
10
11
void crange(int x,int y,int k)
{
while(top[x]!=top[y]) { //当x、y属于两条重链
if(dep[top[x]]<dep[top[y]]) //找到top深度较大的点 swap(x,y);
swap(x,y);
update(1,seg[top[x]],seg[x],k); //更新[seg[x]~seg[top[x]]]的信息
x=father[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
update(1,seg[x],seg[y],k);//更新[x~y]的信息
}

3.子树查询

统计x及其子树上的信息:

这个更简单了,由于x的子树在线段树上是连续的,同时size[x]又储存了x的子树大小,因此直接用一次区间查询统计[x~x+size[x]-1]上的信息即可

代码:

1
2
3
4
int qson(int x)
{
return query(1,seg[x],seg[x]+size[x]-1);
}

3.子树修改

更新x及其子树上的信息:

方法同上,只不过将区间查询换成区间修改。
代码:

1
2
3
4
void cson(int x,int k)
{
update(1,seg[x],seg[x]+size[x]-1,k);
}

例题


题解 P1063 【能量项链】

P1063 题解

这题建议在做完P1880 石子合并之后再做,思路其实和这题差不多


思路

这是一道经典的区间动规题,对于这种题我们一般用记搜解决(其实是因为刷表法过于抽象$\dots$ )

首先是珠子的处理,这里有一个问题:前一颗珠子的头标记后一颗珠子的尾标记,在DP时要特别注意这一点。另外一个问题就是珠子是成环状的,这样的环我们要使用拆成链后复制一遍接在环尾的方法,看代码:

1
2
3
4
5
6
7
8
//由于前一颗珠子的头标记是后一颗珠子的尾标记,
//因此我们可以用a数组直接同时存储当前竹子的头标记和上一颗珠子的尾标记
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[i+n]=a[i]; //复制一遍接在环尾
}
a[2*n+1]=a[1]; //最后一颗珠子的尾标记

接下来是DP的部分,DP的思想其实就是:(为了方便,这里用head[x]和tail[x]来代指x的头标记和尾标记(就是原数组中的a[x]和a[x+1])

设分界点为m,则合成l到r的总收益$=$合成head[l]到tail[m-1]的总收益(因为要使l和m接触)$+$合成head[m+1]到tail[r]的总收益 (因为要使m和r接触)$+$head[l]$\times$tail[m]$\times$tail[r] (再合并l和r)

画成图就是这样子:

当然,如果区间只有2项,则只能在l处合并,因此其总收益$=$head[l]$\times$tail[l]$\times$tail[r]

接下来就可以给出DP代码了:

1
2
3
4
5
6
7
8
9
10
11
12
13
//f为记忆化数组
int dp(int l,int r)
{
int ans=0;
if(f[l][r]!=0) return f[l][r];
if(l==r-1) return a[l]*a[r]*a[r+1];//边界(只有2项)
for(int k=l;k<r;k++)//枚举分界点
{
//注:a[x+1]就是tail[x]
ans=max(ans,dp(l,k)+dp(k+1,r)+a[l]*a[k+1]*a[r+1]);//更新答案
}
return f[l][r]=ans;//返回并记忆化
}

由于环拆成链后一共有n种可能的开头,所以需要n次DP计算出答案

代码:

1
2
3
4
5
int ans=0;
for(int i=1;i<=n;i++)
{
ans=max(ans,dp(i,i+n-1));//head[i]到tail[i+n]就是a[i]到a[i+n-1]
}

关于时间复杂度

这题的时间复杂度很多人认为是$O(n^4)$,会超时,但其实并不是这样。这个算法的实际复杂度其实是$O(n^3)$。

为什么呢?因为在执行下一次DP时,上一次DP计算出的值是可以直接使用的。

让我们模拟一下算法执行的过程:(设n=5)

第一次DP时,要计算$n^2$个值,如图所示:(图中的绿色部分)

TIM截图20191024215559.png

这时,需要计算$n^2$个值,每个值需要$O(n)$的时间去计算,因此第一次DP的总复杂度为$O(n^3)$。

第二次DP时,图形变成了这样:

TIM截图20191024220023.png

这时,图中的黄色部分是已经计算好的值,可以直接使用,只有红色部分需要计算,而这样的格子一共有$2n-1$个,因此第二次DP只需要$O(n^2)$的时间去计算,第3~n次DP同理。

所以,整个算法的时间复杂度为$O(n^3+n(2n-1)\times n)=O(n^3)$。

(话说我好像是唯一一篇有时间复杂度分析的题解…)

代码

关键部分的注释之前已经给过了,这里就不给了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=201;
int f[maxn][maxn];
int n,a[maxn];
int dp(int l,int r)
{
int ans=0;
if(f[l][r]!=0) return f[l][r];
if(l==r-1) return a[l]*a[r]*a[r+1];
for(int k=l;k<r;k++)
{
ans=max(ans,dp(l,k)+dp(k+1,r)+a[l]*a[k+1]*a[r+1]);
}
return f[l][r]=ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[i+n]=a[i];
}
a[2*n+1]=a[1];
int ans=0;
for(int i=1;i<=n;i++)
{
ans=max(ans,dp(i,i+n-1));
}
cout<<ans<<endl;
return 0;
}

欢迎来到博客


【数据结构】线段树

线段树

线段树是什么?

线段树是一种能让你代码强行增加50行的极容易爆炸的万金油数据结构,用于优雅暴力地解决对一个区间上满足区间可加性(即可由两个子区间的信息得到当前区间信息)区间修改和区间查询问题。

结构:

将区间划分为左端点到中点(即左子区间)和中点+1到右端点(即右子区间)的两个子区间,然后对两个子区间继续划分,直到划分到单个元素(即左端点=右端点)

示意图:
c0dd297d009ddb5d3d37da29c291da7c07e3cb5a0c40b2ec.png

不难看出线段树除了最下面一层,其他的部分一定是一颗完全二叉树,这意味着整棵树可以使用“父子二倍法”(左儿子编号为父亲编号 $\times$ 2,右儿子编号为父亲编号 $\times$ 2 $+$ 1)存储在一个数组中。同时,因为还要考虑到最后一层,数组的大小应开到n $\times$ 4大小。

线段树的一个很重要的性质就是一棵[1~n]的线段树的深度最大为 $log_2 n+1$,这也意味着线段树可在$O(logn)$的时间复杂度内完成所有操作。


实现

洛谷P3372 【模板】线段树 1的维护最大值为例
首先,我们给线段树中每个元素一个sum变量存储该元素代表区间的区间和,叶子结点的sum是原数组当前位置的值,非叶节点的sum是其左右子节点sum的和,如当原数组为
3dd6bf7464e1e756f.png

时,对应的线段树为2cd920dd97dbafe0d.png

节点结构体:

1
2
3
4
5
6
7
8

struct segmenttree{
int l,r,sum,add;
#define l(x) tree[x].l //当前区间左端点
#define r(x) tree[x].r //当前区间右端点
#define sum(x) tree[x].sum //区间和
#define add(x) tree[x].add //延迟标记(这个后面会讲)
}tree[maxn];

操作

操作有递归和非递归两种形式,递归式相对于非递归式更直观,因此这里讲解递归式。

非递归式和递归式本同末异,考试时按照数据规模而定。

建树:

按照之前提到的定义,从根节点([1~n])向左右两边递归,递归到叶子结点就将该节点sum设为其在原数组中对应的值,回溯时将当前节点的sum设为其左右子节点sum的和。

代码:

1
2
3
4
5
6
7
8
9

void build(int p,int l,int r)
{
l(p)=l;r(p)=r; //设置端点
if(l==r) { sum(p)=num[l]; return;} //如果是叶子节点
int mid=((l+r)>>1); //位运算,右移1位相当于/2,左移同理
build(p<<1,l,mid); //向左递归
build(p<<1|1,mid+1,r) //向右递归,一个偶数|1相当于+1
}

复杂度为$O(nlogn)$

区间查询:

设查询区间的左端点为 $l$,右端点为 $r$,当前区间的左端点为 $l_1$,右端点为 $r_1$,中点为$mid$ ,则

  • 当 $l \leq l_1$ 且 $r \geq r_1$时 直接返回当前区间的sum,因为当前区间已经涵盖了子区间的全部信息
  • 当 $l \leq mid$时,向左递归,$r_1=mid$(此时查询区间一定涵盖左子区间的一部分)
  • 当 $r > mid$时,向右递归,$l_1=mid+1$ (此时查询区间一定涵盖右子区间的一部分)

代码:

1
2
3
4
5
6
7
8
9
10

int query(int p,int l,int r)
{
if(l<=l(p) && r>=r(p)) return sum(p); //完全包含
int mid=((l(p)+r(p))>>1);
int ans=0;
if(l<=mid) ans+=query(p<<1,l,mid); //向左递归,累加左子树答案
if(r>mid) ans+=query(p<<1|1,mid+1,r); //向右递归,累加左子树答案
return ans;
}

复杂度为$O(logn)$

区间修改与延迟标记:

当进行区间修改时,我们依然可以设查询区间的左端点为 $l$,右端点为 $r$,当前区间的左端点为 $l_1$,右端点为 $r_1$,中点为$mid$,同时查询操作也满足这两条性质:

  • 当 $l \leq mid$时,向左递归,$r_1=mid$(此时查询区间一定涵盖左子区间的一部分)
  • 当 $r > mid$时,向右递归,$l_1=mid+1$ (此时查询区间一定涵盖右子区间的一部分)

但当出现完全覆盖的情况时,事情就变得不那么简单了,一个一个深入更新会使单次修改的复杂度高达 $O(n)$,这是我们所无法接受的。这时,我们就要引入延迟标记

试想一下,如果你花费很大的代价更新了节点p的子树,但在之后的查询中却根本没有访问到它们,那更新p的子树岂不是白费力气?因此,我们可以在区间修改出现“完全覆盖”情况时也直接返回,但要给当前节点打上一个代表“当前节点已被更新,但其子节点尚未被更新”的延迟标记(这里取名add)。(如果操作是相容的(如加法),那在打标记前无需下传原来的标记。如果操作是不相容的(如赋值),那在打标记前需下传原来的标记。)

在以后的查询操作中,如果遇到了有延迟标记的节点,便将其的两个子节点更新并打上延迟标记,并擦除当前节点的延迟标记(即将延迟标记下传一层),这样就减少了大量无用的更新操作 (虽然本质上依旧是暴力)

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

void spread(int p) //下传标记
{
if(add(p))
{
add(p<<1)+=add(p);
add(p<<1|1)+=add(p);
sum(p<<1)+=add(p)*(r(p<<1)-l(p<<1)+1); //区间和增量=数值增量*区间长
sum(p<<1|1)+=add(p)*(r(p<<1|1)-l(p<<1|1)+1); //区间和增量=数值增量*区间长
add(p)=0;
}
}

int query(int p,int l,int r)
//更新后的区间查询,增加了下穿标记的操作
{
if(l<=l(p) && r>=r(p)) return sum(p); //完全包含
spread(p);//下传标记
int mid=((l(p)+r(p))>>1);
int ans=0;
if(l<=mid) ans+=query(p<<1,l,mid);
if(r>mid) ans+=query(p<<1|1,mid+1,r);
return ans;
}

void update(int p int l,int r,int c)
{
if(l<=l(p) && r>=r(p)){
sum(p)+=c*(r(p)-l(p)+1); //区间和增量=数值增量*区间长
add(p)+=c;
return;
}
spread(p);//下传标记
int mid=(l(p)+r(p))>>1;
if(l<=mid) update(p<<1,l,r,c); //更新左子树
if(r>mid) update(p<<1|1,l,r,c); //更新右子树
sum(p)=sum(p<<1)+sum(p<<1|1); //更新当前点
}

复杂度为$O(logn)$


例题:


【算法笔记】快速幂

【算法笔记】快速幂

其实写这篇文章的主要目的是练习LATEX(大雾)

朴素地计算幂的方法就是计算出$b$个$a$的乘积,即
$$ \prod_{i=1}^b a=\underbrace{a \times a \times a \times \dots \times a}_b $$
(因为这篇文章主要介绍快速幂,代码就不贴了)

但是很明显,如果用这个算法去计算$2^{100000000000000}$,那么一定会T飞,原因很简单:
这个算法的时间复杂度是$O(n)$,对于计算幂这样频繁的操作来说代价太大了。

于是,我们就有了快速幂。

快速幂,又称平方求幂法,是一种基于分治思想在 $O(logn)$ 的时间复杂度内求幂的方法。

首先,一个显而易见的事实是:
$$ n^a \times n^b=n^{a+b} $$

于是当n为奇数有:
$$ a^b=a^{ \lfloor\frac{n}{2}\rfloor + \lfloor\frac{n}{2}\rfloor + 1} $$
当n为偶数有:
$$ a^b=a^{ \frac{n}{2} + \frac{n}{2}} $$
所以
$$ a^b=\begin{cases}
a &b=1 \cr
a^{\lfloor\frac{n}{2}\rfloor} \times a^{\lfloor\frac{n}{2}\rfloor} \times a &b \nmid 2 \cr
a^{\frac{n}{2}} \times a^{\frac{n}{2}} &b\mid 2
\end{cases} $$

快速幂代码如下:

1
2
3
4
5
6
int ksm(int a,int b)
{
if(b==1) return a;
else if(b%2==1) return ksm(a,b/2)*ksm(a,b/2)*a;
else return ksm(a,b/2)*ksm(a,b/2)
}

快速幂取模

有时候,因为求出的幂太大,我们不仅想要求出幂,还想求出幂对一个指定的数取模的结果,这时候,我们就要利用余数的可乘性,即

(a mod m) * (b mod m) = (a*b) mod m

(抱歉这里用不了LATEX)

方法很简单,在快速幂计算时的每一处乘法加上取模就可以了
代码如下:

1
2
3
4
5
6
int ksm(int a,int b,int mod)
{
if(b==1) return a;
else if(b%2==1) return (((ksm(a,b/2,mod)*(ksm(a,b/2,mod))%mod*a)%mod;
else return ((ksm(a,b/2,mod)*(ksm(a,b/2,mod))%mod;
}

题解 P1462 【通往奥格瑞玛的道路】

P1462 题解


题目大意:

给定一个$n$个点的无向图,求在满足从$1$到$n$的最短路边权和 $\leq b$ 的情况下,所经过的点的最大点权的最小值。

思路:

带有 “最大值最小” 的“双最”字样的最优化题目一般比较难直接求解,这时候我们不妨用二分的思想,将最优化问题转换为判断合法性问题。

二分代码模板:

1
2
3
4
5
6
7
while(l<=r)
{
mid=(l+r)>>1;
if(check(mid)) ans=mid,r=mid-1; //如果解合法,记录答案并缩小左边界
else l=mid+1;//否则缩小右边界
}
cout<<ans<<endl;

check()函数的设计:

首先,假设我们已经找到了一个解 $val$,那么所有点权 $> val$的点就不能被访问了(因为如果这样做就不满足解)。然后再求出$1$到$n$的最短路 (SPFAer和Dijkstrer们可以不要争了,这个优先队列BFS就可以做,还比你们都快 233),之后判断最短路的权值和是否 $\leq b$ ,如果不满足则说明解不合法 (会被揍死)

一些小坑点:

  • 二分时需要判断 “无论如何也无法到达的情况”
  • fi≤1000000000,因此直接二分会T飞,要先离散化;
  • ci≤1000000000,记得开 long long 不然炸飞;

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<cstring>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
const int maxn=10005;
typedef long long ll;
int n,m,b;

inline ll read()//快读
{
ll s=0,w=1;
char c=getchar();
while(c<'0' || c>'9'){
if(c=='-') w=-1;
c=getchar();
}
while (c>='0' && c<='9') {
s=(s<<3)+(s<<1)+(c^48);
c=getchar();
}
return s*w;
}

/**
* BFS的记录结构体
* @param cur 当前点
* @param c 已经扣掉的血量
*/
struct note{
ll cur,c;
note(ll a,ll b):cur(a),c(b) {}
note() {}
};
//没什么好说的,比较运算符
struct cmp{
bool operator () (note a,note b)
{
return a.c>b.c;
}
};
//pbds的黑科技堆,详细描述可以看这里:https://blog.xehoth.cc/pb-ds-PriorityQueue/
typedef __gnu_pbds::priority_queue<note,cmp,__gnu_pbds::pairing_heap_tag> heap;

//vector数组存图
struct edge{
ll to;ll w;
edge(ll a,ll b):to(a),w(b) {}
edge() {}
};
vector<edge> e[maxn];
ll v[maxn];//点权数组
/**
* 增加一条x到y,权值为w的边
*/
inline void addedge(ll x,ll y,ll w)
{
e[x].push_back(edge(y,w));
}

//BFS部分
bool vis[maxn];
ll bfs(ll val)
{
memset(vis,0,sizeof(vis));
heap q;
q.push(note(1,0));
vis[1]=true;
while(!q.empty())
{
note cu=q.top();
q.pop();
if(cu.cur==n){
return cu.c;
}
ll& st=cu.cur;
ll& co=cu.c;
for(int i=0;i<e[st].size();i++)
{
ll& to=e[st][i].to;
if(!vis[to] && v[to]<=val)
{
q.push(note(to,co+e[st][i].w));
vis[to]=true;
}
}
}
return 0x3f3f3f3f;//如果到不了返回无穷大
}

ll lsv[maxn];//离散数组
int main()
{
n=read(),m=read(),b=read();
for(int i=1;i<=n;i++) lsv[i-1]=v[i]=read();
for(int i=1,x,y,w;i<=m;i++) {
x=read(),y=read(),w=read();
if(x!=y) addedge(x,y,w),addedge(y,x,w);
}
//离散化
sort(lsv,lsv+n);
int sz=unique(lsv,lsv+n)-lsv;
//二分
int l=0,r=sz,mid,ans=-1;
while(l<=r)
{
mid=(l+r)>>1;
if(bfs(lsv[mid])<=b) ans=mid,r=mid-1;
else l=mid+1;
}
if(ans==-1){//如果答案没被更新过即为“不可到达”
printf("AFK\n");
return 0;
}
else printf("%lld\n",lsv[ans]);//输出答案
}

总时间复杂度:$O(nlogn * logn) = O(nlog^2 n)$,比几乎所有题解都要快


题解 P3353 【在你窗外闪耀的星星】

P3353 题解


在做P1502 窗口的星星时偶然发现了这道题,看到这题的名字以后好奇心大增,就决定点进去看看。。。

本来看到这只是道黄题没打算做,直到这题超级长的题面让我想起了我在学校的【已编辑】,于是决定A之以明志


题目大意

天空中有$n$颗星星,求宽度为$W$的窗户(高度无限)最多能圈住亮度为多少的星星。

仔细分析后,我们发现我们可以将天空视作一个数轴,将$x$坐标相等的星星亮度累加在一起(反正$y$坐标没用),然后依次统计出每个长度为$W$的区间和,最后求最大值就可以了。


暴力算法

由上面的题目大意,可以十分直接地得到一个暴力算法——由$W$到最大的$x$坐标循环枚举,每次用循环求出$i-w$到$i$的区间和,然后取最大值

期望得分:(想要期望得分?这玩意估计也只能对拍用)


正解——前缀和

首先,我们要介绍一下前缀和

前缀和,指在一个序列中由序列起始位置到当前位置的和,如
$$Sum_i=A_1+A_2+A_3+A_4+···+A_i$$

前缀和的作用是 $O(1)$ 地维护静态区间和,原理为:
$$Sum_i=A_1+A_2+A_3+A_4+···+A_i$$

$$Sum_j=A_1+A_2+A_3+A_4+···+A_j,j>i$$

则$Sum_j$一定包含$Sum_i$,即
$$Sum_j=A_1+A_2+A_3+A_4+···+A_i+A_(i+1_)+···+A_j$$


$$Sum_j-Sum_i=(A_1+A_2+A_3+A_4+···+A_i+A_(i+1_)+···+A_j)$$
$$-(A_1+A_2+A_3+A_4+···+A_i)=A_(i+1_)+A_(i+2_)+···+A_j$$
所以
$$ A_(i+1_)+A_(i+2_)+···+A_j$$
即为i到j的区间和

由此,我们可以得出最后的思路——在输入完成后,$O(n)$ 预处理出前缀和数组sum,然后对每个区间和操作,返回sum[i]-sum[i-w] (因为只有i-w+1 ~ i会被计算),然后取最大值即可。

至此,问题得到完美解决。完结撒花

贴代码~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include<iostream>
#include<algorithm>
using namespace std;
const int maxw=100005;
long long n,w,x,b;
long long maxx=0,ans=0;
long long br[maxw];//亮度数组
long long sum[maxw];//前缀和数组
int main(int argc, char const *argv[]) {
ios::sync_with_stdio(false);//流式I/O速度优化
cin.tie(0);//流式I/O速度优化
cin>>n>>w;
for(int i=1;i<=n;i++)
{
cin>>x>>b;
br[x]+=b;//向指定的X坐标累加亮度
maxx=max(maxx,x);//更新x的最大值
}
for(int i=1;i<=maxx;i++) sum[i]=sum[i-1]+br[i];//递推处理前缀和数组
for(int i=w;i<=maxx;i++)
{
ans=max(ans,sum[i]-sum[i-w]);//区间和与取最大值
}
cout<<ans<<endl;
return 0;
}