线段树题单记录

线段树题单记录

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

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

TODO

• 【模板】线段树 1
• 【模板】线段树 2
• [JSOI2008] 最大数
• [ABC357F] Two Sequence Queries
• 方差
• [COCI2010-2011#6] STEP
• 贪婪大陆
• 全村最好的嘤嘤刀
• 无聊的数列
• XOR 的艺术
• [TJOI2018] 数学计算
• * [ ] [HNOI2012] 永无乡

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

P3372 【模板】线段树 1

题目

Link

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

思路

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

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

​

​

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

废话

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

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

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

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

那还要珂朵莉树干什么

好吧它们各有优劣。

虽然珂朵莉树快

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

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

代码

<code>#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] 其实就一个点（图中蓝色的点）。

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

那么它为什么没有 pushup​ 呢？

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

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

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

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

还是这张图。

​

​

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

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

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

然后我们会发现，它的值不是最新的，我们要把 [1,3] 区间的懒标记进行 <code>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

4

1

1

2

6

总共 \(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

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

综上，我们可以得出：

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

1. 左右端点 这个不用说了吧
2. 区间最值
3. 区间左侧字母
4. 区间右侧字母
5. 区间从左侧开始最值
6. 区间从右侧开始最值

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

Code

<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

<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

因为这道题从题目到题解都充满了三蹦子的气息

首篇题解的奇妙命名

当然这道题就算你没有玩过崩坏 \(3\) 也能写废话。

咋一看，这就是道板子题啊！

不就是多一个绯狱丸的路标吗。

然后细看，发现八重樱的行动准则：先打绯狱丸再去空地。

为了痛击绯狱丸为民除害而不顾自身利益。

也就是说，去绯狱丸出现的地方优先级 \(>\) 去嘤嘤嘤值最高的地方的优先级。

所以不要想多了。

我用的方法是线段树维护最值，树状数组维护绯狱丸出现位置。

那么线段树维护区间最值不用说了吧，很简单的。

不会的话可以看上面的 P1198 [JSOI2008] 最大数。

树状数组维护也不用说了吧，更简单。

不会的话可以看我上个笔记里没有这样的题。

用树状数组维护的话就是把出现绯狱丸的坐标加入到树状数组中，然后，如果要查有没有的话，只要求 \(sum(r) - sum(l-1)\) 就行了。如果它不为零，那么它就是绯狱丸的坐标，否则没有绯狱丸。

那么可能会有人有疑问了，如果多只绯狱丸叠加在一个区间内呢反正我有？如果你有，请看题目最后一行：

​对于事件 $2$ ，题目保证每个事件中最多出现 $1$ 只绯狱丸。如果出现多个最大值，在每次比较时，请选择靠右的（std 默认的）。​

所以说，不会出现一个区间内有多只绯狱丸这种情况发生的。

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;}code>

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;

}