线段树题单记录

2024-07-31 21:34 由 CLydq 发表于 #后端开发

线段树题单记录

~~线段树的题都很板的，模板敲上去再改改就行~~

~~有的题你用的线段树可能都可以删除一部分并正常使用~~

TODO

~~什么你问为什么有的题是两重确认？啊那是因为我还没写（~~

P3372 【模板】线段树 1

题目

Link

~~为什么模板是绿题，还有下面那道~~

思路

首先我们要明白它为什么叫线段树：

OI Wiki 上的这张图很好理解：

从这张图也可以看出来，线段树的每个节点管辖的一个又一个的线段（区间），所以我们通俗地叫它线段树。

废话

这里只讲最简单的线段树，关于什么 ZKW 线段树、动态开点线段树请自行了解。

~~普通线段树学完了好像那些奇奇怪怪的线段树优化更好理解~~

线段树的功能很简单，就是对区间进行维护。

维护包括但不限于和、积和极值。

~~那还要珂朵莉树干什么~~

好吧它们各有优劣。

~~虽然珂朵莉树快~~

线段树的复杂度有一个 \(4\) 的常数，所以能不用线段树尽量不用线段树。

~~\(st\)~~ ~~表和树状数组的题线段树都能做，但是可能会被出题人卡常~~

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
#define int long long
inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
struct node{
	int l,r;
	int s;
	int lt;
}t[N*4];
int n,m;
int a[N];
void pushup(int p){t[p].s=t[p*2].s+t[p*2+1].s;}
void pushdown(int p){
	if(t[p].lt==0)
		return;
    t[p*2].s+=t[p].lt*(t[p*2].r-t[p*2].l+1);
    t[p*2+1].s+=t[p].lt*(t[p*2+1].r-t[p*2+1].l+1);
	t[p*2].lt+=t[p].lt;
	t[p*2+1].lt+=t[p].lt;
	t[p].lt=0;
}
void build(int p,int l,int r){
	t[p].l=l;
	t[p].r=r;
	if(l==r){t[p].s=a[l];return;}
	int mid=(l+r)>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	pushup(p);
}
void update(int p,int l,int r,int c){
	if(t[p].l>=l&&t[p].r<=r){
		t[p].lt+=c;
		t[p].s+=c*(t[p].r-t[p].l+1);
		return;
	}
	pushdown(p);
	int mid=(t[p].l+t[p].r)>>1;
	if(l<=mid)
		update(p*2,l,r,c);
	if(r>mid)
		update(p*2+1,l,r,c);
	pushup(p);
}
int query(int p,int l,int r){
	if(t[p].l>=l&&t[p].r<=r)
		return t[p].s;
	int reu=0;
	int mid=(t[p].l+t[p].r)>>1;
	pushdown(p);
	if(l<=mid)
		reu+=query(p*2,l,r);
	if(r>mid)
		reu+=query(p*2+1,l,r);
	return reu;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	build(1,1,n);
	int ty;
	int x,y,k;
	for(int i=1;i<=m;i++){
		cin>>ty;
		if(ty==1){
			cin>>x>>y>>k;
			update(1,x,y,k);
		}
		else{
			cin>>x>>y;
			cout<<query(1,x,y)<<endl;
		}
	}
	return 0;
}

建树复杂度：\(O (NlogN)\)

查询复杂度：\(O (logN)\)

修改复杂度：\(O (logN)\)

代码解释

先说它优化时间复杂度的原理。

优化原理 && \(lt\)

重在 \(lt\)。

它是 \(LazyTag\) 的缩写，中文即懒标记。

它的作用很简单。

当我们修改到某一个节点，而这个节点被修改区间包含时，我们就可以直接修改该区间的值并 return。这可以大大节省时间。

~~最极限的情况下一次也只需要遍历~~ ~~\(logN\)~~ 个点

但是由于它的儿子没有被修改，所以我们需要记录已经修改的值再 return。

如果下一次经过这个节点，就先将 \(lt\) 给传递下去，以保证儿子的和是最新的。否则，可能你的某次修改就会被吞掉。

变量声明

结构体 \(node\)：树的结点，包含左右端点和保存的信息什么的。

数组 \(t\)：树的数组

数组 \(a\)：原始数组

\(int\) 整型 \(n\)：原始数组长度

\(int\) 整型 \(m\)：操作个数

build

定义：void build (int p,int l,int r)

传入三个参数：节点编号 \(p\)，该节点的左端点 \(l\) 和右端点 \(r\)。

然后对其进行赋值 t [p].l=l;t [p].r=r;（有些题目可能要赋的值比较多）。

然后递归建树：

    if(l==r){t[p].s=a[l];return;}
	int mid=(l+r)>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	pushup(p);

如果说当前节点的左右端点编号相等，就证明它已经建到叶子节点了，就可以赋值 return 了。

否则，就将区间不严格对半拆开，然后递归建树，然后 pushup。

然后你就看到了突然出现的 pushup。

pushup

声明：void pushup (int p)

pushup 是用来在子节点更新完后更新父节点的。

其中 \(p\) 是节点编号，这道题中该节点的区间和等于它左右儿子的和的和。

有些题目可能要维护的东西比较多，比如下面的 P1471 方差那道题。

