休息日 - “曾经沧海难为水”
2026-07-16 20:27:23
发布于：浙江
自主学习类笔记，没有学习价值。
”曾经沧海难为水，除却巫山不是云。“——元稹《离思五首·其四》
——————————————————————————————————————————
休息日排一下要做的题目：
1.5道线段树 3.5h
2.2道树状数组 2.5h
3.简单贪心3道 1.5h
4.简单搜索2道（带剪枝）2h
5.简单搜索1道（A*） 1h
6.简单搜索1道(ID A*) 1h
7.复习凸包，尝试再次理解
8.简单动态规划3道（线性，背包。橙-黄）
9.二分答案两题 2h
感觉是写不完，挑点想写的砸吧砸吧好了。
线段树
线段树1：复习模板 https://www.luogu.com.cn/problem/P3372
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int a[N*4],w[N*4],lzy[N*4];
void pushup(int u){
w[u]=w[u*2]+w[u*2+1];
}
void build(int u,int l,int r){
if(l==r){
w[u]=a[l];
return;
}
int mid=(l+r)>>1;
build(u*2,l,mid),build(u*2+1,mid+1,r);
pushup(u);
}
void get_lzy(int x,int l,int r,int val){
lzy[x]+=val;
w[x]+=(r-l+1)*val;
}
void pushdown(int u,int l,int r,int mid){
get_lzy(u*2,l,mid,lzy[u]);
get_lzy(u*2+1,mid+1,r,lzy[u]);
lzy[u]=0;
}
void add(int u,int l,int r,int L,int R,int val){
if(r<L||R<l)return;
if(L<=l&&r<=R){
get_lzy(u,l,r,val);
return;
}
int mid=(l+r)>>1;
pushdown(u,l,r,mid);
add(u*2,l,mid,L,R,val),add(u*2+1,mid+1,r,L,R,val);
pushup(u);
}
int ask(int u,int l,int r,int L,int R){
if(r<L||R<l)return 0;
if(L<=l&&r<=R){
return w[u];
}
int mid=(l+r)>>1;
pushdown(u,l,r,mid);
return ask(u*2,l,mid,L,R)+ask(u*2+1,mid+1,r,L,R);
}
signed main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
build(1,1,n);
for(int i=1;i<=m;i++){
int zz;
cin>>zz;
if(zz==1){
int x,y,k;
cin>>x>>y>>k;
add(1,1,n,x,y,k);
}else{
int x,y;
cin>>x>>y;
cout<<ask(1,1,n,x,y)<<'\n';
}
}
return 0;
}
容易写错的地方：
1.开 long long
2.四倍空间
3.函数传参位置错误（改了一下get_lzy传入参数的位置从(u,l,val,r)改成了(u,l,r,val)）但是前面写的用get_lzy函数的地方没有改，所以错了（这个错误还挺难调出来的，所以建议一开始就弄好）
小白逛公园
求动态最大子段和喵。
发现不能只维护“当前区间内的最大子段和”，否则就无法汇总到父节点上。
父节点的最大子段和只存在以下三种情况：
1.是左子节点的最大子段和
2.是右子节点的最大子段和
3.是左子节点和右子节点的两段相邻数值拼在一起的和
不难发现左子节点被拼起来的那一段肯定包含左子节点的右端点，反之，右子节点被拼起来的那一段则一定包含右子节点的左端点。
所以我们可以对于每一个节点维护它的最大子段和，左连续和（以左子节点右端点为起点向左找的最大连续和）与右连续和（以右子节点左端点为起点想左找的最大连续和）。（同时，为了维护左连续和与右连续和，我们还需要维护当前节点区间和）
发现对单点修改区间查询的操作不是特别熟悉，所以重新去做一下线段树2
https://www.luogu.com.cn/problem/P3373
哦，再提一下吧：线段树2并不只是单点查询区间修改
它还有两个标记：乘法标记和加法标记（要记得先乘再加喵），而且在打tag的时候，如果打的是乘法标记，要记得把加法标记给乘一下。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int a[N];
int w[N*4],lzy1[N*4],lzy2[N*4];//lzy1:乘法，lzy2:加法
int n,q,mod;
void build(int u,int l,int r){
if(l==r){
w[u]=a[l];
return;
}
int mid=(l+r)>>1;
build(u*2,l,mid),build(u*2+1,mid+1,r);
w[u]=(w[u*2]+w[u*2+1])%mod;
}
void get_lzy(int u,int l,int r,int val1,int val2){
//val1:乘法懒标记，val2:加法懒标记
w[u]=((w[u]*val1)%mod+((r-l+1)*val2)%mod)%mod;
lzy1[u]=(lzy1[u]*val1)%mod;
lzy2[u]=((lzy2[u]*val1)%mod+val2);
}
void pushdown(int u,int l,int r,int mid){
get_lzy(u*2,l,mid,lzy1[u],lzy2[u]);
get_lzy(u*2+1,mid+1,r,lzy1[u],lzy2[u]);
lzy1[u]=1,lzy2[u]=0;
}
void xds_c(int u,int l,int r,int L,int R,int val){
if(r<L||R<l)return;
if(L<=l&&r<=R){
get_lzy(u,l,r,val,0);
return;
}
int mid=(l+r)>>1;
pushdown(u,l,r,mid);
xds_c(u*2,l,mid,L,R,val),xds_c(u*2+1,mid+1,r,L,R,val);
w[u]=(w[u*2]+w[u*2+1])%mod;
}
void xds_p(int u,int l,int r,int L,int R,int val){
if(r<L||R<l)return;
if(L<=l&&r<=R){
get_lzy(u,l,r,1,val);
return;
}
int mid=(l+r)>>1;
pushdown(u,l,r,mid);
xds_p(u*2,l,mid,L,R,val),xds_p(u*2+1,mid+1,r,L,R,val);
w[u]=(w[u*2]+w[u*2+1])%mod;
}
int ask(int u,int l,int r,int L,int R){
if(r<L||R<l)return 0;
if(L<=l&&r<=R)return w[u];
int mid=(l+r)>>1;
pushdown(u,l,r,mid);
return (ask(u*2,l,mid,L,R)+ask(u*2+1,mid+1,r,L,R))%mod;
}
signed main(){
cin>>n>>q>>mod;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n*4;i++)lzy1[i]=1;
build(1,1,n);
for(int i=1;i<=q;i++){
int zz;
cin>>zz;
if(zz==1){
int x,y,k;
cin>>x>>y>>k;
xds_c(1,1,n,x,y,k);
}else if(zz==2){
int x,y,k;
cin>>x>>y>>k;
xds_p(1,1,n,x,y,k);
}else if(zz==3){
int x,y;
cin>>x>>y;
cout<<ask(1,1,n,x,y)<<'\n';
}
}
return 0;
}
唔。其实我一直觉得#define int long long很危险，但是有时又不得不承认它是好用的。
好了，重新回去做小白逛公园。
等一下，突然发现我不会的好像是单点修改单点查询。
?
算了直接写吧。
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int a[N];
struct Node{
int sum,zd,lv,rv;//区间和，最大子段和
//必须包含当前区间左端点的最大子段和
//必须包含当前区间右端点的最大子段和
}node[N*4];
void pushup(int u){
node[u].sum=node[u*2].sum+node[u*2+1].sum;
int x=node[u*2].rv+node[u*2+1].lv;
node[u].zd=max(node[u*2].zd,max(node[u*2+1].zd,x));
node[u].lv=max(node[u*2].lv,node[u*2].sum+node[u*2+1].lv);
node[u].rv=max(node[u*2+1].rv,node[u*2+1].sum+node[u*2].rv);
}
void build(int u,int l,int r){
if(l==r){
node[u]={a[l],a[l],a[l],a[l]};
return;
}
int mid=(l+r)>>1;
build(u*2,l,mid),build(u*2+1,mid+1,r);
pushup(u);
}
Node mer(Node a,Node b){
Node fan={INT_MIN,INT_MIN,INT_MIN,INT_MIN};
fan.sum=a.sum+b.sum;
int x=a.rv+b.lv;
fan.zd=max(a.zd,max(b.zd,x));
fan.lv=max(a.lv,a.sum+b.lv);
fan.rv=max(b.rv,b.sum+a.rv);
return fan;
}
Node ask(int u,int l,int r,int L,int R){
if(L<=l&&r<=R)return node[u];
int mid=(l+r)>>1;
if(R<=mid)return ask(u*2,l,mid,L,R);
if(L>mid)return ask(u*2+1,mid+1,r,L,R);
return mer(ask(u*2,l,mid,L,R),ask(u*2+1,mid+1,r,L,R));
}
void xds(int u,int l,int r,int mb,int val){
//mb:目标要修改的节点，val:要修改的值
if(l==r&&r==mb){
node[u]={val,val,val,val};
return;
}
int mid=(l+r)>>1;
//左区间：l-mid 右区间：mid+1-r
if(mb<=mid)xds(u*2,l,mid,mb,val);
else xds(u*2+1,mid+1,r,mb,val);
pushup(u);
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
build(1,1,n);
for(int i=1;i<=m;i++){
int k;
cin>>k;
if(k==1){
int a,b;
cin>>a>>b;
if(a>b)swap(a,b);
Node sum=ask(1,1,n,a,b);
cout<<sum.zd<<'\n';
}else{
int p,s;//第p个公园的打分变成了s
cin>>p>>s;
xds(1,1,n,p,s);
}
}
return 0;
}
写代码的时候一直想出去买东西吃，导致产生了一大堆错误，一点点梳理一下.
1.在写合并函数(mer)的时候，我是照着上面的pushup抄的，结果抄错了。
错误代码1:
错误代码2：
正确代码：
也就是说，不是要把两个最大子段和拼起来。（因为最大子段和不一定是连续的）
2.最开始的时候，我不太清楚应该怎么写ask函数。所以我是这样写的：
实际上，这应该是一个求哪个子节点所包含的值更大的倒霉催函数。
事实上，我们应该让ask也返回node，然后按照写pushup的方法全部完成返回值的编写。
接着来写一道简单题。
我记得我应该在我线段树那里写过的，结果当时写炸了。
唔。感觉挺简单。一眼板。
不过有点神秘的是，我第一次写的TLE大爆炸了：
因为我在pushup那边犹豫了一下怎么拼接01数组，而后用了string，超时。
所以要记得不要乱使用string，有可能会超时。
后面转念一想，其实我们根本不用维护包含节点数大于等于二的节点（也就是说可以直接把pushup去掉，所以就新弄了一份代码）
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int w[N*4];
int lzy[N*4];
void build(int u,int l,int r){
if(l==r){
w[u]=0;
return;
}
int mid=(l+r)>>1;
build(u*2,l,mid),build(u*2+1,mid+1,r);
}
void get(int u){
if(lzy[u]==1)lzy[u]=0;
else lzy[u]=1;
if(w[u]==1)w[u]=0;
else w[u]=1;
}
void pushdown(int u,int l,int r,int mid){
if(lzy[u]==0)return;
get(u*2),get(u*2+1);
lzy[u]=0;
}
void xds(int u,int l,int r,int L,int R){
if(r<L||R<l)return;
if(L<=l&&r<=R){
get(u);
return;
}
int mid=(l+r)>>1;
pushdown(u,l,r,mid);
xds(u*2,l,mid,L,R),xds(u*2+1,mid+1,r,L,R);
}
int ask(int u,int l,int r,int whi){
if(l==r)return w[u];
int mid=(l+r)>>1;
pushdown(u,l,r,mid);
if(whi<=mid)return ask(u*2,l,mid,whi);
else return ask(u*2+1,mid+1,r,whi);
}
int main(){
int n,m;
cin>>n>>m;
build(1,1,n);
for(int i=1;i<=m;i++){
int t;
cin>>t;
if(t==1){
//两个数l,r（反转区间）
int l,r;
cin>>l>>r;
xds(1,1,n,l,r);
}else{
int x;//询问下标
cin>>x;
cout<<ask(1,1,n,x)<<'\n';
}
}
return 0;
}
最后一个线段树题目！
权值线段树。
对一个数列a构造一个数列b，其中b[i]表示a中数值i出现过的次数，这样的数列b称为a的权值数列。对b构造的线段树称为数列a的权值线段树。
权值线段树在很多计数问题中有着重要的应用，因为它可以轻松地修改对a维护的统计信息。容易发现，当将a[i]从x修改为y时，只需要对其权值线段树做两次单点修改，即给b[x]间1，给b[y]加上1.
（由于大部分的a会很大，所以需要使用离散化）
除了一堆问题，我先放下代码，然后逐一分析问题所在：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+5;
ll a[N*4],l[N*4],b[N*4],w[N*4];//
void pushup(int u){
w[u]=w[u*2]+w[u*2+1];
return;
}
ll ask(int u,int l,int r,int L,int R){
//?
if(r<L||R<l)return 0;
if(L<=l&&r<=R)return w[u];
int mid=(l+r)>>1;
return ask(u*2,l,mid,L,R)+ask(u*2+1,mid+1,r,L,R);
}
void add(int u,int l,int r,int mb){
if(l==r){
w[u]++;//
return;
}
int mid=(l+r)>>1;
if(mb<=mid)add(u*2,l,mid,mb);
else add(u*2+1,mid+1,r,mb);
pushup(u);
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i],l[i]=a[i];
sort(l+1,l+1+n);
int ed=std::unique(l+1,l+1+n)-l-1;
ll ans=0;//
for(int i=1;i<=n;i++){
int sum=lower_bound(l+1,l+1+ed,a[i])-l;//
ans+=ask(1,1,ed,sum+1,n);
add(1,1,ed,sum);
}
cout<<ans;
return 0;
}
1.还是会忘记要把N*4
前面很好奇为什么一共只有线段树一共只有n * 2个节点，但是要开N *4的空间，这是因为：
2.懒标记的作用
懒标记存在的意义是区间修改时暂时不去修改下面的子节点，只是放置一个标记，等到查询或者再次打表记时再下放。
但是注意：这是只争对区间的，如果你只是想要修改单点，是不需要懒标记的
3.逆序对开long long
其实我经常会漏掉哪里要开long long，遂偷懒写define int long long
但是这样是不对的（define int long long 是有很大概率出错的）
所以如果你要用long long answer，你需要记得把返沪结果的ask函数也开成long long
4.我发现当我用离散化，我还是会搞混数组。所以可以多做一点离散化的题目。
树状数组
注意到现在已经15:38。
注意到我完全忘记了树状数组。
我去。
那就重新做一下树状数组的模板好了，然后再弄一道别的什么玩耍一下。
树状数组是线段树的平替，经典的操作只有两个：1.单点修改 2.区间查询
其精髓在于，它不会直接去存储原数组，而是用一个辅助数组去存储一小段区间和（这一小段的区间和取决于的二进制的最后一个一在哪个位置，即lowbit函数）
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int a[N],w[N],n,m;
int lowbit(int x){
return (x)&(-x);
}
void add(int x,int k){
for(int i=x;i<=n;i+=lowbit(i))w[i]+=k;
}
int q(int x){
int sum=0;
for(int i=x;i>=1;i-=lowbit(i))sum+=w[i];
return sum;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
add(i,a[i]);
}
for(int i=1;i<=m;i++){
int zz;
cin>>zz;
if(zz==1){
int x,k;
cin>>x>>k;//将第x个数加上k
add(x,k);
}else{
int x,y;//求[x,y]内每个数的和
cin>>x>>y;
cout<<q(y)-q(x-1)<<'\n';
}
}
return 0;
}
(碎碎念：树状数组真的比线段树好写很多)
https://www.luogu.com.cn/problem/P5677
配对统计
感觉有点太难了，换一道简单点的题吧，我们要循序渐进！
https://www.luogu.com.cn/problem/P5459
回转寿司
唔。这道题目的大概意思是：寻找一个序列中>=l且<=r的连续子段和的数目
注意到，树状数组的单次查询时间复杂度是
想十五分钟。欧克来讲怎么做。
我一开始先摸了这样一份代码：
但它其实是错的（因为有负数的存在）
然后我去看了树状数组题解。
正解是这样的：
先预处理前缀和，对于每一个区间的右端点pos，找出有多少个是且大于等于L的，由于pre有可能很大，所以使用离散化。
感觉是个比较基础的做法，但是没想出来。待会儿要不再连一道树状数组？
不过在这之前先玩耍一下代码。
所以，从理论上而言，这是不是算权值树状数组？
果然，女儿像妈妈。
突然发现自己应该补一下二分答案。
等一下，我前面好像写错了，理论上而言，应该是对于每个右端点pos，找出[pre[pos]-r,pre[pos]-l]这个区间内的数字有多少个，推理过程如下：
有点坏菜。感觉状态好差。可不能这样啊。六点钟之前一定得把这题做完了，不然效率太低了。
没做完。七点了。我去。
我重新把这道题目的思路梳理一遍：
题目大意：给定一个数组，统计有多少个连续子段，使得子段和在[l,r]区间之内。
第一步：把子段和转化成前缀和的差（子段和是一个区间的累加值，需要时间复杂度处理。而前缀和只需要时间复杂度就能处理出来，这是一个常见的思路转变）
第二步：固定右端点，统计合法的左端点（上面放过deepseek的截图，我们用数学处理的方法将其简化成了：查找有多少个值落在了[pre[r]-R,pre[r]-L]）
其实我们想要统计的是：L<=pre[r]-pre[x-1]<=R
这个时候引入关键的一点：从上面的分析中，我们可以看出，我们需要在树状数组中加入这些值：1.pre[1]-pre[n]
2.pre[i]-L pre[i]-R
3.pre[0]（由于是pre[x-1]，x从1开始，所以x-1=0，得放进去）
感觉还是不够懂，我先放置一下代码，过几天再来看一遍：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int a[N*3],pre[N*3],prel[N*3];//
int w[N],n,L,R,ed;
int lowbit(int x){
return x&(-x);
}
void add(int x){
for(int i=x;i<=ed;i+=lowbit(i))w[i]+=1;//
}
int q(int x){
int sum=0;
for(int i=x;i>=1;i-=lowbit(i))sum+=w[i];
return sum;
}
int ans;
signed main(){
cin>>n>>L>>R;
for(int i=1;i<=n;i++)cin>>a[i],prel[i]=pre[i]=pre[i-1]+a[i];
int cnt=n;
for(int i=1;i<=n;i++){
prel[++cnt]=prel[i]-L,prel[++cnt]=prel[i]-R;
}
prel[++cnt]=0;
sort(prel+1,prel+1+cnt);
ed=std::unique(prel+1,prel+1+cnt)-prel-1;
for(int r=0;r<=n;r++){
int sum=lower_bound(prel+1,prel+1+ed,pre[r])-prel;
int sum1=lower_bound(prel+1,prel+1+ed,pre[r]-R)-prel;
int sum2=lower_bound(prel+1,prel+1+ed,pre[r]-L)-prel;
ans+=(q(sum2)-q(sum1-1));
add(sum);//
}
cout<<ans;
return 0;
}
贪心
https://www.luogu.com.cn/problem/P1803
线段覆盖
这是一个相当基础的贪心，我应该做过挺多次了（虽然不知道为什么这个号没有A）
把代码放一下，然后重新讲一讲吧。
算了。这里内容太多，打字已经开始卡顿，我就不把内容放在这里了。
这里空空如也
有帮助，赞一个