【数据结构】吉司机线段树(Segment Tree Beats)
吉司机线段树,是由杭州学军中学的吉如一在2016年国集论文当中提出的,解决了区间最值操作和区间历史最值问题。
题目描述
给出一个长度为 \(n\) 的数列 \(A\),同时定义一个辅助数组 \(B\),\(B\) 开始与 \(A\) 完全相同。接下来进行了 \(m\) 次操作,操作有五种类型,按以下格式给出:
1 l r k
:对于所有的 \(i\in[l,r]\),将 \(A_i\) 加上 \(k\)(\(k\) 可以为负数)。2 l r v
:对于所有的 \(i\in[l,r]\),将 \(A_i\) 变成 \(\min(A_i,v)\)。3 l r
:求 \(\sum_{i=l}^{r}A_i\)。4 l r
:对于所有的 \(i\in[l,r]\),求 \(A_i\) 的最大值。5 l r
:对于所有的 \(i\in[l,r]\),求 \(B_i\) 的最大值。
在每一次操作后,我们都进行一次更新,让 \(B_i\gets\max(B_i,A_i)\)。
算法描述
对于1、3、4操作,是最基本的线段树区间加,区间求和、求max的操作,详见P3372 【模板】线段树 1 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn),我们先来解决操作2,我们发现想要动态探测哪些值大于\(v\),并进行min操作十分艰难,因为每个大于\(v\)的数不一样,所以每个大于\(v\)的数要减去的数就不一样,很难统计。
那就让区间内大于\(v\)的数只有一个好了。
对于一个区间,我们记录一个最大值\(maxn\),和一个严格次大值\(sec\)(只有一个值时为\(-inf\)),对于区间取\(min\)操作,我们分为以下三种情况讨论:
1.\(k \geq maxn\),\(k\)在这个区间之内不能更新任何一个值,直接\(return\)
2.\(maxn > k > sec\),\(k\)只能更新\(maxn\),让\(sum -= maxn * cnt\)(区间最大值个数)\(,maxn = k\),因为要下传操作,所以让\(tag2\)(更新\(maxn\)的\(tag\))减去(\(maxn - k\))
3.\(k \leq sec\),分别向\(lc\)和\(rc\)两边递归更新答案。
这样我们就完成了对最小值的更新,同时向两边递归,会不会影响复杂度?事实上这个操作的复杂度仍然是\(O(logn)\)的,证明如下:
(选自吉如一2016国家集训队论文)
代码:
inline void modify_min(int l,int r,int L,int R,int k,int pos)
{
if(k >= t[pos].maxn) return;
if(L <= l && r <= R && k > t[pos].sec)
{
t[pos].sum -= 1ll * t[pos].cnt * (t[pos].maxn - k);
t[pos].tag2 -= t[pos].maxn - k;
t[pos].maxn = k;
return;
}
pushdown(pos,l,r);
int mid = (l + r) >> 1;
if(L <= mid) modify_min(l,mid,L,R,k,pos << 1);
if(R > mid) modify_min(mid + 1,r,L,R,k,pos << 1 | 1);
pushup(pos);
}
现在来看操作5,我们发现,因为修改只有加,一个位置的历史最大值,其实是这个位置原来的值(不一定是原始值,可以看作是pushdown之前的值)加上pushdown之前出现过最大的tag,我们发现在上面的\(modify\_min\)操作中最大值会单独改变,所以区间中的最大值与其他数改变的量(也就是tag)是不一样的,所以我们记录\(tag1\),\(tag2\)代表其他数,最大值的改变量,用\(tag3\),\(tag4\)表示\(tag1\),\(tag2\)在pushdown之前的最大值,这样我们在pushdown的时候就有:
\[history\_max_{pos} = max\{history\_max_{pos},max_{pos} + tag4\} \]每次更新\(k1\)和\(k3\)的时候,都相应的更新\(k2\)和\(k4\)
其实最难的部分在更新标记上,这里我们先讲上传:
和、最大值、历史最大值都可以左右区间直接合并更新,但是对于次大值和最大值个数,我们分类讨论:
1.\(maxn_{lc} == maxn_{rc}\) : 这个时候次大值应当等于两儿子的次大值取\(max\),而最大值计数等于两边相加。
2.\(maxn_{lc} > maxn_{rc}\) : 次大值等于左边的次大值和右边的最大值取\(max\),最大值计数等于左边的\(cnt\)
3.\(maxn_{lc} < maxn_{rc}\) : 次大值等于左边的最大值和右边的次大值取\(max\),最大值计数等于右边的\(cnt\)
这样就完成了上传
inline void pushup(int pos)
{
t[pos].sum = t[pos << 1].sum + t[pos << 1 | 1].sum;
t[pos].maxn = max(t[pos << 1].maxn,t[pos << 1 | 1].maxn);
t[pos].hismax = max(t[pos << 1].hismax,t[pos << 1 | 1].hismax);
if(t[pos << 1].maxn == t[pos << 1 | 1].maxn)
t[pos].sec = max(t[pos << 1].sec,t[pos << 1 | 1].sec),t[pos].cnt = t[pos << 1].cnt + t[pos << 1 | 1].cnt;
else if(t[pos << 1].maxn > t[pos << 1 | 1].maxn)
t[pos].sec = max(t[pos << 1].sec,t[pos << 1 | 1].maxn),t[pos].cnt = t[pos << 1].cnt;
else
t[pos].sec = max(t[pos << 1].maxn,t[pos << 1 | 1].sec),t[pos].cnt = t[pos << 1 | 1].cnt;
}
对于下传,我们也需要分类讨论:
如果全局最大值在左边,那么左边的最大值要按照最大值的方式来更新(即将\(tag2\)和\(tag4\)传下去),否则就将左边不管是不是左边的最大值,都用\(tag1\)和\(tag3\)来更新。
如果全局最大值在右边,同理。
注意这两个条件可以同时成立,不要写else
inline void pushdown(int pos,int l,int r)
{
int mid = (l + r) >> 1;
int mx = max(t[pos << 1].maxn,t[pos << 1 | 1].maxn);
if(mx == t[pos << 1].maxn) change(pos << 1,l,mid,t[pos].tag1,t[pos].tag2,t[pos].tag3,t[pos].tag4);
else change(pos << 1,l,mid,t[pos].tag1,t[pos].tag1,t[pos].tag3,t[pos].tag3);
if(mx == t[pos << 1 | 1].maxn) change(pos << 1 | 1,mid + 1,r,t[pos].tag1,t[pos].tag2,t[pos].tag3,t[pos].tag4);
else change(pos << 1 | 1,mid + 1,r,t[pos].tag1,t[pos].tag1,t[pos].tag3,t[pos].tag3);
t[pos].tag1 = 0;
t[pos].tag2 = 0;
t[pos].tag3 = 0;
t[pos].tag4 = 0;
}
inline void change(int pos,int l,int r,int k1,int k2,int k3,int k4)
{
t[pos].sum += 1ll * (r - l + 1 - t[pos].cnt) * k1 + 1ll * t[pos].cnt * k2;
t[pos].hismax = max(t[pos].hismax,t[pos].maxn + k4);
t[pos].maxn += k2;
if(t[pos].sec != -inf) t[pos].sec += k1;
t[pos].tag4 = max(t[pos].tag4,t[pos].tag2 + k4);
t[pos].tag3 = max(t[pos].tag3,t[pos].tag1 + k3);
t[pos].tag1 += k1;
t[pos].tag2 += k2;
}
注意\(sec\)一行,如果这个节点没有次大值(就是整个区间只有一个值),那么就不能更新值为\(-inf\)的次大值。
区间加时注意要更新全部变量:
inline void modify_add(int l,int r,int L,int R,int k,int pos)
{
if(L <= l && r <= R)
{
t[pos].sum += 1ll * k * (r - l + 1 - t[pos].cnt) + 1ll * k * t[pos].cnt;
t[pos].maxn += k;
t[pos].hismax = max(t[pos].hismax,t[pos].maxn);
if(t[pos].sec != -inf) t[pos].sec += k;
t[pos].tag1 += k;t[pos].tag2 += k;
t[pos].tag3 = max(t[pos].tag3,t[pos].tag1);
t[pos].tag4 = max(t[pos].tag4,t[pos].tag2);
return;
}
pushdown(pos,l,r);
int mid = (l + r) >> 1;
if(L <= mid) modify_add(l,mid,L,R,k,pos << 1);
if(R > mid) modify_add(mid + 1,r,L,R,k,pos << 1 | 1);
pushup(pos);
}
对最大值,和,历史最大值的查询正常查询就好,注意在建树的时候给次大值附上\(-inf\)的初值
Code
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5,inf = 2e9;
struct Node{
long long sum;
int maxn,sec,cnt,hismax,tag1,tag2,tag3,tag4;
}t[N * 4];
int n,m;
inline void pushup(int pos)
{
t[pos].sum = t[pos << 1].sum + t[pos << 1 | 1].sum;
t[pos].maxn = max(t[pos << 1].maxn,t[pos << 1 | 1].maxn);
t[pos].hismax = max(t[pos << 1].hismax,t[pos << 1 | 1].hismax);
if(t[pos << 1].maxn == t[pos << 1 | 1].maxn)
t[pos].sec = max(t[pos << 1].sec,t[pos << 1 | 1].sec),t[pos].cnt = t[pos << 1].cnt + t[pos << 1 | 1].cnt;
else if(t[pos << 1].maxn > t[pos << 1 | 1].maxn)
t[pos].sec = max(t[pos << 1].sec,t[pos << 1 | 1].maxn),t[pos].cnt = t[pos << 1].cnt;
else
t[pos].sec = max(t[pos << 1].maxn,t[pos << 1 | 1].sec),t[pos].cnt = t[pos << 1 | 1].cnt;
}
inline void change(int pos,int l,int r,int k1,int k2,int k3,int k4)
{
t[pos].sum += 1ll * (r - l + 1 - t[pos].cnt) * k1 + 1ll * t[pos].cnt * k2;
t[pos].hismax = max(t[pos].hismax,t[pos].maxn + k4);
t[pos].maxn += k2;
if(t[pos].sec != -inf) t[pos].sec += k1;
t[pos].tag4 = max(t[pos].tag4,t[pos].tag2 + k4);
t[pos].tag3 = max(t[pos].tag3,t[pos].tag1 + k3);
t[pos].tag1 += k1;
t[pos].tag2 += k2;
}
inline void pushdown(int pos,int l,int r)
{
int mid = (l + r) >> 1;
int mx = max(t[pos << 1].maxn,t[pos << 1 | 1].maxn);
if(mx == t[pos << 1].maxn) change(pos << 1,l,mid,t[pos].tag1,t[pos].tag2,t[pos].tag3,t[pos].tag4);
else change(pos << 1,l,mid,t[pos].tag1,t[pos].tag1,t[pos].tag3,t[pos].tag3);
if(mx == t[pos << 1 | 1].maxn) change(pos << 1 | 1,mid + 1,r,t[pos].tag1,t[pos].tag2,t[pos].tag3,t[pos].tag4);
else change(pos << 1 | 1,mid + 1,r,t[pos].tag1,t[pos].tag1,t[pos].tag3,t[pos].tag3);
t[pos].tag1 = 0;
t[pos].tag2 = 0;
t[pos].tag3 = 0;
t[pos].tag4 = 0;
}
inline void build(int l,int r,int pos)
{
if(l == r)
{
cin>>t[pos].sum;
t[pos].maxn = t[pos].sum;
t[pos].hismax = t[pos].maxn;
t[pos].sec = -inf;
t[pos].tag1 = t[pos].tag2 = t[pos].tag3 = t[pos].tag4 = 0;
t[pos].cnt = 1;
return;
}
int mid = (l + r) >> 1;
build(l,mid,pos << 1);
build(mid + 1,r,pos << 1 | 1);
pushup(pos);
}
inline void modify_add(int l,int r,int L,int R,int k,int pos)
{
if(L <= l && r <= R)
{
t[pos].sum += 1ll * k * (r - l + 1 - t[pos].cnt) + 1ll * k * t[pos].cnt;
t[pos].maxn += k;
t[pos].hismax = max(t[pos].hismax,t[pos].maxn);
if(t[pos].sec != -inf) t[pos].sec += k;
t[pos].tag1 += k;t[pos].tag2 += k;
t[pos].tag3 = max(t[pos].tag3,t[pos].tag1);
t[pos].tag4 = max(t[pos].tag4,t[pos].tag2);
return;
}
pushdown(pos,l,r);
int mid = (l + r) >> 1;
if(L <= mid) modify_add(l,mid,L,R,k,pos << 1);
if(R > mid) modify_add(mid + 1,r,L,R,k,pos << 1 | 1);
pushup(pos);
}
inline void modify_min(int l,int r,int L,int R,int k,int pos)
{
if(k >= t[pos].maxn) return;
if(L <= l && r <= R && k > t[pos].sec)
{
t[pos].sum -= 1ll * t[pos].cnt * (t[pos].maxn - k);
t[pos].tag2 -= t[pos].maxn - k;
t[pos].maxn = k;
return;
}
pushdown(pos,l,r);
int mid = (l + r) >> 1;
if(L <= mid) modify_min(l,mid,L,R,k,pos << 1);
if(R > mid) modify_min(mid + 1,r,L,R,k,pos << 1 | 1);
pushup(pos);
}
inline long long query_sum(int l,int r,int L,int R,int pos)
{
if(L <= l && r <= R) return t[pos].sum;
pushdown(pos,l,r);
int mid = (l + r) >> 1;
long long ret = 0;
if(L <= mid) ret += query_sum(l,mid,L,R,pos << 1);
if(R > mid) ret += query_sum(mid + 1,r,L,R,pos << 1 | 1);
pushup(pos);
return ret;
}
inline int query_max(int l,int r,int L,int R,int pos)
{
if(L <= l && r <= R) return t[pos].maxn;
pushdown(pos,l,r);
int mid = (l + r) >> 1,ret = -inf;
if(L <= mid) ret = max(ret,query_max(l,mid,L,R,pos << 1));
if(R > mid) ret = max(ret,query_max(mid + 1,r,L,R,pos << 1 | 1));
pushup(pos);
return ret;
}
inline int query_hismax(int l,int r,int L,int R,int pos)
{
if(L <= l && r <= R) return t[pos].hismax;
pushdown(pos,l,r);
int mid = (l + r) >> 1,ret = -inf;
if(L <= mid) ret = max(ret,query_hismax(l,mid,L,R,pos << 1));
if(R > mid) ret = max(ret,query_hismax(mid + 1,r,L,R,pos << 1 | 1));
pushup(pos);
return ret;
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m;
build(1,n,1);
int op,l,r,k;
for(int i = 1;i <= m;i++)
{
cin>>op>>l>>r;
switch(op)
{
case 1:
cin>>k;
modify_add(1,n,l,r,k,1);
break;
case 2:
cin>>k;
modify_min(1,n,l,r,k,1);
break;
case 3:
cout<<query_sum(1,n,l,r,1)<<endl;
break;
case 4:
cout<<query_max(1,n,l,r,1)<<endl;
break;
case 5:
cout<<query_hismax(1,n,l,r,1)<<endl;
break;
}
}
return 0;
}
"所有的真理,都是符合客观事实的,更是顺着逻辑的。"
标签:int,max,线段,pos,mid,司机,maxn,数据结构,最大值 From: https://www.cnblogs.com/fanghaoyu801212/p/17447315.html