[BZOJ 4355] Play with sequence 길 기사 선분 트 리

정의 이원 그룹 태그 (p, c) 는 구간 내 요소 x x = max (x + p, c) 태그 지원 구간 덧셈 tag1 < p1, c1 > + tag2 < p2, c2 > = tag < p1 + p2, max (c1 + p2, c2) > 를 표시 합 니 다.
정의 위치 에너지 함 수 는 이 구간 요소 가 서로 다른 개수 구간 의 유지 최대 치, 최대 치 개수, 차 대 치, 그리고 답 (즉 0 의 개수) 을 나타 낸다. 구간 이 업데이트 되면 새로운 최대 치 는 모두 오래된 최대 치 에 의 해 올 수 있다. 그러면 직접 수정 할 수 있 는 지 없 는 지 를 재 귀적 으로 수정 하면 구간 이 낮 아 질 수 있다.
디 테 일이 많아 요.

//          、     、   、  
//      Tag
     x = max{x+p,c} 
#include 
#include 
#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("%d
",ans);
        }
    }
    return 0;
}