题意：

已知\(n\)个数字，进行以下操作：

\(1.\)区间\([L,R]\) 赋值为\(x\)
\(2.\)区间\([L,R]\) 赋值为\(max(a[i] + x, 0)\)
\(3.\)区间\([L,R]\) 询问\(0\)个数

已知初始值\(\geq 0\)，\(x\geq0\)。

思路：

吉司机线段树。

操作\(1\)可以直接打覆盖标记。

操作\(2\)可以分为两步：区间加\(x\)，然后取区间\(max(a[i],0)\)。

操作\(3\)只要维护最小值的个数，因为不管怎么操作最后的值都\(\geq0\)，然后查询的时候判最小值是不是\(0\)。

注意覆盖的时候，要把次小值初始化为\(INF\)。

代码：

#include<map>

#include<set>

#include<queue>

#include<cmath>

#include<stack>

#include<ctime>

#include<vector>

#include<cstdio>

#include<string>

#include<cstring>

#include<sstream>

#include<iostream>

#include<algorithm>

typedef long long ll;

typedef unsigned long long ull;

using namespace std;

const int maxn = 5e5 + 5;

const int MAXM = 3e6;

const ll MOD = 998244353;

const ull seed = 131;

const ll INF = 1e16;

#define lson (rt << 1)

#define rson (rt << 1 | 1)

int a[maxn];

ll Min[maxn << 2], sMin[maxn << 2], add[maxn << 2], cov[maxn << 2];

int Minlen[maxn << 2];

inline void pushup(int rt){

    if(Min[lson] > Min[rson]){

        Min[rt] = Min[rson];

        Minlen[rt] = Minlen[rson];

        sMin[rt] = min(sMin[rson], Min[lson]);

    }

    if(Min[lson] < Min[rson]){

        Min[rt] = Min[lson];

        Minlen[rt] = Minlen[lson];

        sMin[rt] = min(sMin[lson], Min[rson]);

    }

    if(Min[lson] == Min[rson]){

        Min[rt] = Min[lson];

        Minlen[rt] = Minlen[lson] + Minlen[rson];

        sMin[rt] = min(sMin[lson], sMin[rson]);

    }

}

inline void pushdown(int rt, int l, int r){

    int m = (l + r) >> 1;

    if(cov[rt] != -1){

        Min[lson] = Min[rson] = cov[rt];

        sMin[lson] = sMin[rson] = INF;	//careful！！！！

        cov[lson] = cov[rson] = cov[rt];

        add[lson] = add[rson] = 0;

        Minlen[lson] = m - l + 1;

        Minlen[rson] = r - m;

        cov[rt] = -1;

    }

    if(add[rt]){

        Min[lson] += add[rt], sMin[lson] += add[rt];

        Min[rson] += add[rt], sMin[rson] += add[rt];

        add[lson] += add[rt], add[rson] += add[rt];

        add[rt] = 0;

    }

    if(Min[lson] < Min[rt]){

        if(sMin[lson] == Min[lson]) sMin[lson] = Min[rt];

        Min[lson] = Min[rt];

    }

    if(Min[rson] < Min[rt]){

        if(sMin[rson] == Min[rson]) sMin[rson] = Min[rt];

        Min[rson] = Min[rt];

    }

}

void build(int l, int r, int rt){

    cov[rt] = -1, add[rt] = 0;

    if(l == r){

        Min[rt] = a[l];

        sMin[rt] = INF;

        Minlen[rt] = 1;

        return;

    }

    int m = (l + r) >> 1;

    build(l, m, lson);

    build(m + 1, r, rson);

    pushup(rt);

}

void cover(int L, int R, int l, int r, ll v, int rt){

    if(L <= l && R >= r){

        cov[rt] = v;

        add[rt] = 0;

        Min[rt] = v;

        sMin[rt] = INF;	//careful！！！！

        Minlen[rt] = r - l + 1;

        return;

    }

    pushdown(rt, l, r);

    int m = (l + r) >> 1;

    if(L <= m)

        cover(L, R, l, m, v, lson);

    if(R > m)

        cover(L, R, m + 1, r, v, rson);

    pushup(rt);

}

void update(int L, int R, int l, int r, ll v, int rt){

    if(L <= l && R >= r){

        Min[rt] += v;

        sMin[rt] += v;

        add[rt] += v;

        return;

    }

    pushdown(rt, l, r);

    int m = (l + r) >> 1;

    if(L <= m)

        update(L, R, l, m, v, lson);

    if(R > m)

        update(L, R, m + 1, r, v, rson);

    pushup(rt);

}

void Less(int L, int R, int l, int r, ll v, int rt){

    if(Min[rt] >= v) return;

    if(L <= l && R >= r && sMin[rt] > v){   //>保证Minlen不变

        Min[rt] = v;

        return;

    }

    pushdown(rt, l, r);

    int m = (l + r) >> 1;

    if(L <= m)

        Less(L, R, l, m, v, lson);

    if(R > m)

        Less(L, R, m + 1, r, v, rson);

    pushup(rt);

}

int querySum(int L, int R, int l, int r, int rt){

    if(L <= l && R >= r){

        return Min[rt] == 0? Minlen[rt] : 0;

    }

    pushdown(rt, l, r);

    int m = (l + r) >> 1;

    int ret = 0;

    if(L <= m)

        ret += querySum(L, R, l, m, lson);

    if(R > m)

        ret += querySum(L, R, m + 1, r, rson);

    return ret;

}

inline bool read(int &num){

    char in;

    bool IsN=false;

    in = getchar();

    if(in == EOF) return false;

    while(in != '-' && (in < '0' || in > '9')) in = getchar();

    if(in == '-'){ IsN = true; num = 0;}

    else num = in - '0';

    while(in = getchar(),in >= '0' && in <= '9'){

            num *= 10, num += in-'0';

    }

    if(IsN) num = -num;

    return true;

}

int main(){

    int n, m;

    read(n), read(m);

    for(int i = 1; i <= n; i++) read(a[i]);

    build(1, n, 1);

    while(m--){

        int l, r, x, op;

        read(op), read(l), read(r);

        if(op < 3) read(x);

        if(op == 1) cover(l, r, 1, n, x, 1);

        else if(op == 2) update(l, r, 1, n, x, 1), Less(l, r, 1, n, 0, 1);

        else printf("%d\n", querySum(l, r, 1, n, 1));

    }

    return 0;

}

巴特西

bzoj4355 Play with sequence（吉司机线段树）题解

题意：

思路：

代码：

最新文章

热门文章