它的作用很简单，就是在儿子节点修改后将修改值给向上推给父亲：{t [p].s=t [p*2].s+t[p*2+1].s;}

现在树建完了，然后该维护和查询了。

update

声明：void update (int p,int l,int r,int c)

传入 \(4\) 个参数：

当前节点 \(p\)、当前修改的左端点 \(l\)、当前修改的右端点 \(r\)、当前修改值 \(c\)。

如果说当前节点的左右端点已经被完全包含了，那么就在当前节点修改并 return：

	if(t[p].l>=l&&t[p].r<=r){
		t[p].lt+=c;
		t[p].s+=c*(t[p].r-t[p].l+1);
		return;
	}

否则，继续往下递归修改：

	pushdown(p);
	int mid=(t[p].l+t[p].r)>>1;
	if(l<=mid)
		update(p*2,l,r,c);
	if(r>mid)
		update(p*2+1,l,r,c);
	pushup(p);

于是我们就看到了 pushdown 函数。

pushdown

声明：void pushdown (int p)

这个函数是用来进行儿子节点更新的，传入要进行 pushdown 操作的节点编号 \(p\)，然后进行修改，就像这样：

{
	if(t[p].lt==0)
		return;
    t[p*2].s+=t[p].lt*(t[p*2].r-t[p*2].l+1);
    t[p*2+1].s+=t[p].lt*(t[p*2+1].r-t[p*2+1].l+1);
	t[p*2].lt+=t[p].lt;
	t[p*2+1].lt+=t[p].lt;
	t[p].lt=0;
}

那个 if (t [p].lt==0) return; 是用来进行判断的：如果当前节点没有需要进行 pushdown 操作的懒标记就 return。没有它也行，它主要是用来加快程序运行的。

~~这里也是题目设难点的一个重灾区，某些题目要考虑的情况很多，一不注意就~~ ~~\(WA\)~~ 了

现在我们来看查询 query。

query

声明：int query (int p,int l,int r)

传入三个参数：

当前节点编号 \(p\)、当前修改的左端点 \(l\)、当前修改的右端点 \(r\)。

和 update 差不多，query 的判断逻辑也是如果说当前节点的左右端点已经被查询区间完全包含了，那么就 return 当前节点的查询值：

	if(t[p].l>=l&&t[p].r<=r)
	    return t[p].s;

否则就接着往下查询：

    int reu=0;
    int mid=(t[p].l+t[p].r)>>1;
    pushdown(p);
    if(l<=mid)
        reu+=query(p*2,l,r);
    if(r>mid)
        reu+=query(p*2+1,l,r);
    return reu;

至此，整个线段树的核心代码就讲完了。

可能有的人会比较好奇，pushdown 和 pushup 是个什么用的，为什么要在那些位置放他们 ~~是的没错就是我朋友的问题~~。

关于 `pushup` 和 `pushdown`

为什么会有它俩：

~~用 OI Wiki 上的图画的~~

假如说我们某次修改了区间 [1,3]（图中红色区间）。

现在我们要查询区间 [2,2] ~~其实就一个点~~（图中蓝色的点）。

然后你会发现它并没有被修改，所以在 query 中出现了 pushdown，用来确保它的儿子节点是最新的。

那么它为什么没有 pushup 呢？

有也可以，但是由于它的儿子节点没有 被修改，所以我们用不到 pushup。

那么这个 “被修改” 是什么意思呢？

显然，这里在它的儿子节点修改之前它已经修改过了，所以它不用修改。

那么 update 中为什么会同时有 pushup 和 pushdown 呢？

还是这张图。

假如说我们现在蓝色标记不是查询而是修改，即

我们某次修改了区间 [1,3]（图中红色区间）。

现在我们要修改区间 [2,2]（图中蓝色的点）。

然后我们会发现，它的值不是最新的，我们要把 [1,3] 区间的懒标记进行 pushdown 操作已保证修改前它的值是最新的。

那为什么还要有 pushup 操作呢？

和刚刚的 update 相对，这里它的子节点一定被修改了，而且这次修改没有在它自己身上体现，所以我们需要用 pushup 进行修改以确保它是最新的。

P3373 【模板】线段树 2

Link

题目思路

这个不就是多个 \(lt\)，原有 \(lt\) 功能不变，新的 \(lt\) 用来保存乘积吗，pushdown 的时候先 pushdown 乘积再 pushdown 和就行了。

~~这题还行，某~~ ~~\(AT\)~~ ~~\(ABC\)~~ ~~的题 MD 少~~ ~~\(mod\)~~ ~~了两下连~~ ~~\(unsigned long long\)~~ ~~都给我爆了（~~

关于为什么先 pushdown 乘积再 pushdown 和显然让我们来证一下：

首先，设其中三次修改分别为乘、加、乘，三次修改值分别为 \(x\)、\(y\)、\(z\)。原数列为 \(A\)，其中元素为 \(a\)，长度为 \(N\)（简写 \(n\)）。

那么修改后的和 \(NewSum\) 为：

我懒

\(NewSum\)

\(\xlongequal {} (a_1 \times x+y) \times z + \dots + (a_n \times x+y) \times z\)

\(\xlongequal {} a_1 \times x \times z + y \times z \dots + a_n \times x \times z+ y \times z\)

