标签：题意 rs int 线段练习 tr ls sum

Ⅰ.差分与前缀和

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$有一点变化 ：

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，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

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 :

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位置上的数。

分析：

暴力排序 + 超快读，喜提80分
正解：线段树 + 二分。二分第p位置上的数，把小于p的数改为0，大于等于p的数改为1,。记$[l,r]$内1的个数为 $ cnt $ ,如果把$[l,r]$升序，就把 $r-cnt+1$ 的数都改为$1$,其余改为$0$；降序相反。第一个是$1$的位置就是答案。

code :

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<r){
		int MID=(l+r+1)>>1;
		if(check(MID)) l=MID;
		else r=MID-1;
	}
	cout<<l;
	return 0;
}

P4344 [SHOI2015] 脑洞治疗仪：

题意：一个长度为$n$的$01$序列，初始时均为$1$，三种操作：

将$[l,r]$覆盖为0。
$[l_o,r_o]$复制到$[l_1,r_1]$，并把$[l_0,r_0]$覆盖为$0$。如果$len_1>len_0$，那么就从$l_1$开始，如果$len_1<len_0$,则直接把$len_0$多出的部分直接去掉。
查询$[l,r]$内最长连续的$0$的长度。

分析：

查询最长连续子段和，考虑记录 $0$ 的$sum,lsum,rsum,ms$, $Pushup$ 和 $Pushdown$ 同序列操作。
考虑操作$2$，只需考虑$[l1,r1]$会复制到的右端点，很显然的是，$0$的个数具有单调性，$r_1$越大，$0$的个数越多，可以二分右端点，$check(0)$的个数。

void work(){
	int l0,r0,l1,r1;
	scanf("%d%d%d%d",&l0,&r0,&l1,&r1);
	int cnt=find(1,l0,r0,1);
	if(cnt==0) return;
	modify(1,l0,r0,0);
	int l=l1,r=r1;
	while(l<r){
		int M=(l+r)>>1;
		if(find(1,l1,M,0)<cnt) l=M+1;
		else r=M;
	}
	modify(1,l1,l,1);
}

标签：题意,rs,int,线段,练习,tr,ls,sum
From： https://www.cnblogs.com/jxkzkal/p/17962769

线段树练习

Ⅰ.差分与前缀和

P2184 贪婪大陆

P1438 无聊的数列

Ⅱ. 贪心

P1607 [ USACO09FEB ] Fair Shuttle G

P1937 [ USACO10MAR ] Barn Allocation G

Ⅳ. 最大子段和

P4513 小白逛公园 & GSS3 - Can you answer these queries III

Notice：

P2572 [SCOI2010] 序列操作

P4118 [Ynoi2018] 末日时在做什么？有没有空？可以来拯救吗？

Ⅴ. 优化建图

CF786B Legacy

Ⅵ. 二分

P2824 [HEOI2016/TJOI2016] 排序

P4344 [SHOI2015] 脑洞治疗仪：

相关文章

赞助商

阅读排行

线段树练习

Ⅰ.差分与前缀和

P2184 贪婪大陆

P1438 无聊的数列

Ⅱ. 贪心

P1607 [ USACO09FEB ] Fair Shuttle G

P1937 [ USACO10MAR ] Barn Allocation G

Ⅳ. 最大子段和

P4513 小白逛公园 & GSS3 - Can you answer these queries III

Notice：

P2572 [SCOI2010] 序列操作

P4118 [Ynoi2018] 末日时在做什么？有没有空？可以来拯救吗？

Ⅴ. 优化建图

CF786B Legacy

Ⅵ. 二分

P2824 [HEOI2016/TJOI2016] 排序

P4344 [SHOI2015] 脑洞治疗仪 ：

相关文章

赞助商

阅读排行

P4344 [SHOI2015] 脑洞治疗仪：