先写两道水题，增强自信（可以用线段树做，但是我不会啊 ）
洛谷 P1047 校门外的树
#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int n,m,x,y,ans,a[N];
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;//线段长n+1，总共有m次操作
while(m--)
{
cin>>x>>y;//操作区间[x,y]
for(int i=x;i<=y;i++)
a[i]=1;//被砍标记
}
for(int i=0;i<=n;i++)
{if(a[i]==0)ans++;}
printf("%d\n",ans);
return 0;
}
洛谷 P1276 校门外的树（增强版）
没必要写线段树，直接模拟，线段长度n+1，操作次数m，时间复杂度O(nm)，n*m大约1e6数量级，稳过。
开一个status数组记录线段上每个点的状态，最后再遍历一遍即可。
#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int n,m,x,y,opt,ans1,ans2,status[N];
/*status数组表示线段上的每个点i有4个状态 status[i]=0表示最初始的完整的树 status[i]=1表示从完整的树被砍成无树苗 status[i]=2表示只有树苗 status[i]=3表示种上树苗之后又被砍成无树苗*/
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;//线段长为n+1(0~n)，总共有m次操作
while(m--)
{
cin>>opt>>x>>y;//操作区间[x,y]
if(opt==0)
{
for(int i=x;i<=y;i++)
{
if(status[i]==0)
status[i]=1;
else if(status[i]==2)
{
status[i]=3;
ans2++;
}
}
}
else
{
for(int i=x;i<=y;i++)
{
if(status[i]==1)
status[i]=2;
else if(status[i]==3)
status[i]=2;
}
}
}
for(int i=0;i<=n;i++)
{
if(status[i]==2)
ans1++;
}
printf("%d\n%d\n",ans1,ans2);
return 0;
}
———————————OK，水题结束，开始写线段树模板———————————
hdu 1754 I Hate It
单点修改，询问区间最大值。具体思路详见代码注释。
#include <bits/stdc++.h>
using namespace std;
const int N=200010;
string opt;
int n,m,x,y,a[N],tr[4*N];//tr[i]表示第i个区间内的最大值
void pushup(int i)//更新tr[i]为其两个子区间的最大值
{tr[i]=max(tr[2*i],tr[2*i+1]);}
void build(int i,int l,int r)//i是区间[l,r]对应的编号
{
if(l==r)//区间[l,r]左右端点重合，此时这个区间内的最大值就是原数组的值
{
tr[i]=a[l];
return;
}
int mid=l+r>>1;//mid=(l+r)/2;
build(2*i,l,mid);//左子区间
build(2*i+1,mid+1,r);//右子区间
pushup(i);//向上返回时更新tr[i]为其两个子区间的最大值
}
void update(int i,int l,int r,int x,int y)//第i个区间，[l,r]为当前区间，把原数组中下标为x的值改为y
{
if(x>r||x<l)return;//x在当前区间[l,r]外，直接返回
if(l==r&&l==x)//当前区间为[x,x]，说明找到x了，把这个区间内的最大值改为y
{
tr[i]=y;
return;
}
int mid=l+r>>1;
update(2*i,l,mid,x,y);
update(2*i+1,mid+1,r,x,y);
pushup(i);//向上返回时更新tr[i]为其两个子区间的最大值
}
int query(int i,int l,int r,int x,int y)//[l,r]为当前区间(在递归过程中不断被二分)，[x,y]为要询问的区间(在递归过程中不变)
{
if(l>y||r<x)return 0;//询问区间[l,r]与原数组区间[x,y]没有交集，返回0(返回负数也可以，因为这样能保证返回值小于其他所有可能的最大值)
if(l>=x&&r<=y)return tr[i];//当前区间为询问区间的子区间时，返回区间内维护的最大值
int mid=l+r>>1;
return max(query(2*i,l,mid,x,y),query(2*i+1,mid+1,r,x,y));//返回左子区间和右子区间的最大值
}
int main()
{
ios::sync_with_stdio(false);
while(cin>>n>>m)
{
for(int i=1;i<=n;i++)
cin>>a[i];
build(1,1,n);//从编号为1的[1,n]节点开始向下递归建立线段树
while(m--)
{
cin>>opt>>x>>y;
if(opt=="U")update(1,1,n,x,y);//把原数组中下标为x的值改为y，从第1个区间[1,n]开始向下递归，到最底层子节点后再向上返回修改
else printf("%d\n",query(1,1,n,x,y));//询问[x,y]区间内的最大值，从第1个区间[1,n]开始向下递归查找
}
}
return 0;
}
hdu 1166 敌兵布阵
单点修改，询问区间和。只需把上题代码的模板稍作修改即可。
#include <bits/stdc++.h>
using namespace std;
const int N=50010;
string opt;
int n,t,x,y,a[N],tr[4*N];
void pushup(int i)
{tr[i]=tr[2*i]+tr[2*i+1];}
void build(int i,int l,int r)
{
if(l==r)
{
tr[i]=a[l];
return;
}
int mid=l+r>>1;
build(2*i,l,mid);
build(2*i+1,mid+1,r);
pushup(i);
}
void update(int i,int l,int r,int x,int y)
{
if(x>r||x<l)return;
if(l==r&&l==x)
{
tr[i]=tr[i]+y;//这里必须写tr[i]=tr[i]+y，不能写tr[i]=a[l]+y！
return;
}
int mid=l+r>>1;
update(2*i,l,mid,x,y);
update(2*i+1,mid+1,r,x,y);
pushup(i);
}
int query(int i,int l,int r,int x,int y)
{
if(l>y||r<x)return 0;//询问区间[l,r]与原数组区间[x,y]没有交集，返回的和为0
if(l>=x&&r<=y)return tr[i];
int mid=l+r>>1;
return query(2*i,l,mid,x,y)+query(2*i+1,mid+1,r,x,y);//返回左右子区间之和
}
int main()
{
ios::sync_with_stdio(false);
cin>>t;
for(int cas=1;cas<=t;cas++)
{
printf("Case %d:\n",cas);
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
build(1,1,n);
while(cin>>opt&&opt!="End")
{
cin>>x>>y;
if(opt=="Add")update(1,1,n,x,y);
else if(opt=="Sub")update(1,1,n,x,-y);
else printf("%d\n",query(1,1,n,x,y));
}
}
return 0;
}
poj 3468 A Simple Problem with Integers（洛谷 P3372 线段树1）
区间修改(区间内每个数加k)，区间询问和。
洛谷 P3372 线段树1 AC代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll n,m,x,y,k,opt,a[N],add[4*N],sum[4*N];//add[i]表示第i个区间内每个数要加的值，也就是懒标记(延迟标记)
void build(ll i,ll l,ll r)//建树
{
if(l==r)
{
sum[i]=a[l];
return;
}
ll mid=l+r>>1;
build(2*i,l,mid);
build(2*i+1,mid+1,r);
sum[i]=sum[2*i]+sum[2*i+1];
}
void Add(ll i,ll l,ll r,ll k)//[l,r]区间内每个数加k
{
add[i]=add[i]+k;//add[i]表示第i个区间内每个数要加的值
sum[i]=sum[i]+(r-l+1)*k;
}
void pushdown(ll i,ll l,ll r,ll mid)//下传标记到左右子区间
{
if(add[i]==0)return;//没有标记，直接返回
Add(2*i,l,mid,add[i]);
Add(2*i+1,mid+1,r,add[i]);
add[i]=0;//清除标记
}
void update(ll i,ll l,ll r,ll x,ll y,ll k)//更新[x,y]区间，将[x,y]区间内每个数加k
{
if(l>y||r<x)return;
if(l>=x&&r<=y)return Add(i,l,r,k);
ll mid=l+r>>1;
pushdown(i,l,r,mid);//下传标记后更新左右子区间
update(2*i,l,mid,x,y,k);//更新左子区间
update(2*i+1,mid+1,r,x,y,k);//更新右子区间
sum[i]=sum[2*i]+sum[2*i+1];
}
ll query(ll i,ll l,ll r,ll x,ll y)//查询[x,y]区间和
{
if(l>y||r<x)return 0;
if(l>=x&&r<=y)return sum[i];
ll mid=l+r>>1;
pushdown(i,l,r,mid);//下传标记后查询左右子区间
return query(2*i,l,mid,x,y)+query(2*i+1,mid+1,r,x,y);//查询左右子区间之和
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(ll i=1;i<=n;i++)
cin>>a[i];
build(1,1,n);
while(m--)
{
cin>>opt;
if(opt==1)
{
cin>>x>>y>>k;
update(1,1,n,x,y,k);
}
else
{
cin>>x>>y;
printf("%lld\n",query(1,1,n,x,y));
}
}
return 0;
}
先做的洛谷P3372，完美AC，然后交到poj，竟然给我个TLE，后来发现竟然ios::sync_with_stdio(false)提速cin后也会超时，改成scanf就过了…其实我一直觉得ios::sync_with_stdio(false)提速cin后会比scanf快，没想到只是某些情况下快，其他情况可能慢得超时？不知道是不是poj的锅，下次遇到TLE，如果不是算法的问题，要不改成scanf，要不改成快读吧，这种卡常数的TLE还是要尽量避免。
poj 3468 A Simple Problem with Integers AC代码：
#include <cstdio>
using namespace std;
typedef long long ll;
const int N=1e5+10;
char opt;
ll n,m,x,y,k,a[N],add[4*N],sum[4*N];
void build(ll i,ll l,ll r)
{
if(l==r)
{
sum[i]=a[l];
return;
}
ll mid=l+r>>1;
build(2*i,l,mid);
build(2*i+1,mid+1,r);
sum[i]=sum[2*i]+sum[2*i+1];
}
void Add(ll i,ll l,ll r,ll k)
{
add[i]=add[i]+k;
sum[i]=sum[i]+(r-l+1)*k;
}
void pushdown(ll i,ll l,ll r,ll mid)
{
if(add[i]==0)return;
Add(2*i,l,mid,add[i]);
Add(2*i+1,mid+1,r,add[i]);
add[i]=0;
}
void update(ll i,ll l,ll r,ll x,ll y,ll k)
{
if(l>y||r<x)return;
if(l>=x&&r<=y)return Add(i,l,r,k);
ll mid=l+r>>1;
pushdown(i,l,r,mid);
update(2*i,l,mid,x,y,k);
update(2*i+1,mid+1,r,x,y,k);
sum[i]=sum[2*i]+sum[2*i+1];
}
ll query(ll i,ll l,ll r,ll x,ll y)
{
if(l>y||r<x)return 0;
if(l>=x&&r<=y)return sum[i];
ll mid=l+r>>1;
pushdown(i,l,r,mid);
return query(2*i,l,mid,x,y)+query(2*i+1,mid+1,r,x,y);
}
int main()
{
scanf("%lld%lld",&n,&m);
for(ll i=1;i<=n;i++)
scanf("%lld",&a[i]);
build(1,1,n);
while(m--)
{
scanf(" %c",&opt);
if(opt=='C')
{
scanf("%lld%lld%lld",&x,&y,&k);
update(1,1,n,x,y,k);
}
else
{
scanf("%lld%lld",&x,&y);
printf("%lld\n",query(1,1,n,x,y));
}
}
return 0;
}
洛谷 P3373 线段树2
区间修改(区间内每个数乘k)，区间询问和。
注意下传标记函数写法，要先算乘法再算加法，并且对区间乘k时，不仅要把mul标记和sum值乘k，还要把add标记乘k。
懒标记下放（pushdown）原理解释：
1.当对某区间执行加法操作时，由于加法优先级低，不会对乘法操作产生影响，故直接相加即可；
2.当对某区间执行乘法操作时，由于乘法优先级高，会对之前的加法操作产生影响，故需要在相乘时不仅对sum和mul相乘，也需要对add相乘；
3.由于上述原因，故需要先算乘法再算加法。
（以上转自洛谷大佬博客）
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll n,m,p,x,y,k,opt,a[N],add[4*N],mul[4*N],sum[4*N];
void build(ll i,ll l,ll r)
{
mul[i]=1;//乘法标记初始化为1
if(l==r)
{
sum[i]=a[l];
return;
}
ll mid=l+r>>1;
build(2*i,l,mid);
build(2*i+1,mid+1,r);
sum[i]=(sum[2*i]+sum[2*i+1])%p;
}
void Add(ll i,ll l,ll r,ll k)//[l,r]区间内每个数加k
{
add[i]=(add[i]+k)%p;
sum[i]=(sum[i]+(r-l+1)*k)%p;
}
void Mul(ll i,ll l,ll r,ll k)//[l,r]区间内每个数乘k
{
add[i]=add[i]*k%p;//注意add标记也要乘k，这行代码很重要
mul[i]=mul[i]*k%p;
sum[i]=sum[i]*k%p;
}
void pushdown(ll i,ll l,ll r,ll mid)//下传标记到左右子区间
{
if(mul[i]==1&&add[i]==0)return;//加法标记和乘法标记都没有，直接返回
Mul(2*i,l,mid,mul[i]);Mul(2*i+1,mid+1,r,mul[i]);//先乘
Add(2*i,l,mid,add[i]);Add(2*i+1,mid+1,r,add[i]);//后加(不能先加后乘，顺序不能颠倒)
mul[i]=1;add[i]=0;//清除标记
}
void update_add(ll i,ll l,ll r,ll x,ll y,ll k)//更新[x,y]区间，将[x,y]区间内每个数加k
{
if(l>y||r<x)return;
if(l>=x&&r<=y)return Add(i,l,r,k);
ll mid=l+r>>1;
pushdown(i,l,r,mid);//下传标记后更新左右子区间
update_add(2*i,l,mid,x,y,k);//更新左子区间
update_add(2*i+1,mid+1,r,x,y,k);//更新右子区间
sum[i]=(sum[2*i]+sum[2*i+1])%p;
}
void update_mul(ll i,ll l,ll r,ll x,ll y,ll k)//更新[x,y]区间，将[x,y]区间内每个数乘k
{
if(l>y||r<x)return;
if(l>=x&&r<=y)return Mul(i,l,r,k);
ll mid=l+r>>1;
pushdown(i,l,r,mid);//下传标记后更新左右子区间
update_mul(2*i,l,mid,x,y,k);//更新左子区间
update_mul(2*i+1,mid+1,r,x,y,k);//更新右子区间
sum[i]=(sum[2*i]+sum[2*i+1])%p;
}
ll query(ll i,ll l,ll r,ll x,ll y)//查询[x,y]区间和
{
if(l>y||r<x)return 0;
if(l>=x&&r<=y)return sum[i];
ll mid=l+r>>1;
pushdown(i,l,r,mid);//下传标记后查询左右子区间
return (query(2*i,l,mid,x,y)+query(2*i+1,mid+1,r,x,y))%p;//查询左右子区间之和
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m>>p;
for(int i=1;i<=n;i++)
cin>>a[i];
build(1,1,n);
while(m--)
{
cin>>opt;
if(opt==1)
{
cin>>x>>y>>k;
update_mul(1,1,n,x,y,k);
}
else if(opt==2)
{
cin>>x>>y>>k;
update_add(1,1,n,x,y,k);
}
else
{
cin>>x>>y;
printf("%lld\n",query(1,1,n,x,y));
}
}
return 0;
}
洛谷 P1438 无聊的数列
求原数组的差分数组(不知道“差分”的)，线段树维护差分数组dif[i]。需要知道的是，差分与前缀和互为逆运算，也就是说，原数组a[i]等于其差分数组的前缀和sum[i]。
1、修改区间[l,r]，给出一个长度等于R-L+1的等差数列，首项为K，公差为D，并将它对应加到a[L]~a[R]的每一个数上。把原数组该区间内的数依次对应加一个等差数列，相当于对差分数组进行如下操作：
dif[l]=dif[l]+k，dif[r+1]=dif[r+1]-(k+(r-l)*d)，dif[i]=dif[i]+d(当i∈[l+1,r]时)
2、单点询问原数组a[r]相当于求[1,r]区间内差分数组的前缀和。
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,l,r,k,d,opt,a[N],dif[N],add[4*N],sum[4*N];//原数组a[i]的差分数组为dif[i]，对dif求前缀和记为sum，sum[i]就是a[i]
void build(int i,int l,int r)
{
if(l==r)
{
sum[i]=dif[l];
return;
}
int mid=l+r>>1;
build(2*i,l,mid);
build(2*i+1,mid+1,r);
sum[i]=sum[2*i]+sum[2*i+1];
}
void Add(int i,int l,int r,int k)//dif数组在[l,r]区间内每个数要加的值为k
{
add[i]=add[i]+k;//add标记在区间[l,r]中每个数要加的值
sum[i]=sum[i]+(r-l+1)*k;
}
void pushdown(int i,int l,int r,int mid)
{
if(add[i]==0)return;
Add(2*i,l,mid,add[i]);
Add(2*i+1,mid+1,r,add[i]);
add[i]=0;
}
void update(int i,int l,int r,int x,int y,int k)//dif数组在[l,r]区间内每个数要加的值为k
{
if(l>y||r<x)return;
if(l>=x&&r<=y)return Add(i,l,r,k);
int mid=l+r>>1;
pushdown(i,l,r,mid);
update(2*i,l,mid,x,y,k);
update(2*i+1,mid+1,r,x,y,k);
sum[i]=sum[2*i]+sum[2*i+1];
}
int query(int i,int l,int r,int x,int y)
{
if(l>y||r<x)return 0;
if(l>=x&&r<=y)return sum[i];
int mid=l+r>>1;
pushdown(i,l,r,mid);
return query(2*i,l,mid,x,y)+query(2*i+1,mid+1,r,x,y);
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)//求原数组a[i]差分数组dif[i]
dif[i]=a[i]-a[i-1];
build(1,1,n);
while(m--)
{
cin>>opt;
if(opt==1)
{
cin>>l>>r>>k>>d;
update(1,1,n,l,l,k);//dif[l]=dif[l]+k
if(r+1<=n)update(1,1,n,r+1,r+1,-(k+(r-l)*d));//dif[r+1]=dif[r+1]-(k+(r-l)*d)
if(l+1<=r)update(1,1,n,l+1,r,d);//当i∈[l+1,r]时，dif[i]=dif[i]+d
}
else
{
cin>>r;
printf("%d\n",query(1,1,n,1,r));//求[1,r]区间内差分数组的前缀和sum[r]，也就是求原数组a[r]
}
}
return 0;
}
洛谷 P1020 导弹拦截
关于第二问为什么是求最长上升子序列的长度，给出以下证明（转自洛谷大佬们的题解）
第二问需要一个转换的思想了
我们可以把问题中需要几组导弹转化成求一个最长上升子序列
证明： 1、首先我们把这些导弹分为s组（s即为所求答案）
可以看出每一组都是一个不升子序列
2、划分完后我们在组一里找一个原序列里以组一的开头点连续的不升子串的最后一个元素，可以知道在组2中一定有一个大与它的点
（如果组二中没有的话，那么组二中最高的导弹高度必然小于这个点，而其他的高度都小于这个高度而且是递减或相等的，那么没有必要再开一个组二了，矛盾，所以不存在找不到比他大的点的情况）
3、以此类推，对于每一个k组（1<=k<n）都可以找到这样的一些点
所以把这些点连起来，就是一条上升子序列。
4、设最长上升子序列长度为l
所求上升子序列为h
那么h<=l
因为最长上升子序列任意两个不在一组内
(如果在同一个组内，则每个组的数不成为一个不生子序列，矛盾）
所以l==h
我给一个严密的数学证明【证明部分引自CSDN】
这里我们要介绍一个很优美的定理。
Dilworth定理：对于一个偏序集，最少链划分等于最长反链长度。
Dilworth定理的对偶定理：对于一个偏序集，其最少反链划分数等于其最长链的长度。
也就是说把一个数列划分成最少的不升子序列的数目就等于这个数列的最长上升子序列的长度。
下面来说说这个定理是怎么来的：
偏序集的定义：偏序是在集合X上的二元关系≤（这只是个抽象符号，不是“小于或等于”，它满足自反性、反对称性和传递性）。即，对于X中的任意元素a,b和c，有:
(1)自反性：a≤a;
(2)反对称性：如果a≤b且b≤a，则有a=b;
(3)传递性：如果a≤b且b≤c，则a≤c 。
带有偏序关系的集合称为偏序集。
令(X,≤)是一个偏序集，对于集合中的两个元素a、b，如果有a≤b或者b≤a，则称a和b是可比的，否则a和b不可比。
在这个例子(反链)中元素Ri<=Rj是指(i<=j) and (ai>=aj)
一个反链A是X的一个子集，它的任意两个元素都不能进行比较。
一个链C是X的一个子集，它的任意两个元素都可比。
【定理】
在X中，对于元素a，如果任意元素b，都有a≤b，则称a为极小元。
定理1：令（X,≤）是一个有限偏序集，并令r是其最大链的大小。则X可以被划分成r个但不能再少的反链。
其对偶定理称为Dilworth定理：
令（X,≤）是一个有限偏序集，并令m是反链的最大的大小。则X可以被划分成m个但不能再少的链。
虽然这两个定理内容相似，但第一个定理证明要简单一些。此处就只证明定理1。
证明：设p为最少反链个数
(1)先证明X不能划分成小于r个反链。由于r是最大链C的大小，C中任两个元素都可比，因此C中任两个元素都不能属于同一反链。所以p>=r。
(2)设X1＝X，A1是X1中的极小元的集合。从X1中删除A1得到X2。注意到对于X2中任意元素a2，必存在X1中的元素a1，使得a1<=a2。令A2是X2中极小元的集合，从X2中删除A2得到X3……，最终会有一个Xk非空而Xk+1为空。于是A1,A2,…,Ak就是X的反链的划分，同时存在链a1<=a2<=…<=ak，其中ai在Ai内。由于r是最长链大小，因此r>=k。由于X被划分成了k个反链，因此r>=k>=p。
(3)因此r=p，定理1得证。
【解决】
要求最少的覆盖，按照Dilworth定理
最少链划分 = 最长反链长度
所以最少系统 = 最长导弹高度上升序列长度。
求最长不上升子序列和最长上升子序列，二分+贪心，优化到O(n*logn)。线段树优化我不会，待我好好研究一下
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,k,len1,len2,a[N],lis1[N],lis2[N];
int main()
{
ios::sync_with_stdio(false);
while(cin>>a[++n]);n--;
lis1[++len1]=a[1];
for(int i=2;i<=n;i++)
{
if(a[i]<=lis1[len1])lis1[++len1]=a[i];
else
{//必须是upper_bound！
k=upper_bound(lis1+1,lis1+len1+1,a[i],greater<int>())-lis1;//减去lis1而不是lis1+1
lis1[k]=a[i];
}
}
lis2[++len2]=a[1];
for(int i=2;i<=n;i++)
{
if(a[i]>lis2[len2])lis2[++len2]=a[i];
else
{
k=lower_bound(lis2+1,lis2+len2+1,a[i])-lis2;//必须是lower_bound，不是upper_bound！
lis2[k]=a[i];
}
}
printf("%d\n%d\n",len1,len2);
return 0;
}
京公网安备 11010502036488号