\(\xlongequal {} OldSum \times x \times z + n \times y \times z\)

所以我们要先更新乘法的懒标记再更新加法的懒标记。

~~应该没有人会把乘法的懒标记重置为~~ ~~\(0\)~~ 吧

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
#define int unsigned long long
struct node{
	int l,r;
	int s;
	int clt,jlt;
}t[N*4];
int a[N];
int n,q,m;
void pushup(int p){t[p].s=t[p*2].s+t[p*2+1].s;}
void mod(int p){t[p].jlt%=m;t[p].clt%=m;t[p].s%=m;}
void pushdown(int p){
	if(t[p].clt==1&&t[p].jlt==0)
		return;
	t[p*2].jlt*=t[p].clt,mod(p*2);
	t[p*2].clt*=t[p].clt,mod(p*2);
	t[p*2].s*=t[p].clt,mod(p*2);
	t[p*2+1].jlt*=t[p].clt,mod(p*2+1);
	t[p*2+1].clt*=t[p].clt,mod(p*2+1);
	t[p*2+1].s*=t[p].clt,mod(p*2+1);
	t[p*2].jlt+=t[p].jlt,mod(p*2);
	t[p*2].s+=t[p].jlt*(t[p*2].r-t[p*2].l+1),mod(p*2);
	t[p*2+1].jlt+=t[p].jlt,mod(p*2+1);
	t[p*2+1].s+=t[p].jlt*(t[p*2+1].r-t[p*2+1].l+1),mod(p*2+1);
	mod(p*2),mod(p*2+1),mod(p);
	t[p].jlt=0,t[p].clt=1;
}
void build(int p,int l,int r){
	t[p].l=l,t[p].r=r,t[p].clt=1,t[p].jlt=0;
	if(l==r){t[p].s=a[l];return;}
	int mid=(l+r)>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	pushup(p);
}
void update(int p,int l,int r,int k,int ty){
	if(t[p].l>=l&&t[p].r<=r){
		if(ty==1){
			t[p].clt*=k,t[p].clt%=m;
			t[p].jlt*=k,t[p].jlt%=m;
			t[p].s*=k,t[p].s%=m;
		}
		else{
			t[p].jlt+=k,t[p].jlt%=m;
			t[p].s+=k*(t[p].r-t[p].l+1),t[p].s%=m;
		}
		return;
	}
	pushdown(p);
	int mid=(t[p].l+t[p].r)>>1;
	if(l<=mid)
		update(p*2,l,r,k,ty);
	if(r>mid)
		update(p*2+1,l,r,k,ty);
	pushup(p);
}
int query(int p,int l,int r){
	if(t[p].l>=l&&t[p].r<=r)
		return t[p].s%m;
	int reu=0;
	int mid=(t[p].l+t[p].r)>>1;
	pushdown(p);
	if(l<=mid)
		reu+=query(p*2,l,r),reu%=m;
	if(r>mid)
		reu+=query(p*2+1,l,r),reu%=m;
	return reu%m;
}
signed main(){
	cin>>n>>q>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	build(1,1,n);
	int x,y,k,ty;
	for(int i=1;i<=q;i++){
		cin>>ty>>x>>y;
		if(ty==3)
			cout<<query(1,x,y)%m<<endl;
		else
			cin>>k,update(1,x,y,k,ty);
	}
	return 0;
}

P1198 [JSOI2008] 最大数

Link

思路

这里应该用线段树动态开点做的。

but，它并没有强制要求在线。

也就是说，我们可以将所有操作记录下来，然后将 \(A\) 操作的数量进行计数，从而得到线段树长度 \(n\) 进行离线操作。

~~当时写的动态开点线段树出了亿点小 bug。~~

这里也体现了线段树的另外一个作用：维护区间最值，修改 pushup 、 query 和 update 就行。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
struct node{
	int l,r;
	int s;
}t[N*4];
int m,d,n;
pair <char,int> ps[N];
void pushup(int p){ t[p].s = max( t[p*2].s , t[p*2+1].s ) ; }
void build(int p,int l,int r){
	t[p].l=l,t[p].r=r,t[p].s=INT_MIN;
	if(l==r)
		return;
	int mid = ( l + r ) >> 1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
}
void update(int p,int l,int r,int c){
	if(t[p].l>=l&&t[p].r<=r){
		t[p].s=max(t[p].s,c);
		return;
	}
	int mid=(t[p].l+t[p].r)>>1;
	if(l<=mid)
		update(p*2,l,r,c);
	if(r>mid)
		update(p*2+1,l,r,c);
	pushup(p);
}
int query(int p,int l,int r){
	if(t[p].l>=l&&t[p].r<=r)
		return t[p].s;
	int reu=INT_MIN;
	int mid=(t[p].l+t[p].r)>>1;
	if(l<=mid)
		reu=max(query(p*2,l,r),reu);
	if(r>mid)
		reu=max(query(p*2+1,l,r),reu);
	return reu;
}
signed main(){
	cin>>m>>d;
	for(int i=1;i<=m;i++)
		cin >> ps[i].first >> ps[i].second ,
		n += ps[i].first == 'A' ? 1 : 0 ;
	build(1,1,n);
	int len = 0;
	int tm=0;
	for(int i=1;i<=m;i++)
		if(ps[i].first == 'A'){
			len ++ ;
			update(1,len,len,(ps[i].second+tm)%d);
		}
		else{
			tm=query(1,len-ps[i].second+1,len);
			cout<<tm<<endl;
		}
	return 0;
}

