题目链接 hdu 4614错因及重点lazy-tag本题实现我用了两个lazy-tag虽然考虑到了两个tag同时存在的情况但没有把tag的时序和区间最终状态的关系考虑清楚。WA而不知所以下面贴出原始错误代码void pushdown(int l,int r,int x){ if(tag1[x]){ tag1[x] 0; int mid (l r) 1; tag1[ls(x)] 1; tree[ls(x)] mid - l 1; tag1[rs(x)] 1; tree[rs(x)] r - mid; } if(tag2[x]){ tag2[x] 0; tag2[ls(x)] 1; tree[ls(x)] 0; tag2[rs(x)] 1; tree[rs(x)] 0; } } void update1(int l,int r,int L,int R,int x){ if(l L r R){ tree[x] r - l 1; tag1[x] 1; return; } pushdown(l,r,x); int mid (l r) 1; if(L mid) update1(l,mid,L,R,ls(x)); if(R mid) update1(mid 1,r,L,R,rs(x)); pushup(x); //回溯修改父区间 } void update2(int l,int r,int L,int R,int x){ if(l L r R){ tree[x] 0; tag2[x] 1; return; } pushdown(l,r,x); int mid (l r) 1; if(L mid) update2(l,mid,L,R,ls(x)); if(R mid) update2(mid 1,r,L,R,rs(x)); pushup(x); } int query(int l,int r,int L,int R,int x){ if(l L r R) return tree[x]; pushdown(l,r,x); int res 0; int mid (l r) 1; if(L mid) res query(l,mid,L,R,ls(x)); if(R mid) res query(mid 1,r,L,R,rs(x)); return res; }ps.这里只贴出与lazy-tag相关的代码片段不是可运行代码破解的关键在于区间的最终状态假设区间a的下标为a改动a的tag的只有两种情况——update中区间完全覆盖时和push_down操作时指将a的父区间的标记下传到a。以a加tag1为例update区间a原本tag2[a]为1因为标记同时存在才会出现这种问题所以需要a原来已有另一标记即a的所有子区间此时应在清零状态只不过并未执行一旦tag1[a]被标记为1a的子区间应变为插满状态也就是说未执行的tag2[a]被新的tag1[a]覆盖无需执行了所以必须要将tag2[a]置为0。push_down操作解释同上。现在还有个问题push_down层面上的区间状态唯一化可否通过控制两个push_down操作的顺序实现在update1时先push_down2再push_down1update2时先push_down1再push_down2这是可以的。那query呢还需要两个query吗无济于事的因为在query时并不清楚tag间的覆盖关系因而无法确定push_down的先后关系。综上实现时要通过两个tag标记的互斥保证一个区间只有一种状态完整AC代码如下#include bits/stdc.h using namespace std; const int N 5e4; int tree[4 * N],tag1[4 * N],tag2[4 * N]; int ls(int x){return x 1;} int rs(int x){return x 1 | 1;} void pushup(int x){tree[x] tree[ls(x)] tree[rs(x)];} void pushdown(int l,int r,int x){ if(tag1[x]){ tag1[x] 0; int mid (l r) 1; tag1[ls(x)] 1; tag2[ls(x)] 0; //(ヮ) tree[ls(x)] mid - l 1; tag1[rs(x)] 1; tag2[rs(x)] 0; //(ヮ) tree[rs(x)] r - mid; } if(tag2[x]){ tag2[x] 0; tag2[ls(x)] 1; tag1[ls(x)] 0; //(ヮ) tree[ls(x)] 0; tag2[rs(x)] 1; tag1[rs(x)] 0; //(ヮ) tree[rs(x)] 0; } } void update1(int l,int r,int L,int R,int x){ if(l L r R){ tree[x] r - l 1; tag1[x] 1; tag2[x] 0; //(ヮ) return; } pushdown(l,r,x); int mid (l r) 1; if(L mid) update1(l,mid,L,R,ls(x)); if(R mid) update1(mid 1,r,L,R,rs(x)); pushup(x); } void update2(int l,int r,int L,int R,int x){ if(l L r R){ tree[x] 0; tag2[x] 1; tag1[x] 0; //(ヮ) return; } pushdown(l,r,x); int mid (l r) 1; if(L mid) update2(l,mid,L,R,ls(x)); if(R mid) update2(mid 1,r,L,R,rs(x)); pushup(x); } int query(int l,int r,int L,int R,int x){ if(l L r R) return tree[x]; pushdown(l,r,x); int res 0; int mid (l r) 1; if(L mid) res query(l,mid,L,R,ls(x)); if(R mid) res query(mid 1,r,L,R,rs(x)); return res; } int find_first(int l,int r,int n){ if(l r) return l; int mid (l r) 1; if(query(0,n - 1,l,mid,1) mid - l 1) return find_first(l,mid,n); else return find_first(mid 1,r,n); } int find_last(int l,int r,int n,int lef){ if(l r) return l; int mid (l r) 1; int used query(0,n - 1,l,mid,1); if(used lef mid - l 1) return find_last(l,mid,n,lef); else{ int lef1 lef - (mid - l 1 - used); return find_last(mid 1,r,n,lef1); } } int main(){ int t; cin t; while(t--){ int n,m; cin n m; for(int i 1;i 4 * n;i){ tree[i] 0; tag1[i] 0; tag2[i] 0; } while(m--){ int op; cin op; if(op 1){ int a,f; cin a f; if(query(0,n-1,a,n-1,1) n - a) cout Can not put any one.\n; else{ int l find_first(a,n - 1,n); int used query(0,n - 1,l,n - 1,1); /*测试样例的时候发现如果区间内剩余空位无法放下f朵花 在find_last逻辑下会一直到区间右端点而不是最后一个放下的位置加上了这个特判*/ if(n - l - used f) f n - l - used; int r find_last(l,n - 1,n,f); cout l r \n; update1(0,n - 1,l,r,1); } }else{ int a,b; cin a b; cout query(0,n - 1,a,b,1) \n; update2(0,n - 1,a,b,1); } } cout \n; } }方法补充只用一个tag0表示清空1表示插满也可实现标签互斥