CF780G Andryusha and Nervous Barriers()-其他
CF780G Andryusha and Nervous Barriers()
\(\tt Link\)。
有些球在某次掉落后会处于相同高度，相同位置，我们将它们组合为一个「节点」。
假设扫描线到隔板 \(l,r,u,s\)，我们询问 \([l,r]\) 里高度 \(\le\min\{h+1,u+s\}\) 的「节点」的点总数并将这些「节点」删除，记点的总数为 \(v\)，然后将 \(u\) 为高，\(v\) 为点数组成的节点加入 \([l,r]\) 两端。
辅助上述操作的数据结构是线段树。线段树的底层维护按高度排序的所有节点。（你可以用 ，）。插入就暴力插，\(\mathcal O(\log w)\)。询问，因为已经按高度排好序，所以容易按照高度删除。
setpriority_queue但是你询问不能暴力遍历然后删除啊，这样复杂度是错的。考虑线段树维护子树深度最小值 \(v\)，如果 \(v\gt\) 询问的高度，那么这个子树就没用了。
复杂度分析见下。
const int N = 1e5 + 5;
const int S = N << 2;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
int h,w,n,L[N],R[N],T[S];
struct barrier{ int u,l,r,s; } B[N];
using node = pair<int,int>;
priority_queue<node> Q[N];
#define lc (i << 1)
#define rc (i << 1 | 1)
#define mid ((L + R) >> 1)
#define ls lc,L,mid
#define rs rc,mid + 1,R
#define id int i = 1,int L = 1,int R = w
#define psu T[i] = min(T[lc],T[rc])
void build(id){
if(L == R) return Q[L].emplace(-(T[i] = h + 1),-1);
build(ls); build(rs); psu;
}
void upd(int p,int h,int v,id){
if(L == R){
Q[L].emplace(-h,-v);
return void(T[i] = -Q[L].top().first);
}
p <= mid ? upd(p,h,v,ls) : upd(p,h,v,rs); psu;
}
int qry(int l,int r,int x,id){
if(T[i] > x) return 0;
int sum = 0;
if(L == R){
while(Q[L].size() && -Q[L].top().first <= x)
(sum += -Q[L].top().second) %= mod,Q[L].pop();
T[i] = Q[L].size() ? -Q[L].top().first : inf;
return sum;
}
if(l <= mid) sum += qry(l,r,x,ls);
if(r > mid) (sum += qry(l,r,x,rs)) %= mod;
psu; return sum;
}
int main(){
read(h,w,n);
rep(i,1,n) read(B[i].u,B[i].l,B[i].r,B[i].s);
sort(B + 1,B + n + 1,[](auto a,auto b){return a.u > b.u;});
build();
rep(i,1,n){
int x = qry(B[i].l,B[i].r,min(h + 1,B[i].s + B[i].u));
if(B[i].l != 1) upd(B[i].l - 1,B[i].u,x * ((B[i].r == w) + 1) % mod);
if(B[i].r != w) upd(B[i].r + 1,B[i].u,x * ((B[i].l == 1) + 1) % mod);
}
print(qry(1,w,inf));
return 0;
}
- 我们认为 \(n,w\) 同阶。
- 初始球的数量是 \(\mathcal O(w)\)，而让球数量发生变化的 upd 函数只会进行 \(\mathcal O(n)\) 次，所以球的总数是 \(\mathcal O(n)\) 的。
- 对于落到一块隔板的球，它们会合并为一个
- 对于没落到一块隔板的球，它们不会被再用到（因为隔板按高度降序）
- 所以复杂度正确
————————
\(\tt Link\)。
有些球在某次掉落后会处于相同高度，相同位置，我们将它们组合为一个「节点」。
假设扫描线到隔板 \(l,r,u,s\)，我们询问 \([l,r]\) 里高度 \(\le\min\{h+1,u+s\}\) 的「节点」的点总数并将这些「节点」删除，记点的总数为 \(v\)，然后将 \(u\) 为高，\(v\) 为点数组成的节点加入 \([l,r]\) 两端。
辅助上述操作的数据结构是线段树。线段树的底层维护按高度排序的所有节点。（你可以用 ，）。插入就暴力插，\(\mathcal O(\log w)\)。询问，因为已经按高度排好序，所以容易按照高度删除。
setpriority_queue但是你询问不能暴力遍历然后删除啊，这样复杂度是错的。考虑线段树维护子树深度最小值 \(v\)，如果 \(v\gt\) 询问的高度，那么这个子树就没用了。
复杂度分析见下。
const int N = 1e5 + 5;
const int S = N << 2;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
int h,w,n,L[N],R[N],T[S];
struct barrier{ int u,l,r,s; } B[N];
using node = pair<int,int>;
priority_queue<node> Q[N];
#define lc (i << 1)
#define rc (i << 1 | 1)
#define mid ((L + R) >> 1)
#define ls lc,L,mid
#define rs rc,mid + 1,R
#define id int i = 1,int L = 1,int R = w
#define psu T[i] = min(T[lc],T[rc])
void build(id){
if(L == R) return Q[L].emplace(-(T[i] = h + 1),-1);
build(ls); build(rs); psu;
}
void upd(int p,int h,int v,id){
if(L == R){
Q[L].emplace(-h,-v);
return void(T[i] = -Q[L].top().first);
}
p <= mid ? upd(p,h,v,ls) : upd(p,h,v,rs); psu;
}
int qry(int l,int r,int x,id){
if(T[i] > x) return 0;
int sum = 0;
if(L == R){
while(Q[L].size() && -Q[L].top().first <= x)
(sum += -Q[L].top().second) %= mod,Q[L].pop();
T[i] = Q[L].size() ? -Q[L].top().first : inf;
return sum;
}
if(l <= mid) sum += qry(l,r,x,ls);
if(r > mid) (sum += qry(l,r,x,rs)) %= mod;
psu; return sum;
}
int main(){
read(h,w,n);
rep(i,1,n) read(B[i].u,B[i].l,B[i].r,B[i].s);
sort(B + 1,B + n + 1,[](auto a,auto b){return a.u > b.u;});
build();
rep(i,1,n){
int x = qry(B[i].l,B[i].r,min(h + 1,B[i].s + B[i].u));
if(B[i].l != 1) upd(B[i].l - 1,B[i].u,x * ((B[i].r == w) + 1) % mod);
if(B[i].r != w) upd(B[i].r + 1,B[i].u,x * ((B[i].l == 1) + 1) % mod);
}
print(qry(1,w,inf));
return 0;
}
- 我们认为 \(n,w\) 同阶。
- 初始球的数量是 \(\mathcal O(w)\)，而让球数量发生变化的 upd 函数只会进行 \(\mathcal O(n)\) 次，所以球的总数是 \(\mathcal O(n)\) 的。
- 对于落到一块隔板的球，它们会合并为一个
- 对于没落到一块隔板的球，它们不会被再用到（因为隔板按高度降序）
- 所以复杂度正确