[ABC357F] Two Sequence Queries

Link - Luogu

Link - AtCoder

思路

关于为什么要把这个题给中间插过来：

因为它真的仅仅只是多维护了一点东西，就是个模板的难度，没什么思路。

~~但是它的数据是真的 unsigned long long 都给我爆了~~

单独维护三个和：

\(A\) 数组和

\(B\) 数组和

\(A\) 数组中每个元素 \(\times\) \(B\) 数组中每个对应位置的和

和两个 \(lt\)：

对 \(A\) 数组进行更新的 \(lt\)

对 \(B\) 数组进行更新的 \(lt\)

然后就行了。

这个题告诉我们一个道理：

有时候 \(mod\) 一下不行，你得多 \(mod\) 一下，不然 \(unsigned\) \(long\) \(long\) 都能给你干爆。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const int mod=998244353;
#define int unsigned long long
struct node{
	int l,r;
	int s,sa,sb;
	int lta,ltb;
}t[N*4];
int n,q;
int a[N],b[N];
inline void Gomod(int p){
	t[p].s%=mod;
	t[p].sa%=mod;
	t[p].sb%=mod;
	t[p].lta%=mod;
	t[p].ltb%=mod;
}
inline void pushup(int p){
	t[p].s=t[p*2].s+t[p*2+1].s;
	t[p].sa=t[p*2].sa+t[p*2+1].sa;
	t[p].sb=t[p*2].sb+t[p*2+1].sb;
	Gomod(p);
}
inline void upa(int p,int lt){
	Gomod(p);
	t[p].lta+=lt;
	t[p].sa+=lt*(t[p].r-t[p].l+1);
	t[p].s+=t[p].sb*lt;
	Gomod(p);
}
inline void upb(int p,int lt){
	Gomod(p);
	t[p].ltb+=lt;
	t[p].sb+=lt*(t[p].r-t[p].l+1);
	t[p].s+=t[p].sa*lt;
	Gomod(p);
}
void pushdown(int p){
	if(!t[p].lta&&!t[p].ltb)
		return;
	Gomod(p);
	upa(p*2,t[p].lta);
	upb(p*2,t[p].ltb);
	upa(p*2+1,t[p].lta);
	upb(p*2+1,t[p].ltb);
	t[p].lta=0;
	t[p].ltb=0;
}
void build(int p,int l,int r){
	t[p].l=l,t[p].r=r;
	if(l==r){
		t[p].sa=a[l];
		t[p].sb=b[l];
		t[p].s=a[l]*b[r];
		Gomod(p);
		return;
	}
	int mid=(l+r)>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	pushup(p);
	Gomod(p);
}
void update(int p,int l,int r,int x,int ty){
	if(t[p].l>=l&&t[p].r<=r){
		if(ty==1)
			upa(p,x);
		else
			upb(p,x);
		return;
	}
	int mid=(t[p].r+t[p].l)>>1;
	pushdown(p);
	if(l<=mid)
		update(p*2,l,r,x,ty);
	if(r>mid)
		update(p*2+1,l,r,x,ty);
	pushup(p);
}
int query(int p,int l,int r){
	if(t[p].l>=l&&t[p].r<=r)
		return t[p].s;
	pushdown(p);
	int reu=0,mid=(t[p].l+t[p].r)>>1;
	if(l<=mid)
		reu+=query(p*2,l,r),reu%=mod;
	if(r>mid)
		reu+=query(p*2+1,l,r),reu%=mod;
	return reu%mod;
}
inline void solve(){
	int ty,l,r,x;
	cin>>ty>>l>>r;
	if(ty!=3)
		cin>>x,update(1,l,r,x,ty);
	else
		cout<<query(1,l,r)%mod<<endl;
}
signed main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)
		cin>>b[i];
	build(1,1,n);
	for(int i=1;i<=q;i++)
		solve();
	return 0;
}

P1471 方差

Link

思路

这题蓝就蓝在那个方差公式的推导。

~~谁说这个公式是初中推了的，我们都没推~~

现在我们来推一下：

\([(X_1 - \overline{X})^2 + \dots + (X_n - \overline{X})^2] / n\)

\(\xlongequal {} [X_1^2 + \dots + X_n^2 - 2 \times (X_1 + \dots X_n) \times \overline{X} + n \times \overline {X}^2] / n\)

\(\xlongequal {} \overline{X} - 2 \times \overline{X} + (X_1^2 + \dots X_n^2) / n\)

\(\xlongequal {} (X_1^2 + \dots X_n^2) / n - \overline{X}\)

然后我们就可以看出来，这里要进行方差的查询，额外维护一个平方和即可。

~~\(oh\)~~ ~~对了别忘记数据是实数，我就卡在这里卡了一天~~

Code

