社区讨论
调了两天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打的没我好,一直不知道哪里的问题。没时间帮调的话给个可能的方向吧,没见过这种情况。都是怎么有的对有的不对。
CPP样例三成这样:

就这ai打的没我好,一直不知道哪里的问题。没时间帮调的话给个可能的方向吧,没见过这种情况。都是怎么有的对有的不对。
#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 条回复,欢迎继续交流。
正在加载回复...