D0000 @ 2024-07-15 22:20:06
众所周知，线段树单点修改时，如果 l==r 那么就不能往下递归了。但是在本题下放标记的过程中，如果你把类似于 if(l==r)return; 这样的语句删掉，仍然能 A。
by lin_ziran @ 2024-07-17 08:44:03
@D0000
请问你说的是这里被注释的一行代码吗：
#define ls id << 1
#define rs id << 1 | 1
void Change_Tag(int id, int l, int r, int s) {//s 是加入的线段编号
int &t = tag[id];
int mid = l + r >> 1;
if (cmp(s, t, mid) == s) swap(s, t);
// if (l == r) return;
if (cmp(s, t, l) == s) Change_Tag(ls, l, mid, s);
else if (cmp(s, t, r) == s) Change_Tag(rs, mid + 1, r, s);
}我认为当 l 等于 r 时，不用加这一行，因为此时已经不会再向下递归了。
因为当 l 等于 r 时，mid 的值也与 l 和 r 相等，所以求 cmp(s, t, mid) 与求 cmp(s, t, l) 和求 cmp(s, t, r) 等价。
又因为 if (cmp(s, t, mid) == s) swap(s, t);，且 s != t，所以后面的 cmp(s, t, l) 和 cmp(s, t, r) 的返回值应该都等于 t，不等于 s。
所以当 l 等于 r 时，不会再往下递归了。
（第一次回复，若有错误欢迎指出）
by D0000 @ 2024-07-17 13:55:33
可能是写法不同，我的代码有一段：
void push_down(seg zyh,int l,int r,int o){//printf("(%d,%d)",l,r);
int mid=(l+r)>>1;
if(jisuan(zyh,mid)>jisuan(sgt[o].tag,mid)||(jisuan(zyh,mid)==jisuan(sgt[o].tag,mid)&&sgt[o].tag.id>zyh.id)){//if(zyh.id==49)//printf("(%d,%d)",l,r);//
seg ddx=zyh;
zyh=sgt[o].tag;
sgt[o].tag=ddx;
}
if(jisuan(zyh,l)<jisuan(sgt[o].tag,l)&&jisuan(zyh,r)<jisuan(sgt[o].tag,r))return;
if(l==r)return;
if(jisuan(zyh,l)<jisuan(sgt[o].tag,l))push_down(zyh,mid+1,r,o*2+1);
else push_down(zyh,l,mid,o*2);
}把 if(l==r)return; 注释掉后，去交 这道题就会 RE 7个点，但是本题不会，说明下方标记时不会到最后一层。
by D0000 @ 2024-07-17 13:57:03
虽然不能因为一份 AC 代码中有问题说明数据有问题，但是这或许能说明数据中的线段不存在很多条覆盖相同区间的线段
by lin_ziran @ 2024-07-17 19:22:58
@D0000
你说的对，数据水了，if (l == r) return; 不能省略。
我的证明有问题，因为 s 与 t 可能会相等。
这是我 AC 的记录
这是我 RE 6个点的记录（注释了 if (l == r) return;）
我还试着对拍了一下，发现确实会出错：