#include <bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
const int N=1e5+5;
struct node{
	int l,r;
	int len;
	long double s;
	long double pfh;
	long double pjs;
	long double lt;
}t[N<<2];
int n,m;
long double a[N];
void pushup(int p){
	t[p].s=t[p*2].s+t[p*2+1].s;
	t[p].pfh=t[p*2].pfh+t[p*2+1].pfh;
	t[p].pjs=t[p].s/t[p].len;
}
void pushdown(int p){
	if(!t[p].lt)
		return;
	t[p*2].lt+=t[p].lt;
	t[p*2].pjs+=t[p].lt;
	t[p*2].pfh+=2*t[p].lt*t[p*2].s+t[p].lt*t[p].lt*t[p*2].len;
	t[p*2].s+=t[p].lt*t[p*2].len;
	t[p*2+1].lt+=t[p].lt;
	t[p*2+1].pjs+=t[p].lt;
	t[p*2+1].pfh+=2*t[p].lt*t[p*2+1].s+t[p].lt*t[p].lt*t[p*2+1].len;
	t[p*2+1].s+=t[p].lt*t[p*2+1].len;
	t[p].lt=0;
}
void build(int p,int l,int r){
	t[p].l=l,t[p].r=r,t[p].len=t[p].r-t[p].l+1;
	if(l==r){
		t[p].s=a[l];
		t[p].pfh=a[l]*a[r];
		t[p].pjs=a[r];
		return;
	}
	int mid=(l+r)>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	pushup(p);
}
void update(int p,int l,int r,long double k){
	if(t[p].l>=l&&t[p].r<=r){
		t[p].pfh+=2*k*t[p].s+k*k*t[p].len;
		t[p].s+=t[p].len*k;
		t[p].pjs+=k;
		t[p].lt+=k;
		return;
	}
	pushdown(p);
	int mid=(t[p].l+t[p].r)>>1;
	if(l<=mid)
		update(p*2,l,r,k);
	if(r>mid)
		update(p*2+1,l,r,k);
	pushup(p);
}
long double query(int p,int l,int r,int ty){
	if(t[p].l>=l&&t[p].r<=r)
		return ty==2 ? t[p].s : t[p].pfh;
	int mid=(t[p].l+t[p].r)>>1;
	long double reu=0;
	pushdown(p);
	if(l<=mid)
		reu+=query(p*2,l,r,ty);
	if(r>mid)
		reu+=query(p*2+1,l,r,ty);
	return reu;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	build(1,1,n);
	int ty,l,r;
	long double k;
	for(int i=1;i<=m;i++){
		cin>>ty>>l>>r;
		if(ty==1){
			cin>>k;
			update(1,l,r,k);
		}
		else if(ty==2)
			printf("%.4lf\n",(double)query(1,l,r,ty)/(r-l+1));
		else{
			int len=r-l+1;
			long double r1=query(1,l,r,2);
			long double r2=query(1,l,r,3);
			long double ans=(r2-r1*r1/len)/len;
			printf("%.4lf\n",(double)ans);
		}
	}
	return 0;
}

