企业官网建设流程全解析

题目链接 hdu 4614

错因及重点：lazy-tag

本题实现我用了两个lazy-tag，虽然考虑到了两个tag同时存在的情况，但没有把tag的时序和区间最终状态的关系考虑清楚。

下面贴出原始错误代码

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]被标记为1，a的子区间应变为插满状态，也就是说未执行的tag2[a]被新的tag1[a]覆盖，无需执行了，所以必须要将tag2[a]置为0。push_down操作解释同上。

现在还有个问题：

push_down层面上的区间状态唯一化可否通过控制两个push_down操作的顺序实现？在update1时先push_down2再push_down1，update2时先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"; } }

方法补充：只用一个tag，0表示清空，1表示插满，也可实现标签互斥