欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

BZOJ4355: Play with sequence(吉司机线段树)

程序员文章站 2024-01-25 08:58:16
题意 题目链接 Sol 传说中的吉司机线段树??感觉和BZOJ冒险那题差不多,就是强行剪枝。。。 这题最坑的地方在于对于操作1,$C >= 0$, 操作2中需要对0取max,$a[i] >= 0$,这不就是统计最小值出现的次数么?? 按照套路 维护好区间赋值标记 / 区间加法标记 / 区间max标记 ......

题意

题目链接

sol

传说中的吉司机线段树??感觉和bzoj冒险那题差不多,就是强行剪枝。。。

这题最坑的地方在于对于操作1,$c >= 0$, 操作2中需要对0取max,$a[i] >= 0$,这不就是统计最小值出现的次数么??

按照套路

维护好区间赋值标记 / 区间加法标记 / 区间max标记 / 区间最小值 / 区间最小值出现的次数 / 区间次小值

对于第二个操作就拆成区间加 和 区间max

区间max是一个很神奇的操作

设当前加入的数为val

若val>=mn,那该操作对该区间无影响

若se < val < mn,该操作只会对次小值产生影响,因为对其他的标记均不会产生影响,因此打一个额外的标记即可

否则暴力递归

时间复杂度:$o(n log^2n)$??

另外这东西可以做区间加 / 查询历史版本,前者维护一下标记就行,,后者嘛,,,等长大了再研究吧qwq

 

#include<cstdio>
#include<algorithm>
#define ll long long 
//#define int long long 
using namespace std;
const int maxn = 3 * 1e5 + 10;
const ll inf = 1e10 +10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
#define ls k << 1
#define rs k << 1 | 1
int n, q;
int a[maxn];
struct node {
    int l, r, siz, cnt;
    ll mx, add, mn, se, cov;
}t[maxn << 2];
void update(int k) {
    //t[k].mn = min(t[ls].mn, t[rs].mn);
    if(t[ls].mn < t[rs].mn)      t[k].cnt = t[ls].cnt, t[k].mn = t[ls].mn, t[k].se = min(t[rs].mn, t[ls].se);
    else if(t[ls].mn > t[rs].mn) t[k].cnt = t[rs].cnt, t[k].mn = t[rs].mn, t[k].se = min(t[ls].mn, t[rs].se);
    else              t[k].cnt = t[ls].cnt + t[rs].cnt, t[k].mn = t[ls].mn, t[k].se = min(t[ls].se, t[rs].se);
}
void memp(int k, ll val) {
    t[k].cov = val;
    t[k].cnt = t[k].siz;
    t[k].se = inf;
    t[k].mx = -inf;
    t[k].add = 0;
    t[k].mn = val;
}
void addp(int k, ll val) {
    if(t[k].se != inf)  t[k].se += val;
    if(t[k].mx != -inf) t[k].mx += val;
    t[k].mn += val;
    t[k].add += val;
}
void maxp(int k, ll val) {
    t[k].mn = max(t[k].mn, val);//
    t[k].mx = max(t[k].mx, val);
}
void pushdown(int k) {
    if(t[k].cov != inf) memp(ls, t[k].cov), memp(rs, t[k].cov), t[k].cov = inf;
    if(t[k].add) addp(ls, t[k].add), addp(rs, t[k].add), t[k].add = 0;
    if(t[k].mx != -inf) maxp(ls, t[k].mx), maxp(rs, t[k].mx), t[k].mx = -inf;
}
void build(int k, int ll, int rr) {
    t[k] = (node) {ll, rr, rr - ll + 1, 0, -inf, 0, 0, inf, inf};
    if(ll == rr) {
        t[k].mn = a[ll]; t[k].cnt = 1;
        return ;
    }
    int mid = t[k].l + t[k].r >> 1;
    build(ls, ll, mid); build(rs, mid + 1, rr);
    update(k);
}
void intmem(int k, int ll, int rr, ll val) {
    if(ll <= t[k].l && t[k].r <= rr) {memp(k, val); return ;}
    pushdown(k);
    int mid = t[k].l + t[k].r >> 1;
    if(ll <= mid) intmem(ls, ll, rr, val); 
    if(rr >  mid) intmem(rs, ll, rr, val);
    update(k);
}
void intadd(int k, int ll, int rr, ll val) {
    if(ll <= t[k].l && t[k].r <= rr) {addp(k, val); return ;}
    pushdown(k);
    int mid = t[k].l + t[k].r >> 1;
    if(ll <= mid) intadd(ls, ll, rr, val);
    if(rr >  mid) intadd(rs, ll, rr, val);
    update(k);
}
void intmax(int k, int ll, int rr, ll val) {
    if(val <= t[k].mn) return ;
    if(ll <= t[k].l && t[k].r <= rr && t[k].se > val) {//tag
        maxp(k, val); 
        return ;
    }
    int mid = t[k].l + t[k].r >> 1;
    pushdown(k);
    if(ll <= mid) intmax(ls, ll, rr, val); 
    if(rr >  mid) intmax(rs, ll, rr, val);
    update(k);
}
ll query(int k, int ll, int rr) {
    // int ans = 0;
    if(ll <= t[k].l && t[k].r <= rr) 
        return (t[k].mn == 0 ? t[k].cnt : 0);
    pushdown(k);
    int mid = t[k].l + t[k].r >> 1;
    if(ll > mid) return query(rs, ll, rr);
    else if(rr <= mid) return query(ls, ll, rr);
    else return query(ls, ll, rr) + query(rs, ll, rr);
}
main() {
    // freopen("4355.in", "r", stdin);
    // freopen("4355.out", "w", stdout);
    n = read(); q = read();
    for(int i = 1; i <= n; i++) a[i] = read();
    build(1, 1, n);
    while(q--) {
        int opt = read(), l = read(), r = read(), val;
        if(opt == 3) printf("%d\n", query(1, l, r));
        else {
            val = read();
            if(opt == 1) intmem(1, l, r, val);
            else {
                intadd(1, l, r, val);
                intmax(1, l, r, 0);
            }
        }
    }
    return 0;
}