[COCI2010-2011#6] STEP

Link

思路

这里可以体现出线段树不只能维护区间某些数学值，也可以维护一些 ~~奇奇怪怪~~ 的值。

这道题的节点中需要维护的东西有亿点多，不过字符因为只有两种，为了方便，可以用 \(bool\) 类型来存。

就拿样例 \(1\) 来说明吧。

总共 \(6\) 个节点，\(5\) 次操作。

https://imgse.com/i/pkOP0L4

用颜色来区分 \(L\) 和 \(R\)，其中黑色为 \(L\)，红色为 \(R\)。

现在来想一下更新区间 \(1\) ~ \(3\) 的最大值时可能出现的情况：

1. 左右两段区间不能衔接

如图：

https://imgse.com/i/pkOP0L4

~~其实就是上面那张图~~

它的最值为它左右儿子的最值。

2. 左右两段区间可以相接

如图：

https://imgse.com/i/pkOP6F1

这种情况下，要额外考虑左右区间相接的情况对于区间最值潜在的影响。

综上，我们可以得出：

节点中需要保存的信息有：

左右端点 ~~这个不用说了吧~~
区间最值
区间左侧字母
区间右侧字母
区间从左侧开始最值
区间从右侧开始最值

更新时，需要额外考虑左右区间能否相接以更新最值。

Code

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
struct node{
	int l,r;
	int len;
	int s;
	int ls,rs;
	bool cl,cr;
}t[N*4];
int n,q;
void pushup(int p){
	t[p].s=max(t[p*2].s,t[p*2+1].s);
	if(t[p*2].cr!=t[p*2+1].cl)
		t[p].s=max(t[p].s,t[p*2].rs+t[p*2+1].ls);
	t[p].cl=t[p*2].cl;
	t[p].cr=t[p*2+1].cr;
	if(t[p*2].ls==t[p*2].len&&t[p*2].cr!=t[p*2+1].cl)
		t[p].ls=t[p*2].ls+t[p*2+1].ls;
	else
		t[p].ls=t[p*2].ls;
	if(t[p*2+1].rs==t[p*2+1].len&&t[p*2].cr!=t[p*2+1].cl)
		t[p].rs=t[p*2+1].rs+t[p*2].rs;
	else
		t[p].rs=t[p*2+1].rs;
}
void build(int p,int l,int r){
	t[p].l=l,t[p].r=r;
	t[p].len=t[p].r-t[p].l+1;
	t[p].cl=0,t[p].cr=0;
	if(l==r){
		t[p].s=1;
		t[p].ls=1;
		t[p].rs=1;
		return;
	}
	int mid=(l+r)>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	pushup(p);
}
void update(int p,int l,int r){
	if(t[p].l>=l&&t[p].r<=r){
		t[p].cl=1-t[p].cl;
		t[p].cr=1-t[p].cr;
		return;
	}
	int mid=(t[p].l+t[p].r)>>1;
	if(l<=mid)
		update(p*2,l,r);
	if(r>mid)
		update(p*2+1,l,r);
	pushup(p);
}
int query(int p,int l,int r){
	if(t[p].l>=l&&t[p].r<=r)
		return t[p].s;
	int reu=0;
	int mid=(t[p].l+t[p].r)>>1;
	int ql=query(p*2,l,r);
	int qr=query(p*2+1,l,r);
	if(l<=mid&&!(r>mid))
		reu=ql;
	if(r>mid&&!(l<=mid))
		reu=qr;
	if(l<=mid&&r>mid)
		if(t[p*2].cr!=t[p*2+1].cl)
			reu=max(max(ql,qr),t[p*2].rs+t[p*2+1].ls);
	return reu;
}
signed main(){
	cin>>n>>q;
	int x;
	build(1,1,n);
	for(int i=1;i<=q;i++)
		cin>>x,update(1,x,x),cout<<query(1,1,n)<<endl;
	return 0;
}

贪婪大陆

Link

思路

考虑把区间抽象成线段：

https://imgse.com/i/pkOaKUJ

然后我们就可以比较直观的理解埋地雷的操作了：

https://imgse.com/i/pkOaD2t

是的。

我们只需要考虑当前区间左侧有多少右端点，右侧有多少左端点，然后从埋下的地雷种类总数中减掉他们就行了。

为什么？

直接统计在区间内的地雷显然不是很好求。

~~如果你有方法可以发到评论区~~

那么，我们可以转换问题为求有多少种地雷不在区间内，然后用地雷种类总数减掉它们就行。

Code

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct Tree{
	struct node{
		int l,r;
		int lt,s;
	}t[N*4];
	int n;
	void pushup(int p){t[p].s=t[p*2].s+t[p*2+1].s;}
	void pushdown(int p){
		if(!t[p].lt)
			return;
		t[p*2].lt+=t[p].lt;
		t[p*2].s+=t[p].lt;
		t[p*2+1].lt+=t[p].lt;
		t[p*2+1].s+=t[p].lt;
		t[p].lt=0;
	}
	void build(int p,int l,int r){
		t[p].l=l,t[p].r=r,t[p].s=0;
		if(l==r)
			return;
		int mid=(l+r)>>1;
		build(p*2,l,mid);
		build(p*2+1,mid+1,r);
	}
	int query(int p,int l,int r){
		if(t[p].l>=l&&t[p].r<=r)
			return t[p].s;
		int reu=0;
		int mid=(t[p].l+t[p].r)>>1;
		pushdown(p);
		if(l<=mid)
			reu+=query(p*2,l,r);
		if(r>mid)
			reu+=query(p*2+1,l,r);
		return reu;
	}
	void update(int p,int l,int r,int c){
		if(t[p].l>=l&&t[p].r<=r){
			t[p].lt+=c;
			t[p].s+=c;
			return;
		}
		pushdown(p);
		int mid=(t[p].l+t[p].r)>>1;
		if(l<=mid)
			update(p*2,l,r,c);
		if(r>mid)
			update(p*2+1,l,r,c);
		pushup(p);
	}
}lt,rt;
int n,m;
signed main(){
	cin>>n>>m;
	lt.n=n;
	rt.n=n;
	lt.build(1,1,n);
	rt.build(1,1,n);
	int q,l,r,k=0;
	for(int i=1;i<=m;i++){
		cin>>q>>l>>r;
		if(q==1)
			lt.update(1,l,l,1),rt.update(1,r,r,1),k++;
		else{
			int cost=0;
			if(l-1 >= 1)
				cost+=rt.query(1,1,l-1);
			if(r+1 <= n)
				cost+=lt.query(1,r+1,n);
			cout<<k-cost<<endl;
		}
	}
	return 0;
}

全村最好的嘤嘤刀

Link

思路

~~你猜它为什么在这里~~

~~因为我善（bushi~~

‍

Code

#include <bits/stdc++.h>
using namespace std;
#define rint register int
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;}
inline void writes(string s){int len=s.length();for(rint i=0;i<len;i++)putchar(s[i]);}
inline void write(long long x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');}
inline string reads(){string s="";char ch=getchar();while(ch==' '||ch=='\n')ch=getchar();while(ch!=' '&&ch!='\n')s+=ch,ch=getchar();return s;}
const int N=100005;
struct node{
	int l,r;
	int lt;
	int mx,pl;
	friend ostream &operator << (ostream &out,node &a){
		out<<" node: l:"<<a.l<<" r:"<<a.r<<" lt:"<<a.lt<<" mx:"<<a.mx<<" pl:"<<a.pl;
		return out;
	}
}t[N<<2];
int n,m,spc=0;
int a[N];
inline void pushup(int p){
	if(t[p<<1].mx>t[p*2+1].mx)
		t[p].mx=t[p<<1].mx,t[p].pl=t[p<<1].pl;
	else
		t[p].mx=t[p*2+1].mx,t[p].pl=t[p*2+1].pl;
}
inline void pushdown(int p){
	if(!t[p].lt)
		return;
	t[p<<1].mx+=t[p].lt;
	t[p<<1].lt+=t[p].lt;
	t[p*2+1].mx+=t[p].lt;
	t[p*2+1].lt+=t[p].lt;
	t[p].lt=0;
}
void build(int p,int l,int r){
	t[p].l=l,t[p].r=r;
	if(l==r){
		t[p].mx=a[l];
		t[p].pl=r;
		return;
	}
	int mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p*2+1,mid+1,r);
	pushup(p);
}
//sp==1 表示这次修改为情况 1，否则为情况 3
void update(int p,int l,int r,int val,bool sp){
	if(t[p].l>=l&&t[p].r<=r){
		if(sp)
			t[p].mx=val-t[p].mx;
		else
			t[p].mx+=val,t[p].lt+=val;
		return;
	}
	int mid=(t[p].l+t[p].r)>>1;
	pushdown(p);
	if(l<=mid)
		update(p<<1,l,r,val,sp);
	if(r>mid)
		update(p*2+1,l,r,val,sp);
	pushup(p);
}
node query(int p,int l,int r){
	if(t[p].l>=l&&t[p].r<=r){
		return t[p];
	}
	int mid=(t[p].l+t[p].r)>>1;
	node reu={0,0,INT_MIN,INT_MIN,0};
	pushdown(p);
	if(l<=mid)
		reu=query(p<<1,l,r);
	if(r>mid){
		node tmp=query(p*2+1,l,r);
		if(reu.l){
			if(tmp.mx>=reu.mx)
				reu=tmp;
		}
		else
			reu=tmp;
	}
	return reu;
}
void clear(int p,int l,int r){
	if(t[p].l>=l&&t[p].r<=r){
		t[p].mx=0;
		return;
	}
	int mid=(t[p].l+t[p].r)>>1;
	pushdown(p);
	if(l<=mid)
		clear(p<<1,l,r);
	if(r>mid)
		clear(p*2+1,l,r);
	pushup(p);
}
int ts[N];
inline int lowbit(int x){ return x & (-x) ; }
inline void add(int x,int y){
	while(x<=n){
		ts[x]+=y;
		x+=lowbit(x);
	}
}
inline int sum(int x){
	int reu=0;
	while(x){
		reu+=ts[x];
		x-=lowbit(x);
	}
	return reu;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	build(1,1,n);
	int op,l,r,x,val;
	for(int i=1;i<=m;i++){
		cin>>op;
		if(op==1){
			cin>>x>>val;
			update(1,x,x,val,1);
			add(x,x);
		}
		else if(op==2){
			cin>>l>>r;
			int pl=sum(r)-sum(l-1);
			node tmp;
			if(pl){
				tmp=query(1,pl,pl);
				add(pl,-pl);
				clear(1,pl,pl);
			}
			else{
				tmp=query(1,l,r);
				update(1,tmp.pl,tmp.pl,-tmp.mx,0);
			}
			spc+=tmp.mx;
			cout<<tmp.mx<<endl;
		}
		else{
			cin>>l>>r>>val;
			update(1,l,r,val,0);
		}
	}
	if(spc<10000)
		cout<<"QAQ";
	else if(spc<10000000)
		cout<<"Sakura";
	else
		cout<<"ice";
	return 0;
}

