BZOJ 4355: Play with sequence 吉司机线段树
Description
维护一个长度为N的序列a，现在有三种操作：
1）给出参数U,V,C，将a[U],a[U+1],...,a[V-1],a[V]都赋值为C。
2）给出参数U,V,C，对于区间[U,V]里的每个数i，将a[i]赋值为max(a[i]+C,0)。
3）给出参数U,V，输出a[U],a[U+1],...,a[V-1],a[V]里值为0的数字个数。
Input
第一行包含两个正整数N,M(1<=N,M<=300000)，分别表示序列长度和操作个数。
第二行包含N个整数，其中第i个数表示a[i](0<=a[i]<=10^9)，描述序列的初始状态。
接下来M行描述M个操作，保证1<=U<=V<=N，对于操作1，0<=C<=10^9，对于操作2，|C|<=10^9。
Output
输出若干行，每行一个整数，依次回答每个操作3的问题。
吉司机线段树.
注意一定要 pushdown
这个是基于势能分析的线段树，相对来说比较好写，好理解.
然后如果有多个标记的话就需要注意标记下传的顺序.
假设有 add, modify, 取 max，这三种标记.
显然，如果只有前两个的话应该是 val[x]=modify+add，然后如果有取 max 的话应该在这两个标记下传之后进行.
我们考虑，什么时候一个点同时有 3 种标记 ? 一定是先有 set，再有 add，max 只可能是最后加的，所以要把 max 放在最后下传.
code:
#include <cstdio>
#include <algorithm>
#include <cstring>
#define ll long long
#define lson x<<1
#define rson x<<1|1
#define N 300007
#define I(s) freopen(s".in","r",stdin)
#define O(s) freopen(s".out","w",stdout)
#define setIO(s) I(s),O(s)
using namespace std;
const ll inf=1ll<<60;
int n,m;
int mi[N<<2],len[N<<2];
ll add[N<<2],tag[N<<2],mn[N<<2],sn[N<<2];
void pushup(int x)
{
if(mn[lson]<mn[rson]) mn[x]=mn[lson],mi[x]=mi[lson],sn[x]=min(sn[lson],mn[rson]);
if(mn[rson]<mn[lson]) mn[x]=mn[rson],mi[x]=mi[rson],sn[x]=min(sn[rson],mn[lson]);
if(mn[lson]==mn[rson]) mn[x]=mn[lson],mi[x]=mi[lson]+mi[rson],sn[x]=min(sn[lson],sn[rson]);
}
void build(int l,int r,int x)
{
add[x]=0,tag[x]=inf,len[x]=r-l+1;
if(l==r)
{
scanf("%lld",&mn[x]),sn[x]=inf,mi[x]=1;
return;
}
int mid=(l+r)>>1;
build(l,mid,lson),build(mid+1,r,rson);
pushup(x);
}
void mark_tag(int x,ll v)
{
add[x]=0,tag[x]=v,mn[x]=v,sn[x]=inf,mi[x]=len[x];
}
void mark_add(int x,ll v)
{
add[x]+=v,mn[x]+=v,sn[x]+=v;
}
void pushdown(int x)
{
if(tag[x]!=inf)
{
mark_tag(lson,tag[x]);
mark_tag(rson,tag[x]);
}
if(add[x])
{
mark_add(lson,add[x]);
mark_add(rson,add[x]);
}
mn[lson]=max(mn[lson],mn[x]);
mn[rson]=max(mn[rson],mn[x]);
add[x]=0,tag[x]=inf;
}
void modify(int l,int r,int x,int L,int R,ll v)
{
if(l>=L&&r<=R)
{
mark_tag(x,v);
return;
}
pushdown(x);
int mid=(l+r)>>1;
if(L<=mid) modify(l,mid,lson,L,R,v);
if(R>mid) modify(mid+1,r,rson,L,R,v);
pushup(x);
}
void addv(int l,int r,int x,int L,int R,ll v)
{
if(l>=L&&r<=R)
{
mark_add(x,v);
return;
}
pushdown(x);
int mid=(l+r)>>1;
if(L<=mid) addv(l,mid,lson,L,R,v);
if(R>mid) addv(mid+1,r,rson,L,R,v);
pushup(x);
}
void getmax(int l,int r,int x,int L,int R,ll v)
{
if(mn[x]>=v) return;
if(l>=L&&r<=R&&sn[x]>v)
{
mn[x]=v;
return;
}
pushdown(x);
int mid=(l+r)>>1;
if(L<=mid) getmax(l,mid,lson,L,R,v);
if(R>mid) getmax(mid+1,r,rson,L,R,v);
pushup(x);
}
int query(int l,int r,int x,int L,int R)
{
if(l>=L&&r<=R) return mn[x]?0:mi[x];
pushdown(x);
int mid=(l+r)>>1,re=0;
if(L<=mid) re+=query(l,mid,lson,L,R);
if(R>mid) re+=query(mid+1,r,rson,L,R);
return re;
}
int main()
{
// setIO("input");
scanf("%d%d",&n,&m);
build(1,n,1);
for(int i=1;i<=m;++i)
{
ll z;
int op,l,r;
scanf("%d%d%d",&op,&l,&r);
if(op==1) scanf("%lld",&z),modify(1,n,1,l,r,z);
if(op==2) scanf("%lld",&z),addv(1,n,1,l,r,z),getmax(1,n,1,l,r,0ll);
if(op==3) printf("%d
",query(1,n,1,l,r));
}
return 0;
}