蒟蒻0分求助QWQ
  • 板块P1382 楼房
  • 楼主lin2
  • 当前回复9
  • 已保存回复9
  • 发布时间2023/4/27 22:06
  • 上次更新2023/10/23 17:23:44
查看原帖
蒟蒻0分求助QWQ
350468
lin2楼主2023/4/27 22:06

rt

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <map>
using namespace std;

const int SIZE = 1e5+5;

struct node {
	int mxv, tag;
} t[SIZE << 2];

int n;
int h[SIZE], l[SIZE], r[SIZE], tmp[SIZE], mxidx;
int cnt, ans[SIZE << 2][2];
map<int,int> pd, pr;

void pushup(int i) {
	t[i].mxv = max(t[i << 1].mxv, t[i << 1 | 1].mxv);
}

void addlz(int i, int v) {
	t[i].tag = v;
	t[i].mxv = max(t[i].mxv, v);
}

void pushdown(int i) {
	if (t[i].tag) {
		addlz(i << 1, t[i].tag);
		addlz(i << 1 | 1, t[i].tag);
		t[i].tag = 0;
	}
}

void bt(int i, int x, int y) {
	t[i].tag = 0;
	if (x == y) {
		t[i].mxv = 0;
	} else {
		int mid = x + y >> 1;
		bt(i << 1, x, mid);
		bt(i << 1 | 1, mid+1, y);
		pushup(i);
	}
}

void mdf(int i, int x, int y, int l, int r, int v) {
	if (l <= x && y <= r) {
		addlz(i, v);
	} else {
		pushdown(i);
		int mid = x + y >> 1;
		if (l <= mid) mdf(i << 1, x, mid, l, r, v);
		if (mid < r) mdf(i << 1 | 1, mid+1, y, l, r, v);
		pushup(i);
	}
}

int qry(int i, int x, int y, int pos) {
	if (x == y) {
		return t[i].mxv;
	} else {
		pushdown(i);
		int mid = x + y >> 1;
		if (pos <= mid) return qry(i << 1, x, mid, pos);
		else return qry(i << 1 | 1, mid+1, y, pos);
	}
}

void discre() {
	for (int i = 1; i <= n; ++i) {
		tmp[i] = l[i];
		tmp[i + n] = r[i];
	}
	sort(tmp + 1, tmp + 1 + 2 * n);
	int ed = unique(tmp + 1, tmp + 1 + 2 * n) - tmp;
	for (int i = 1; i <= 2 * n; ++i) {
		int idx = lower_bound(tmp + 1, tmp + ed, tmp[i]) - tmp;
		mxidx = max(mxidx, idx);
		pd[tmp[i]] = idx;
		pr[idx] = tmp[i];
	}
}

inline int height(int pos) {
	return qry(1, 1, mxidx, pos);
}

void pushpos(int x, int y) {
	ans[++cnt][0] = x, ans[cnt][1] = y;
}

int main() {
//	freopen("test.in","r",stdin);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		scanf("%d%d%d",h+i,l+i,r+i);
	}
	discre();
	bt(1, 1, mxidx);
	for (int i = 1; i <= n; ++i) {
		mdf(1, 1, mxidx, pd[l[i]], pd[r[i]]-1, h[i]);
	}
	int ch = 0, he, pos;
	for (int i = 1; i <= mxidx; ++i) {
		he = height(i);
		pos = pr[i];
		if (ch < he) {
			pushpos(pos, ch);
			pushpos(pos, he);
		} else if (ch > he) {
			pushpos(pos, ch);
			pushpos(pos, he);
		}
		ch = he;
	}
	printf("%d\n",cnt);
	for (int i = 1; i <= cnt; ++i) {
		printf("%d %d\n",ans[i][0],ans[i][1]);
	}
	return 0;
}
2023/4/27 22:06
加载中...