[BZOJ4355]Play with sequence 吉司机线段树

定义二元组标记(p,c)表示对区间内元素x
x=max(x+p,c)
标记支持区间加法
tag1<p1,c1>+tag2<p2,c2>=tag<p1+p2,max(c1+p2,c2)>
那么标记就可以下推啦
覆盖操作可以表示成 tag<−INF,c>
加法操作可以表示成 tag<p,0>

定义势能函数表示该区间元素不同的个数
区间维护最大值、最大值个数、次大值、和答案（即零的个数）
若区间更新后，新的最大值都是由旧的最大值得来的，那么直接修改即可
否则，递归下去修改，区间势能降低

写起来细节很多

//线段树维护区间最小值、最小值个数、次小值、答案
//标记为二元组Tag<p,c>表示对元素x = max{x+p,c}
#include <iostream>
#include <cstdio>
#define INF (1LL<<61)
#define N 600050
#define mid ((l+r)>>1)
#define ls l,mid,t<<1
#define rs mid+1,r,t<<1^1
using namespace std;
typedef long long LL;
int n,m,a[N];
struct Tag{
LL p,c;
Tag operator+=(Tag cur) {
Tag tmp;
tmp.p = max(cur.p + p , -INF);
tmp.c = max(c + cur.p , cur.c);
p = tmp.p , c = tmp.c;
}
}ag[4*N],now;
struct Node{
LL mx; int tot; LL se; int ans;
}tr[4*N],id;
Node operator +(Node p1,Node p2) {
Node tmp = id;
tmp.ans = p1.ans + p2.ans;
if (p1.mx == p2.mx) {
tmp.mx = p1.mx;
tmp.tot = p1.tot + p2.tot;
tmp.se = min(p1.se,p2.se);
} else {
if (p1.mx > p2.mx) swap(p1,p2);
tmp.mx = p1.mx;
tmp.tot = p1.tot;
tmp.se = min(p1.se,p2.mx);
}
return tmp;
}
Node build(int l,int r,int t) {
ag[t] = (Tag){0LL,-INF};
return l == r ? tr[t] = (Node){a[l],1,INF,a[l]==0} : tr[t] = build(ls) + build(rs);
}
void push_down(int );
void color(Tag tag,int t) {
LL a = max( max(tr[t].mx+tag.p , tag.c) , 0LL);
LL b = max( max(tr[t].se+tag.p , tag.c) , 0LL);
b = min(b,INF);
if (tr[t].se == INF) b = INF;
//
if (a >= tr[t].mx) {
//
tr[t].mx = a;
//
tr[t].se = b;
//
if (a == 0) tr[t].ans = tr[t].tot; else tr[t].ans = 0;
//
return ;
//
}
if (a >= b) {
push_down(t);
tr[t] = tr[t<<1] + tr[t<<1^1];
} else {
tr[t].mx = a;
tr[t].se = b;
if (a == 0) tr[t].ans = tr[t].tot; else tr[t].ans = 0;
}
}
void push_down(int t) {
ag[t<<1] += ag[t]; color(ag[t],t<<1);
ag[t<<1^1] += ag[t]; color(ag[t],t<<1^1);
ag[t] = (Tag){0,-INF};
}
int ll,rr;
void update(int l,int r,int t) {
if (l > rr || r < ll) return ;
if (l >= ll && r <= rr) {
ag[t] += now;
color(now,t);
return ;
}
push_down(t);
update(ls);
update(rs);
tr[t] = tr[t<<1] + tr[t<<1^1];
return ;
}
int query(int l,int r,int t) {
if (l > rr || r < ll) return 0;
if (l >= ll && r <= rr) return tr[t].ans;
push_down(t);
int cur = query(ls) + query(rs);
tr[t] = tr[t<<1] + tr[t<<1^1];
return cur;
}
int main() {
//
freopen("1.in","r",stdin);
scanf("%d%d",&n,&m);
for (int _=1;_<=n;_++) scanf("%d",&a[_]);
build(1,n,1);
while (m--) {
int cmd=0,c=0; scanf("%d",&cmd);
if (cmd == 1) {
scanf("%d%d%d",&ll,&rr,&c);
now = (Tag){-INF,c};
update(1,n,1);
}
if (cmd == 2) {
scanf("%d%d%d",&ll,&rr,&c);
now = (Tag){c,0};
update(1,n,1);
}
if (cmd == 3) {
scanf("%d%d",&ll,&rr);
int ans = query(1,n,1);
printf("%dn",ans);
}
}
return 0;
} 

最后

以上就是含蓄钥匙为你收集整理的[BZOJ4355]Play with sequence 吉司机线段树的全部内容，希望文章能够帮你解决[BZOJ4355]Play with sequence 吉司机线段树所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。