[BZOJ1171][BZOJ2892]大sz的游戏

时间：2021-03-10 16:24:30

[BZOJ1171][BZOJ2892]大sz的游戏

试题描述

大sz最近在玩一个由星球大战改编的游戏。话说绝地武士当前共控制了N个星球。但是，西斯正在暗处悄悄地准备他们的复仇计划。绝地评议会也感觉到了这件事。于是，准备加派绝地武士到各星球防止西斯的突袭。一个星球受到攻击以后，会尽快通知到总基地。需要的时间越长的星球就需要越多绝地武士来防御。为了合理分配有限的武士，大sz需要你帮他求出每个星球各需要多少时间能够通知到总基地。由于某种原因，N个星球排成一条直线，编号1至N。其中总基地建在1号星球上。每个星球虽然都是绝地武士控制的，但是上面居住的生物不一定相同，并且科技水平也不一样。第i个星球能收到并分析波长在[xi, yi]之间的信号，并且也能够发出在这个区间的信号，但是不能发出其他任何波长的信号。由于技术原因，每个星球只能发信号到比自己编号小的距离不超过L的星球。特别地，强大的总基地可以接收任何波长的信号。每个星球处理接收到的数据需要1个单位时间，传输时间可以忽略不计。

输入

第一行两个正整数N、L。接下来N-1行，总共第i行包含了三个正整数xi、yi、li，其中li表示第i个星球距离1号星球li，满足li严格递增。

输出

总共N-1行，每行一个数分别表示2到N号星球至少需要多少单位时间，总基地能够处理好数据，如果无法传到总基地则输出-1。

输入示例1





输出示例1








输入示例2








输出示例2








数据规模及约定


30%的数据满足N <=20000; 

100%的数据满足2 <=N<= 2.5*10^5、0<=xi，yi，li<=2*10^9，1<=L<=2*10^9,xi<=yi．


题解


首先这是一道裸 dp，f(i)表示对于星球 i 要求的答案，f(i) = min{ f(j) | [xi, yi]与[xj, yj]有交集 & l[i] - l[j] <= L & 0 < j < i } + 1.


最棘手的是两个区间有没有交集的问题。可以考虑离散后用线段树，但是要资瓷区间加入、删除、查询操作，不好搞，注意在上面的转移方程中，随着 i 的增长，j 所在的区间是一直向右移动的（因为 l[i] - l[j] <= L），或者说是一个滑动窗口，可以再套一个单调队列。


此外这里的线段树标记不好合并，所以干脆不进行标记下传；只在线段树的节点刚好被操作区间完全包含时，在这个节点上打标记，再向上更新一下最小值即可，询问时需要把节点到根的标记都取一个 min。（注意为什么这里我要把“标记”标红）




#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <queue>

#include <list>

using namespace std;

const int BufferSize = 1 << 16;

char buffer[BufferSize], *Head, *tail;

inline char Getchar() {

	if(Head == tail) {

		int l = fread(buffer, 1, BufferSize, stdin);

		tail = (Head = buffer) + l;

	}

	return *Head++;

}

int read() {

	int x = 0, f = 1; char c = Getchar();

	while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }

	while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }

	return x * f;

}

#define maxn 250005

#define oo 2147483646

int n, Len, num[maxn<<1], cnt, x[maxn], y[maxn], l[maxn], f[maxn], que[maxn], hd, tl;

list <int> Q[maxn<<3];

int res[maxn<<3];

void update(int L, int R, int o, int ql, int qr, int p, bool tp) {

	int M = L + R >> 1, lc = o << 1, rc = lc | 1;

	if(ql <= L && R <= qr) {

		if(!tp) {

			while(!Q[o].empty() && Q[o].front() <= p) Q[o].pop_front();

		}

		else {

			while(!Q[o].empty() && f[Q[o].back()] >= f[p]) Q[o].pop_back();

			Q[o].push_back(p);

		}

		res[o] = oo;

		if(!Q[o].empty()) {

			if(L < R) res[o] = min(res[lc], res[rc]);

			res[o] = min(res[o], f[Q[o].front()]);

		}

		else if(L < R) res[o] = min(res[lc], res[rc]);

		return ;

	}

	if(ql <= M) update(L, M, lc, ql, qr, p, tp);

	if(qr > M) update(M+1, R, rc, ql, qr, p, tp);

	res[o] = min(res[lc], res[rc]);

	if(!Q[o].empty()) res[o] = min(res[o], f[Q[o].front()]);

	return ;

}

int query(int L, int R, int o, int ql, int qr) {

	if(ql <= L && R <= qr) return res[o];

	int M = L + R >> 1, lc = o << 1, rc = lc | 1, ans = oo;

	if(ql <= M) ans = min(ans, query(L, M, lc, ql, qr));

	if(qr > M) ans = min(ans, query(M+1, R, rc, ql, qr));

	if(!Q[o].empty()) ans = min(ans, f[Q[o].front()]);

	return ans;

}

int main() {

	n = read(); Len = read();

	for(int i = 2; i <= n; i++) {

		num[++cnt] = x[i] = read(); num[++cnt] = y[i] = read();

		l[i] = read();

	}

	sort(num + 1, num + cnt + 1);

	for(int i = 2; i <= n; i++) {

		x[i] = lower_bound(num + 1, num + cnt + 1, x[i]) - num;

		y[i] = lower_bound(num + 1, num + cnt + 1, y[i]) - num;

	}

	for(int i = 0; i < (maxn<<3); i++) res[i] = oo;

	que[++tl] = 1;

	f[1] = 0; x[1] = 1; y[1] = cnt; l[1] = 0;

	update(1, cnt, 1, 1, cnt, 1, 1);

	for(int i = 2; i <= n; i++) {

		while(hd < tl && l[que[hd+1]] < l[i] - Len) {

			hd++;

			update(1, cnt, 1, x[que[hd]], y[que[hd]], que[hd], 0);

		}

		f[i] = query(1, cnt, 1, x[i], y[i]) + 1;

		if(f[i] < oo) {

			printf("%d\n", f[i]);

			que[++tl] = i;

			update(1, cnt, 1, x[i], y[i], i, 1);

		}

		else puts("-1");

	}

	return 0;

}

/*

3 3

1 2 1

2 3 2

8 100000

2 8192813 100000

5 23131346 113213

23131346 83131346 123213

23131346 83131346 199213

231346 103131346 213213

213 1038 213214

854 5432153 214214

*/



相关文章