线段树练习
发布时间 2024-01-13 18:53:46作者: Liuyc07
# Ⅰ.差分与前缀和
## P2184 贪婪大陆
**题意** ：给定防线长度 $n$ 和操作次数 $m$, 每次在 [$l$ ,$r$] 内布下一种雷，查询区间雷的种类数。
**分析** ： 用线段的方式表示区间布的雷 :
如[ 2 , 4 ]内的种类 = [ 1 , 4 ]内的起点 - [ 1 , 2 ]内的终点
## P1438 无聊的数列
**题意** ： 区间加等差数列，区间查询。
**分析** ： 将原序列差分，即可转化为区间加。
**Summary**：在[ $l$ ,$r$ ] 内加上一个首项为 $k$ ，公差为 $D$ 的等差数列，等价于在差分数组上的 $l$ 加 $k$ , 然后在在 [ $l+1$ , $r$] 加上$D$, 最后在 $r+1$ 减去 $[ k+D*(r-l) ]$。
# Ⅱ. 贪心
## P1607 [ USACO09FEB ] Fair Shuttle G
**题意** ： 从$1$ 到 $n$ 在有 $k$ 组cow，想从 $s$ 到 $e$, bus只能单向行驶，且容量为c, 问最大能有多少cow能达成目的。 （其中每组cow可以只有部分上车）
**分析** ： 用线段树模拟上车的过程，显然应该按照右端点排序。
然后就可以边模拟边用线段树维护已经在车上的最大人数。
## P1937 [ USACO10MAR ] Barn Allocation G
**题意** ： $n$ 个点，每个点有一个容量 $c_i$, $m$ 次操作，在$[l , r]$ 内加上 $1$，问最多能加几次。
**分析** ：
做完上一道就很点了，维护区间minn，可以就 $-1$，$ans$++
# Ⅳ. 最大子段和
单独拿出来了，~~也算是一类吧~~。目前做过的都比较明显。
## P4513 小白逛公园 & GSS3 - Can you answer these queries III
**题意** ： 1. 查询区间最大子段和； 2.单点修改
**分析** ： 板子。
将子树 $ls$ 和 $rs$ 的节点信息上传到父节点 $u$ 时，对于 $u$ 维护的序列中，和最大的子段有两种情况：
$case1:$ 子段不经过中点，那么 $u$ 的答案为 $ls$ 和 $rs$ 的答案的最大值。
$case2:$ 子段经过了中点。这种情况比较复杂，因为我们无法知道子树的答案所对应的序列。这也是本题的难点所在。
接下来对第 22 种情况进行重点分析：
我们记 $ms$ 为区间最长子段和，$sum$ 为区间和，$prel$ 和 $prer$ 分别表示从区间左端点和右端点开始的最大子段和。
考虑 $ pushup $：$sum$ 可以直接上传，$prel[u]=\max(prel[ls],sum[ls]+prel[rs]) \quad $（$prer$ 同理）
$ms[u]=\max(res[ls],ms[rs],prer[ls]+prel[rs]) \quad $
#### Notice：
**$query$有~~一点~~变化** ：
```cpp
Info query(int u,int l,int r){
if(tr[u].l>=l and tr[u].r<=r){
return tr[u];
}
if(r<=mid) return query(ls,l,r); //千万注意
if(l>mid) return query(rs,l,r);
Info T, L=query(ls,l,r), R=query(rs,l,r);
T.sum=L.sum+R.sum;
T.lsum=max(L.lsum,L.sum+R.lsum);
T.rsum=max(R.rsum,R.sum+L.rsum);
T.ms=max(max(L.ms,R.ms),L.rsum+R.lsum);
return T;
}
```
参考：[Siyuan](https://www.luogu.com.cn/user/49725)，[SP1716](https://www.luogu.com.cn/problem/solution/SP1716) sol
## P2572 [SCOI2010] 序列操作
**题意** ：
- `0 l r` 把 $[l, r]$ 区间内的所有数全变成 $0$；
- `1 l r` 把 $[l, r]$ 区间内的所有数全变成 $1$；
- `2 l r` 把 $[l,r]$ 区间内的所有数全部取反，也就是说把所有的 $0$ 变成 $1$，把所有的 $1$ 变成 $0$；
- `3 l r` 询问 $[l, r]$ 区间内总共有多少个 $1$；
- `4 l r` 询问 $[l, r]$ 区间内最多有多少个连续的 $1$。
**分析** ：
类似最大子段和的思想，相当于记录了2个最大子段和（0和1）,同时维护前后缀$sum$。
$Notice : $ 前后缀 $sum$ 的更新
$\quad\quad\quad u.prel_0= ls.sum_o ~?~ ls.prel_0 : ls.sum_0 + rs.prel_o$
## P4118 [Ynoi2018] 末日时在做什么？有没有空？可以来拯救吗？
**~~~~不会~~~~**
# Ⅴ. 优化建图
**Statement** ：大多与最短路有关（~~其它的太难了也不去做~~） 建一棵in树和out树，in树由上到下连边，再连向out树，out树自下而上连边。这样，如果要连 $ 1$ 到 $[ 4 ,6 ]$ 的边，只需于fa节点相连。
$O(n) -$> $O( \log_ 2x ) $
参考：[maoyiting](https://www.cnblogs.com/maoyiting/p/13764109.html#/cnblog/works/article/13764109)
**Notice** : 实际上不需要开structure，只需要记录左右 $l,r$，以及一个极大的 $\Delta K$ ,为了分别表示 $in$ 树和 $out$ 树，然后直接建图即可。
## CF786B Legacy
**题意** ： 1. 把$u,v$ 连 $w$ 的边 2.把 $u$ 连向 $[l ,r]$ 3.把 $[l , r]$连向u. 求s号点到其它的最短路。
**sol** : 线段树优化建图，$dijkstra$.
**code** :
```cpp
void add(){
}
void build(int u,int l,int r){
if(l==r){
a[l]=u; return;
}
add(u,ls,0); add(u,rs,0);
add(ls+k,u+k,0); add(rs+k,u+k,0);
build(ls,l,mid); build(rs,mid + 1,r);
}
void modify(int u,int l,int r,int x,int y,int v,int w){
if(l>=x and r<=y){
if(opt==2) add(v+k,u,w);
else add(u+k,v,w);
return;
}
if(x<=mid) modify(ls,l,mid,x,y,v,w);
if(y>mid) modify(rs,mid+1,r,x,y,v,w);
}
void djkstra(){
}
signed main(){
read(n,m,s);
build(1,1,n);
rep(i,1,n) add(a[i],a[i]+k,0),add(a[i]+k,a[i],0);
rep(i,1,m){
read(opt);
if(opt==1){
int u,v,w; read(u,v,w);
add(a[u]+k,a[v],w);
}
else{
int u,l,r,w; read(u,l,r,w);
modify(1,1,n,l,r,a[u],w);
}
}
dijkstra(a[s]+k);
rep(i,1,n){
printf("%lld ",dis[a[i]]==0x3f3f3f3f3f3f3f3fll? -1:dis[a[i]]);
}
return 0;
}
```
# Ⅵ. 二分
权值线段树上可以直接二分，应用：逆序对
## P2824 [HEOI2016/TJOI2016] 排序
**题意** ： 一个排列n，m次操作，把$[l,r]$升序或降序，求最后完成操作后第p位置上的数。
**分析** ：
1. 暴力排序 + 超快读，喜提80分
2. 正解 ： 线段树 + 二分。 二分第p位置上的数，把小于p的数改为0，大于等于p的数改为1,。记$[l,r]$内1的个数为 $ cnt $ ,如果把$[l,r]$升序，就把 $r-cnt+1$ 的数都改为$1$,其余改为$0$；降序相反。第一个是$1$的位置就是答案。
**code** :
```cpp
void pushup(int u){
tr[u].sum=tr[ls].sum+tr[rs].sum;
}
void pushdown(int u){
if(~tr[u].tag){
tr[ls].tag=tr[rs].tag=tr[u].tag;
tr[ls].sum=tr[u].tag*len(tr[ls]);
tr[rs].sum=tr[u].tag*len(tr[rs]);
tr[u].tag=-1;
}
}
void build(int u,int l,int r,int k){
tr[u]={l,r,0,-1};
if(l==r){
tr[u].sum=(a[l]>=k);
return;
}
build(ls,l,mid,k); build(rs,mid+1,r,k);
pushup(u);
}
void assign(int u,int l,int r,int k){
if(tr[u].l>=l and tr[u].r<=r){
tr[u].sum=len(tr[u])*k;
tr[u].tag=k;
return;
}
pushdown(u);
if(l<=mid) assign(ls,l,r,k);
if(r>mid) assign(rs,l,r,k);
pushup(u);
}
int query(int u,int l,int r){
return sum;
}
int check(int k){
build(1,1,n,k);
rep(i,1,m){
int l=x[i],r=y[i],k=op[i];
int cnt=query(1,l,r);
if(!k){
assign(1,r-cnt+1,r,1);
assign(1,l,r-cnt,0);
}
else{
assign(1,l,l+cnt-1,1);
assign(1,l+cnt,r,0);
}
}
return query(1,p,p);
}
int main(){
......
int l=0,r=n;
while(l>1;
if(check(MID)) l=MID;
else r=MID-1;
}
cout<len_0$，那么就从$l_1$开始，如果$len_1>1;
if(find(1,l1,M,0)