无聊的数列

Link

思路

‍

Code

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
#define int long long
struct node{
	int l,r;
	int lt,s;
}t[N*4];
int n,m;
int a[N],d[N];
void pushup(int p){t[p].s=t[p*2].s+t[p*2+1].s;}
void pushdown(int p){
	if(!t[p].lt)
		return;
	t[p*2].lt+=t[p].lt;
	t[p*2].s+=t[p].lt*(t[p*2].r-t[p*2].l+1);
	t[p*2+1].lt+=t[p].lt;
	t[p*2+1].s+=t[p].lt*(t[p*2+1].r-t[p*2+1].l+1);
	t[p].lt=0;
}
void build(int p,int l,int r){
	t[p].l=l,t[p].r=r;
	if(l==r){
		t[p].s=d[l];
		return;
	}
	int mid=(l+r)>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	pushup(p);
}
void update(int p,int l,int r,int c){
	if(t[p].l>=l&&t[p].r<=r){
		t[p].lt+=c;
		t[p].s+=(t[p].r-t[p].l+1)*c;
		return;
	}
	pushdown(p);
	int mid=(t[p].l+t[p].r)>>1;
	if(l<=mid)
		update(p*2,l,r,c);
	if(r>mid)
		update(p*2+1,l,r,c);
	pushup(p);
}
int query(int p,int l,int r){
	if(t[p].l>=l&&t[p].r<=r)
		return t[p].s;
	pushdown(p);
	int mid=(t[p].l+t[p].r)>>1;
	int reu=0;
	if(l<=mid)
		reu+=query(p*2,l,r);
	if(r>mid)
		reu+=query(p*2+1,l,r);
	return reu;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i],d[i]=a[i]-a[i-1];
	build(1,1,n);
	int opt,l,r,k,d,p;
	for(int i=1;i<=m;i++){
		cin>>opt;
		if(opt==1){
			cin>>l>>r>>k>>d;
			update(1,l,l,k);
			if(l+1<=r)
				update(1,l+1,r,d);
			if(r<n)
				update(1,r+1,r+1,-(r-l)*d-k);
		}
		else{
			cin>>p;
			cout<<query(1,1,p)<<endl;
		}
	}
	return 0;
}

