社区讨论

调了两天3小时细节不行了

AT_abc441_g[ABC441G] Takoyaki and Flip参与者 3已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@mknw9ze8
此快照首次捕获于
2026/01/21 18:43
4 周前
此快照最后确认于
2026/02/11 02:29
上周
查看原帖
第一次做蓝题线段树,并打算以后先去水水板子题吧。这辈子不想再被线段树卡题了。
样例三成这样:

就这ai打的没我好,一直不知道哪里的问题。没时间帮调的话给个可能的方向吧,没见过这种情况。都是querymaxquerymax怎么有的对有的不对。
CPP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N  = 2e5 + 10;
#define tm tr[p].tmax
#define cz tr[p].cntz
#define cf tr[p].cntf
#define ad tr[p].add
#define rp tr[p].rep

//定义线段树节点
struct tree {
    ll tmax;
    ll cntz;
    ll cntf;
    ll add;
    ll rep;
} tr[N << 2];

int n, Q;

int ls(int p) {return p << 1;}
int rs(int p) {return p << 1 | 1;}

void push_up(int p){
    // 合并左右孩子的tmax/cntz/cntf
    tm = max(tr[ls(p)].tmax, tr[rs(p)].tmax);
    cz = tr[ls(p)].cntz + tr[rs(p)].cntz;
    cf = tr[ls(p)].cntf + tr[rs(p)].cntf;
}

void build(int p, int pl, int pr){
    ad = rp = 0;
    if(pl == pr){
        tm = 0;//初始章鱼烧数量0
        cz = 1;//初始正面朝上数量1
        cf = 0;//初始反面朝上数量0
        return;
    }
    int mid = pl + pr >> 1;
    build(ls(p), pl, mid);
    build(rs(p), mid + 1, pr);
    push_up(p);
}

void addtag(int p, int add_, int rep_){
    if(rep_ == 0){//没有区间翻转操作
        if(cz != 0){//至少有一个盘子是正面朝上的
            tr[p] = {
                tm + add_,
                cz, 
                cf, 
                ad + add_,
                rp + rep_
            };
        }else{
            tr[p] = {
                0,
                0, 
                cf,
                ad + add_,
                rp
            };
        }
    }else{//区间反转会覆盖掉区间加
        if(rep_ & 1){
            if(cf == 0){
                tr[p] = {
                    0,
                    cf,
                    cz,
                    add_,
                    rp + rep_
                };
            }else{
                tr[p] = {
                    add_,
                    cf,
                    cz,
                    add_,
                    rp + rep_
                };
            }
        }
    }
}

void push_down(int p){
    if(ad | rp){
        //下传标记到左右
        addtag(ls(p), ad, rp);
        addtag(rs(p), ad, rp);
        ad = rp = 0;
    }
}

void update(int L, int R, int p, int pl, int pr, int add_, int rep_){
    if(L <= pl && R >= pr){
        addtag(p, add_, rep_);
        return;
    }
    push_down(p);
    int mid = pl + pr >> 1;
    if(L <= mid){
        update(L, R, ls(p), pl, mid, add_, rep_);
    }
    if(R > mid){
        update(L, R, rs(p), mid + 1, pr, add_, rep_);
    }
    push_up(p);
}

ll querymax(int L, int R, int p, int pl, int pr){
    if(cz == 0) return 0;
    if(L <= pl && R >= pr){
        return tm;
    }
    push_down(p);
    int mid = pl + pr >> 1;
    ll res = -1;
    if(L <= mid){
        res = querymax(L, R, ls(p), pl, mid);
    }
    if(R > mid){
        res = max(res, querymax(L, R, rs(p), mid + 1, pr));
    }
    return res;
}

int main(){
    scanf("%d%d", &n, &Q);
    build(1, 1, n);
    while(Q --){
        int t;
        scanf("%d", &t);
        if(t == 1){
            int l, r, x;
            scanf("%d%d%d", &l, &r, &x);
            update(l, r, 1, 1, n, x, 0);
        }else if(t == 2){
            int l, r;
            scanf("%d%d", &l, &r);
            update(l, r, 1, 1, n, 0, 1);
        }else{
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%lld\n", querymax(l, r, 1, 1, n));
        }
    }
    return 0;
}

回复

6 条回复,欢迎继续交流。

正在加载回复...