CF780G Andryusha and Nervous Barriers

CF780G Andryusha and Nervous Barriers

考虑树套树.

One-dimensional maintenance interval column,Another dimension maintains the height of the ball on the column,Make sure the points are correct.

maintenance single point,区间查.

The situation when the scan line height is maintained to each board from large to small.

优化：The interval check is to judge that the minimum height of the interval ball can only pass through the baffle and end.

时间复杂度 $\mathcal{O}(n{\log }^{2}n)$.

#include<bits/stdc++.h>

using namespace std;

#define int long long
typedef long long ll;

#define ha putchar(' ')
#define he putchar('\n')

inline int read() {
    
	int x = 0, f = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
    
		if (c == '-')
			f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9')
		x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	return x * f;
}

inline void write(int x) {
    
	if (x < 0) {
    
		putchar('-');
		x = -x;
	}
	if (x > 9)
		write(x / 10);
	putchar(x % 10 + 48);
}

const int _ = 1e5 + 10, mod = 1e9 + 7;

int h, w, n, N;

ll ans[_ << 2];

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q[_];

struct abc {
    
	int u, l, r, s;
	bool operator < (const abc &t) const {
    
		return u > t.u;
	}
} k[_];

void build(int o, int l, int r) {
    
	if (l == r) {
    
		q[l].push({
    h + 1, 1});
		ans[o] = h + 1;
		return;
	}
	int mid = (l + r) >> 1;
	build(o << 1, l, mid), build(o << 1 | 1, mid + 1, r);
	ans[o] = min(ans[o << 1], ans[o << 1 | 1]);
}

void upd(int o, int l, int r, int pos, int p, int h) {
    
	if (l == r) {
    
		q[l].push({
    h, p});
		ans[o] = min(ans[o], (ll)h);
		return;
	}
	int mid = (l + r) >> 1;
	if (pos <= mid) upd(o << 1, l, mid, pos, p, h);
	else upd(o << 1 | 1, mid + 1, r, pos, p, h);
	ans[o] = min(ans[o << 1], ans[o << 1 | 1]);
}

int qry(int o, int l, int r, int L, int R, int h, int s) {
    
	if (ans[o] > h + s) return 0;
	if (l == r) {
    
		int res = 0;
		while (!q[l].empty() && q[l].top().first <= h + s) {
    
			res = (res + q[l].top().second) % mod;
			q[l].pop();
		}
		ans[o] = q[l].empty() ? 1e10 + 7 : q[l].top().first;
		return res;
	}
	int mid = (l + r) >> 1, res = 0;
	if (L <= mid) res = qry(o << 1, l, mid, L, R, h, s);
	if (R > mid) res = (res + qry(o << 1 | 1, mid + 1, r, L, R, h, s)) % mod;
	ans[o] = min(ans[o << 1], ans[o << 1 | 1]);
	return res;
}

signed main() {
    
	h = read(), w = read(), n = read();
	for (int i = 1; i <= n; ++i) k[i].u = read(), k[i].l = read(), k[i].r = read(), k[i].s = read();
	N = w;
	build(1, 1, w);
	sort(k + 1, k + n + 1);
	for (int i = 1; i <= n; ++i) {
    
		int t = qry(1, 1, w, k[i].l, k[i].r, k[i].u, k[i].s);
		N = (N + t) % mod;
		if (k[i].l == 1) upd(1, 1, w, k[i].r + 1, (t << 1) % mod, k[i].u);
		else if (k[i].r == w) upd(1, 1, w, k[i].l - 1, (t << 1) % mod, k[i].u);
		else {
    
			upd(1, 1, w, k[i].l - 1, t, k[i].u);
			upd(1, 1, w, k[i].r + 1, t, k[i].u);
		}
	}
	write(N), he;
	return 0;
}