全网最适合入门的面向对象编程教程：29 类和对象的Python实现-断言与防御性编程和help函数的使用

在Python中，断言是一种常用的调试工具，它允许程序员编写一条检查某个条件。本文主要介绍了断言的应用场景和特点以及assert语句的使用，同时介绍了防御性编程和help()函数。 ...阅读全文

java基础知识汇总（二）

PART1:变量与数据类型 Java语言是强类型语言，对于每一种数据都定义了明确的具体数据类型，在内存总分配了不同大小的内存空间。整数默认：int 小数默认：double 使用变量注意事项：作用域：变量定义在哪一级大括号中，哪个大括号的范围就是这个变量的作用域。相同的作用域中不能定义两个同名变量 ...阅读全文

三，搭建环境：事务控制

三，搭建环境：事务控制 @目录三，搭建环境：事务控制声明式事务配置注解写法查询操作增删改操作声明式事务配置在 demo-module01-web 的模块下的，spring-persist.xml 配置文件中开启基于注解的声明式事务支持  <bean id="tr ...阅读全文

服务注册中心+配置中心-Nacos-微服务核心组件【分布式微服务笔记07】

服务注册中心+配置中心-Nacos-微服务核心组件【分布式微服务笔记07】服务注册中心+配置中心-Nacos Nacos 有两大功能：注册中心[替代Eureka]+配置中心[替代Config] 架构理论基础: CAP 理论(支持AP【高可用、分区容错性】和CP【分区容错性和数据一致性】, 可以 ...阅读全文

如何在Linux云服务器上通过Docker Compose部署安装Halo，搭建个人博客网站？

目录前置步骤环境搭建创建容器组在系统任意位置创建一个文件夹创建docker-compose.yaml启动 Halo 服务配置反向代理以及域名解析Halo初始化页面。更新新版本的halo 前置步骤首先你需要一套linux服务器，这里默认你已经有了。如果没有可以在云服务器优惠合集选择，如果你是个人博客 ...阅读全文

Spring循环依赖+案例解析

什么是Spring中的循环依赖？循环依赖是指两个或者多个bean互相依赖对方，从而形成一个闭环。例如：Bean A依赖于Bean B，而Bean B又依赖于Bean A。可能会导致Spring在尝试创建这些bean实例时出现问题，因为他们互相等待对方被创建，最终导致应用程序无法启动。 Spring ...阅读全文

java注解与反射(非常详细, 带有很多样例)

下面是详细地讲解 Java 中的注解与反射，并提供了很多的示例来帮助理解。 Java 注解（Annotations） 1. 注解的基本概念注解（Annotation）是 Java 5 引入的一种用于为代码元素（类、方法、字段、参数等）添加元数据的机制。这些元数据可以在编译时、类加载时或运行时被读取 ...阅读全文

【日记】9 个发箍只有 2 个能压住头发……（513 字）

正文今天下午实在有些受不了，从正大门外走了出去。抬头望着天空，望着那些悠然自在纯白无暇的云，竟然有些眼睛疼，刺激到想要流泪。我在室内待得太久太久了。似乎很久没有在这种时间段出来过了。下午快下班的时候，有个客户拿了一张远古的转账支票出来，说要转账。我懵了，我们主管也有点懵。转账支票我们起码四五年 ...阅读全文

P1398 [NOI2013] 书法家

思路：来一篇极小常数的 \(O(N^3M)\) 和 \(O(N^2M \log^2 N)\) 的题解，最慢点在 500ms 以下但是为什么还是最劣解。定义 \(dp_{i,j,k,x \in \{0,1,2\},y \in \{0,1,2\}}\) 表示对于正在画的第 \(x\) 个字符，目前正 ...阅读全文

golang对遍历目录操作的优化

一转眼go1.23都快发布了，时间过得真快。不过今天我们把时间倒流回三年半之前，来关注一个在go1.16引入的关于处理目录时的优化。对于go1.16的新变化，大家印象最深的可能是io包的大规模重构，但这个重构实际上还引进了一个优化，这篇文章要说的就是这个优化。本文默认Linux环境，不过这个优 ...阅读全文

线段树题单记录

TODO

P3372 【模板】线段树 1

题目

思路

代码

代码解释

优化原理 && \(lt\)

变量声明

build

pushup

update

pushdown

query

关于 pushup​ 和 pushdown​

P3373 【模板】线段树 2

题目思路

代码

P1198 [JSOI2008] 最大数

思路

代码

[ABC357F] Two Sequence Queries

思路

代码

P1471 方差

思路

Code

[COCI2010-2011#6] STEP

思路

1. 左右两段区间不能衔接

2. 左右两段区间可以相接

Code

贪婪大陆

思路

Code

全村最好的嘤嘤刀

思路

Code

无聊的数列

思路

Code

关于 `pushup` 和 `pushdown`