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)\)。询问,因为已经按高度排好序,所以容易按照高度删除。

set
priority_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)\)。询问,因为已经按高度排好序,所以容易按照高度删除。

set
priority_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)\) 的。
  • 对于落到一块隔板的球,它们会合并为一个
  • 对于没落到一块隔板的球,它们不会被再用到(因为隔板按高度降序)
  • 所以复杂度正确